ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Conjecture 4. For each graph H there is c(H) > 0 such that every induced H-free graph on n vertices contains a clique or independent set of size at least nc . It is well-known that polynomial versions of theorems of Rödl and Nikiforov, as conjectured by Fox and Sudakov and Nguyen, Scott and Seymour imply the classical Erdős-Hajnal conjecture. In the recent paper [1], Bucić, Pham, and the speaker proved that these three conjectures are in fact equivalent, extending several previous particular results in this direction by Fox, Nguyen, Scott and Seymour; Nguyen, Scott and Seymour and Gishboliner and Shapira. We deduce that the family of string graphs satisfies the polynomial Rödl conjecture. The proof utilizes the graph container method, a powerful method in extremal graph theory. In this talk, we also presented a simple inductive proof of the graph container lemma from [1]. We also derived analogous results for hypergraphs, tournaments, ordered graphs, and colored graphs. In the direction of the Erdős-Hajnal conjecture, Erdős and Hajnal used the greedy embedding method to prove the following result. For every induced H-free graph G on nC(H) vertices with n \geq 2, G or its complement Ḡ contains Kn,n as a subgraph. The greedy embedding method is a general technique that is used in many extremal graph theory problems. The basic idea is to try to embed a copy of a graph one vertex at a time, keeping the sets of future potential vertices as large as possible. Using the powerful probabilistic method dependent random choice, Sudakov and the speaker [2] improved this to the following result in the direction of the Erdős-Hajnal conjecture. For every induced H-free graph G on nC(H) vertices, G contains an independent set of order n or Kn,n as a subgraph. Understanding how small MH (\varepsilon) is as a function of \varepsilon is an important problem with various applications in computer science, combinatorics, discrete geometry, and number theory. See the paper [3] by Zhao and the speaker for more about this problem. Another major open problem in this area is the Erdős-Hajnal conjecture: It is well-known that polynomial versions of theorems of Rödl and Nikiforov, as conjectured by Fox and Sudakov and Nguyen, Scott and Seymour imply the classical Erdős-Hajnal conjecture. In the recent paper [1], Bucić, Pham, and the speaker proved that these three conjectures are in fact equivalent, extending several previous particular results in this direction by Fox, Nguyen, Scott and Seymour; Nguyen, Scott and Seymour and Gishboliner and Shapira. We deduce that the family of string graphs satisfies the polynomial Rödl conjecture. The proof utilizes the graph container method, a powerful method in extremal graph theory. In this talk, we also presented a simple inductive proof of the graph container lemma from [1]. We also derived analogous results for hypergraphs, tournaments, ordered graphs, and colored graphs. In the direction of the Erdős-Hajnal conjecture, Erdős and Hajnal used the greedy embedding method to prove the following result. For every induced H-free graph G on nC(H) vertices with n \geq 2, G or its complement Ḡ contains Kn,n as a subgraph. The greedy embedding method is a general technique that is used in many extremal graph theory problems. The basic idea is to

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.