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

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

Research output: Contribution to journalArticlepeer-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 languageEnglish (US)
Pages (from-to)315-340
Number of pages26
JournalJournal of Graph Theory
Volume95
Issue number3
DOIs
StatePublished - Nov 1 2020

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Keywords

  • Erdős-Hajnal conjecture
  • induced subgraph

Fingerprint Dive into the research topics of 'Pure pairs. III. Sparse graphs with no polynomial-sized anticomplete pairs'. Together they form a unique fingerprint.

Cite this