Pure pairs. III. Sparse graphs with no polynomial-sized anticomplete pairs

Maria Chudnovsky; Jacob Fox; Alex Scott; Paul Seymour; Sophie Spirkl

doi:10.1002/jgt.22556

Pure pairs. III. Sparse graphs with no polynomial-sized anticomplete pairs

Maria Chudnovsky, Jacob Fox, Alex Scott, Paul Seymour, Sophie Spirkl

Mathematics

Princeton University

Research output: Contribution to journal › Article › peer-review

Abstract

A graph is (Formula presented.) -free if it has no induced subgraph isomorphic to (Formula presented.), and |G| denotes the number of vertices of (Formula presented.). A conjecture of Conlon, Sudakov and the second author asserts that: For every graph (Formula presented.), there exists (Formula presented.) such that in every (Formula presented.) -free graph (Formula presented.) with |G| there are two disjoint sets of vertices, of sizes at least (Formula presented.) and (Formula presented.), complete or anticomplete to each other. This is equivalent to: The “sparse linear conjecture”: For every graph (Formula presented.), there exists (Formula presented.) such that in every (Formula presented.) -free graph (Formula presented.) with (Formula presented.), either some vertex has degree at least (Formula presented.), or there are two disjoint sets of vertices, of sizes at least (Formula presented.) and (Formula presented.), 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 (Formula presented.), and we prove that something like it holds for all graphs (Formula presented.). More exactly, say (Formula presented.) is “almost-bipartite” if (Formula presented.) is triangle-free and (Formula presented.) 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 almost-bipartite graphs (Formula presented.). (It remains open when (Formula presented.) is the triangle (Formula presented.).) There is also a stronger theorem: For every almost-bipartite graph (Formula presented.), there exist (Formula presented.) such that for every graph (Formula presented.) with (Formula presented.) and maximum degree less than (Formula presented.), and for every (Formula presented.) with (Formula presented.), either (Formula presented.) contains (Formula presented.) induced copies of (Formula presented.), or there are two disjoint sets (Formula presented.) with (Formula presented.) and (Formula presented.), and with at most (Formula presented.) edges between them. We also prove some variations on the sparse linear conjecture, such as: For every graph (Formula presented.), there exists (Formula presented.) such that in every (Formula presented.) -free graph (Formula presented.) with (Formula presented.) vertices, either some vertex has degree at least (Formula presented.), or there are two disjoint sets (Formula presented.) of vertices with (Formula presented.), anticomplete to each other.

Original language	American English
Pages (from-to)	315-340
Number of pages	26
Journal	Journal of Graph Theory
Volume	95
Issue number	3
DOIs	https://doi.org/10.1002/jgt.22556
State	Published - Nov 1 2020

ASJC Scopus subject areas

Geometry and Topology

Keywords

Erdős-Hajnal conjecture
induced subgraph

Access to Document

10.1002/jgt.22556

Cite this

@article{dc26b38eb21547b1ab11bbacc18c6fe5,

title = "Pure pairs. III. Sparse graphs with no polynomial-sized anticomplete pairs",

abstract = "A graph is (Formula presented.) -free if it has no induced subgraph isomorphic to (Formula presented.), and |G| denotes the number of vertices of (Formula presented.). A conjecture of Conlon, Sudakov and the second author asserts that: For every graph (Formula presented.), there exists (Formula presented.) such that in every (Formula presented.) -free graph (Formula presented.) with |G| there are two disjoint sets of vertices, of sizes at least (Formula presented.) and (Formula presented.), complete or anticomplete to each other. This is equivalent to: The “sparse linear conjecture”: For every graph (Formula presented.), there exists (Formula presented.) such that in every (Formula presented.) -free graph (Formula presented.) with (Formula presented.), either some vertex has degree at least (Formula presented.), or there are two disjoint sets of vertices, of sizes at least (Formula presented.) and (Formula presented.), 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 (Formula presented.), and we prove that something like it holds for all graphs (Formula presented.). More exactly, say (Formula presented.) is “almost-bipartite” if (Formula presented.) is triangle-free and (Formula presented.) 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 almost-bipartite graphs (Formula presented.). (It remains open when (Formula presented.) is the triangle (Formula presented.).) There is also a stronger theorem: For every almost-bipartite graph (Formula presented.), there exist (Formula presented.) such that for every graph (Formula presented.) with (Formula presented.) and maximum degree less than (Formula presented.), and for every (Formula presented.) with (Formula presented.), either (Formula presented.) contains (Formula presented.) induced copies of (Formula presented.), or there are two disjoint sets (Formula presented.) with (Formula presented.) and (Formula presented.), and with at most (Formula presented.) edges between them. We also prove some variations on the sparse linear conjecture, such as: For every graph (Formula presented.), there exists (Formula presented.) such that in every (Formula presented.) -free graph (Formula presented.) with (Formula presented.) vertices, either some vertex has degree at least (Formula presented.), or there are two disjoint sets (Formula presented.) of vertices with (Formula presented.), anticomplete to each other.",

keywords = "Erd{\H o}s-Hajnal conjecture, induced subgraph",

author = "Maria Chudnovsky and Jacob Fox and Alex Scott and Paul Seymour and Sophie Spirkl",

note = "Publisher Copyright: {\textcopyright} 2020 Wiley Periodicals, Inc.",

year = "2020",

month = nov,

day = "1",

doi = "10.1002/jgt.22556",

language = "American English",

volume = "95",

pages = "315--340",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "3",

}

TY - JOUR

T1 - Pure pairs. III. Sparse graphs with no polynomial-sized anticomplete pairs

AU - Chudnovsky, Maria

AU - Fox, Jacob

AU - Scott, Alex

AU - Seymour, Paul

AU - Spirkl, Sophie

PY - 2020/11/1

Y1 - 2020/11/1

N2 - A graph is (Formula presented.) -free if it has no induced subgraph isomorphic to (Formula presented.), and |G| denotes the number of vertices of (Formula presented.). A conjecture of Conlon, Sudakov and the second author asserts that: For every graph (Formula presented.), there exists (Formula presented.) such that in every (Formula presented.) -free graph (Formula presented.) with |G| there are two disjoint sets of vertices, of sizes at least (Formula presented.) and (Formula presented.), complete or anticomplete to each other. This is equivalent to: The “sparse linear conjecture”: For every graph (Formula presented.), there exists (Formula presented.) such that in every (Formula presented.) -free graph (Formula presented.) with (Formula presented.), either some vertex has degree at least (Formula presented.), or there are two disjoint sets of vertices, of sizes at least (Formula presented.) and (Formula presented.), 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 (Formula presented.), and we prove that something like it holds for all graphs (Formula presented.). More exactly, say (Formula presented.) is “almost-bipartite” if (Formula presented.) is triangle-free and (Formula presented.) 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 almost-bipartite graphs (Formula presented.). (It remains open when (Formula presented.) is the triangle (Formula presented.).) There is also a stronger theorem: For every almost-bipartite graph (Formula presented.), there exist (Formula presented.) such that for every graph (Formula presented.) with (Formula presented.) and maximum degree less than (Formula presented.), and for every (Formula presented.) with (Formula presented.), either (Formula presented.) contains (Formula presented.) induced copies of (Formula presented.), or there are two disjoint sets (Formula presented.) with (Formula presented.) and (Formula presented.), and with at most (Formula presented.) edges between them. We also prove some variations on the sparse linear conjecture, such as: For every graph (Formula presented.), there exists (Formula presented.) such that in every (Formula presented.) -free graph (Formula presented.) with (Formula presented.) vertices, either some vertex has degree at least (Formula presented.), or there are two disjoint sets (Formula presented.) of vertices with (Formula presented.), anticomplete to each other.

AB - A graph is (Formula presented.) -free if it has no induced subgraph isomorphic to (Formula presented.), and |G| denotes the number of vertices of (Formula presented.). A conjecture of Conlon, Sudakov and the second author asserts that: For every graph (Formula presented.), there exists (Formula presented.) such that in every (Formula presented.) -free graph (Formula presented.) with |G| there are two disjoint sets of vertices, of sizes at least (Formula presented.) and (Formula presented.), complete or anticomplete to each other. This is equivalent to: The “sparse linear conjecture”: For every graph (Formula presented.), there exists (Formula presented.) such that in every (Formula presented.) -free graph (Formula presented.) with (Formula presented.), either some vertex has degree at least (Formula presented.), or there are two disjoint sets of vertices, of sizes at least (Formula presented.) and (Formula presented.), 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 (Formula presented.), and we prove that something like it holds for all graphs (Formula presented.). More exactly, say (Formula presented.) is “almost-bipartite” if (Formula presented.) is triangle-free and (Formula presented.) 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 almost-bipartite graphs (Formula presented.). (It remains open when (Formula presented.) is the triangle (Formula presented.).) There is also a stronger theorem: For every almost-bipartite graph (Formula presented.), there exist (Formula presented.) such that for every graph (Formula presented.) with (Formula presented.) and maximum degree less than (Formula presented.), and for every (Formula presented.) with (Formula presented.), either (Formula presented.) contains (Formula presented.) induced copies of (Formula presented.), or there are two disjoint sets (Formula presented.) with (Formula presented.) and (Formula presented.), and with at most (Formula presented.) edges between them. We also prove some variations on the sparse linear conjecture, such as: For every graph (Formula presented.), there exists (Formula presented.) such that in every (Formula presented.) -free graph (Formula presented.) with (Formula presented.) vertices, either some vertex has degree at least (Formula presented.), or there are two disjoint sets (Formula presented.) of vertices with (Formula presented.), anticomplete to each other.

KW - Erdős-Hajnal conjecture

KW - induced subgraph

UR - http://www.scopus.com/inward/record.url?scp=85080874749&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85080874749&partnerID=8YFLogxK

U2 - 10.1002/jgt.22556

DO - 10.1002/jgt.22556

M3 - Article

SN - 0364-9024

VL - 95

SP - 315

EP - 340

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 3

ER -

Pure pairs. III. Sparse graphs with no polynomial-sized anticomplete pairs

Abstract

ASJC Scopus subject areas

Keywords

Access to Document

Other files and links

Fingerprint

Cite this