Pure pairs. III. Sparse graphs with no polynomial-sized anticomplete pairs
A graph is H-free if it has no induced subgraph isomorphic to H, and |G| denotes the number of vertices of G. A conjecture of Conlon, Sudakov and the second author asserts that: • For every graph H, there exists ε > 0 such that in every H-free graph G with |G| there are t...
| Main Authors: | , , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Wiley
2020
|
| _version_ | 1797054075179630592 |
|---|---|
| author | Chudnovsky, M Fox, J Scott, A Seymour, P Spirkl, S |
| author_facet | Chudnovsky, M Fox, J Scott, A Seymour, P Spirkl, S |
| author_sort | Chudnovsky, M |
| collection | OXFORD |
| description | A graph is H-free if it has no induced subgraph isomorphic to H, and |G| denotes the number of vertices of G. A conjecture of Conlon, Sudakov and the second author asserts that: • For every graph H, there exists ε > 0 such that in every H-free graph G with |G| there are two disjoint sets of vertices, of sizes at least ε|G|ε and ε|G|, complete or anticomplete to each other. This is equivalent to: • The “sparse linear conjecture”: For every graph H, there exists e > 0 such that in every H-free graph G with |G| > 1, either some vertex has degree at least ε|G|, or there are two disjoint sets of vertices, of sizes at least ε|G|ε and ε|G|, anticomplete to each other. We prove a number of partial results toward the sparse linear conjecture. In particular, we prove it holds for a large class of graphs H, and we prove that something like it holds for all graphs H. More exactly, say H is “almost-bipartite” if H is triangle-free and V(H) can be partitioned into a stable set and a set inducing a graph of maximum degree at most one. (This includes all graphs that arise from another graph by subdividing every edge at least once.) Our main result is: • The sparse linear conjecture holds for all almostbipartite graphs H. (It remains open when H is the triangle K3.) There is also a stronger theorem: • For every almost-bipartite graph H, there exist ε, t > 0 such that for every graph G with |G| > 1 and maximum degree less than ε|G|, and for every c with 0 < c = 1, either G contains εct |G||H| induced copies of H, or there are two disjoint sets A, B ⊆ V(G) with |A| = ect|G| and |B| = e|G|, and with at most c|A|·|B| edges between them. We also prove some variations on the sparse linear conjecture, such as: • For every graph H, there exists ε > 0 such that in every H-free graph G with |G| > 1 vertices, either some vertex has degree at least ε|G|, or there are two disjoint sets A, B of vertices with |A|·|B| = ε|G|1+ε, anticomplete to each other. |
| first_indexed | 2024-03-06T18:52:28Z |
| format | Journal article |
| id | oxford-uuid:10b6c762-0e0e-4bb2-8d00-2b30fffb59a1 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T18:52:28Z |
| publishDate | 2020 |
| publisher | Wiley |
| record_format | dspace |
| spelling | oxford-uuid:10b6c762-0e0e-4bb2-8d00-2b30fffb59a12022-03-26T09:57:53ZPure pairs. III. Sparse graphs with no polynomial-sized anticomplete pairsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:10b6c762-0e0e-4bb2-8d00-2b30fffb59a1EnglishSymplectic ElementsWiley 2020Chudnovsky, MFox, JScott, ASeymour, PSpirkl, SA graph is H-free if it has no induced subgraph isomorphic to H, and |G| denotes the number of vertices of G. A conjecture of Conlon, Sudakov and the second author asserts that: • For every graph H, there exists ε > 0 such that in every H-free graph G with |G| there are two disjoint sets of vertices, of sizes at least ε|G|ε and ε|G|, complete or anticomplete to each other. This is equivalent to: • The “sparse linear conjecture”: For every graph H, there exists e > 0 such that in every H-free graph G with |G| > 1, either some vertex has degree at least ε|G|, or there are two disjoint sets of vertices, of sizes at least ε|G|ε and ε|G|, anticomplete to each other. We prove a number of partial results toward the sparse linear conjecture. In particular, we prove it holds for a large class of graphs H, and we prove that something like it holds for all graphs H. More exactly, say H is “almost-bipartite” if H is triangle-free and V(H) can be partitioned into a stable set and a set inducing a graph of maximum degree at most one. (This includes all graphs that arise from another graph by subdividing every edge at least once.) Our main result is: • The sparse linear conjecture holds for all almostbipartite graphs H. (It remains open when H is the triangle K3.) There is also a stronger theorem: • For every almost-bipartite graph H, there exist ε, t > 0 such that for every graph G with |G| > 1 and maximum degree less than ε|G|, and for every c with 0 < c = 1, either G contains εct |G||H| induced copies of H, or there are two disjoint sets A, B ⊆ V(G) with |A| = ect|G| and |B| = e|G|, and with at most c|A|·|B| edges between them. We also prove some variations on the sparse linear conjecture, such as: • For every graph H, there exists ε > 0 such that in every H-free graph G with |G| > 1 vertices, either some vertex has degree at least ε|G|, or there are two disjoint sets A, B of vertices with |A|·|B| = ε|G|1+ε, anticomplete to each other. |
| spellingShingle | Chudnovsky, M Fox, J Scott, A Seymour, P Spirkl, S Pure pairs. III. Sparse graphs with no polynomial-sized anticomplete pairs |
| title | Pure pairs. III. Sparse graphs with no polynomial-sized anticomplete pairs |
| title_full | Pure pairs. III. Sparse graphs with no polynomial-sized anticomplete pairs |
| title_fullStr | Pure pairs. III. Sparse graphs with no polynomial-sized anticomplete pairs |
| title_full_unstemmed | Pure pairs. III. Sparse graphs with no polynomial-sized anticomplete pairs |
| title_short | Pure pairs. III. Sparse graphs with no polynomial-sized anticomplete pairs |
| title_sort | pure pairs iii sparse graphs with no polynomial sized anticomplete pairs |
| work_keys_str_mv | AT chudnovskym purepairsiiisparsegraphswithnopolynomialsizedanticompletepairs AT foxj purepairsiiisparsegraphswithnopolynomialsizedanticompletepairs AT scotta purepairsiiisparsegraphswithnopolynomialsizedanticompletepairs AT seymourp purepairsiiisparsegraphswithnopolynomialsizedanticompletepairs AT spirkls purepairsiiisparsegraphswithnopolynomialsizedanticompletepairs |