Loading...
Please wait, while we are loading the content...
Universal and unavoidable graphs
| Content Provider | Scilit |
|---|---|
| Author | Bucić, Matija Draganić, Nemanja Sudakov, Benny |
| Copyright Year | 2021 |
| Description | The Turán number ex(n, H) of a graph H is the maximal number of edges in an H-free graph on n vertices. In 1983, Chung and Erdős asked which graphs H with e edges minimise ex(n, H). They resolved this question asymptotically for most of the range of e and asked to complete the picture. In this paper, we answer their question by resolving all remaining cases. Our result translates directly to the setting of universality, a well-studied notion of finding graphs which contain every graph belonging to a certain family. In this setting, we extend previous work done by Babai, Chung, Erdős, Graham and Spencer, and by Alon and Asodi. |
| Related Links | https://www.cambridge.org/core/services/aop-cambridge-core/content/view/AF73AF5A5324830C149338577258AFFC/S0963548321000110a.pdf/div-class-title-universal-and-unavoidable-graphs-div.pdf |
| Ending Page | 955 |
| Page Count | 14 |
| Starting Page | 942 |
| ISSN | 09635483 |
| e-ISSN | 14692163 |
| DOI | 10.1017/s0963548321000110 |
| Journal | Combinatorics, Probability and Computing |
| Issue Number | 6 |
| Volume Number | 30 |
| Language | English |
| Publisher | Cambridge University Press (CUP) |
| Publisher Date | 2021-11-01 |
| Access Restriction | Open |
| Subject Keyword | Combinatorics, Probability and Computing Applied Mathematics |
| Content Type | Text |
| Resource Type | Article |
| Subject | Applied Mathematics Statistics and Probability Theoretical Computer Science Computational Theory and Mathematics |
