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…
Statement
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. 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 .
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 inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.