Erdős–Hajnal conjecture

In graph theory, a branch of mathematics, the Erdős–Hajnal conjecture states that families of graphs defined by forbidden induced subgraphs have either large cliques or large independent sets. It is named for Paul Erdős and András Hajnal.

Unsolved problem in mathematics:

Do the graphs with a fixed forbidden induced subgraph necessarily have large cliques or large independent sets?

More precisely, for an arbitrary undirected graph , let be the family of graphs that do not have as an induced subgraph. Then, according to the conjecture, there exists a constant such that the -vertex graphs in have either a clique or an independent set of size .

An equivalent statement to the original conjecture is that, for every graph , the -free graphs all contain polynomially large perfect induced subgraphs.

Graphs without large cliques or independent sets

In contrast, for random graphs in the Erdős–Rényi model with edge probability 1/2, both the maximum clique and the maximum independent set are much smaller: their size is proportional to the logarithm of , rather than growing polynomially. Ramsey's theorem proves that no graph has both its maximum clique size and maximum independent set size smaller than logarithmic.[1][2] Ramsey's theorem also implies the special case of the Erdős–Hajnal conjecture when itself is a clique or independent set.[1]

Partial results

This conjecture is due to Paul Erdős and András Hajnal, who proved it to be true when is a cograph. They also showed, for arbitrary , that the size of the largest clique or independent set grows superlogarithmically. More precisely, for every there is a constant such that the -vertex -free graphs have cliques or independent sets containing at least vertices.[1][3] The graphs for which the conjecture is true also include those with four verticies or less,[1][4] all five-vertex graphs except the five-vertex path and its complement,[5][1][6] and any graph that can be obtained from these and the cographs by modular decomposition.[1][2] As of 2021, however, the full conjecture has not been proven, and remains an open problem.[1]

An earlier formulation of the conjecture, also by Erdős and Hajnal, concerns the special case when is a 5-vertex cycle graph.[4] This case has been resolved by Maria Chudnovsky, Alex Scott, Paul Seymour, and Sophie Spirkl in 2021.[7][8] The -free graphs include the perfect graphs, which necessarily have either a clique or independent set of size proportional to the square root of their number of vertices. Conversely, every clique or independent set is itself perfect. For this reason, a convenient and symmetric reformulation of the Erdős–Hajnal conjecture is that for every graph , the -free graphs necessarily contain an induced perfect subgraph of polynomial size.[1]

Relation to the chromatic number of tournaments

Alon et al. [2] showed that the following statement concerning tournaments is equivalent to the Erdős-Hajnal conjecture.

Conjecture. For every tournament , there exists and such that for every -free tournament with vertices .

Here denotes the chromatic number of , which is the smallest such that there is a -coloring for . A coloring of a tournament is a mapping such that the color classes are transitive for all .

The class of tournaments with the property that every -free tournament has for some constant satisfies this equivalent Erdős-Hajnal conjecture (with ). Such tournaments , called heroes, were considered by Berger et al.[9] There it is proven that a hero has a special structure which is as follows:

Theorem. A tournament is a hero if and only if all its strong components are heroes. A strong tournament with more than one vertex is a hero if and only if it equals or for some hero and some integer .

Here denotes the tournament with the three components , the transitive tournament of size and a single node . The arcs between the three components are defined as follows: . The tournament is defined analogously.

References

  1. Chudnovsky, Maria (2014), "The Erdös–Hajnal conjecture—a survey" (PDF), Journal of Graph Theory, 75 (2): 178–190, arXiv:1606.08827, doi:10.1002/jgt.21730, MR 3150572, S2CID 985458, Zbl 1280.05086.
  2. Alon, Noga; Pach, János; Solymosi, József (2001), "Ramsey-type theorems with forbidden subgraphs", Combinatorica, 21 (2): 155–170, doi:10.1007/s004930100016, MR 1832443, S2CID 7590638, Zbl 0989.05124.
  3. Erdős, P.; Hajnal, A. (1989), "Ramsey-type theorems", Discrete Applied Mathematics, 25 (1–2): 37–52, doi:10.1016/0166-218X(89)90045-0, MR 1031262, Zbl 0715.05052.
  4. Gyárfás, András (1997), "Reflections on a problem of Erdős and Hajnal", The mathematics of Paul Erdős, II, Algorithms Combin., vol. 14, Springer, Berlin, pp. 93–98, doi:10.1007/978-3-642-60406-5_10, MR 1425208.
  5. Nadis, Steve (26 April 2021). "New Proof Reveals That Graphs With No Pentagons Are Fundamentally Different". Quanta Magazine. Retrieved 2021-04-26.
  6. Chudnovsky, Maria; Safra, Shmuel (2008), "The Erdős–Hajnal conjecture for bull-free graphs", Journal of Combinatorial Theory, Series B, 98 (6): 1301–1310, doi:10.1016/j.jctb.2008.02.005, MR 2462320.
  7. Chudnovsky, Maria; Scott, Alex; Seymour, Paul; Spirkl, Sophie (2021), Erdős–Hajnal for graphs with no 5-hole (PDF), arXiv:2102.04994.
  8. Chudnovsky, Maria; Scott, Alex; Seymour, Paul; Spirkl, Sophie (2023-01-31). "Erdős–Hajnal for graphs with no 5‐hole". Proceedings of the London Mathematical Society. Wiley. 126 (3): 997–1014. doi:10.1112/plms.12504. ISSN 0024-6115.
  9. Berger, E.; Choromanski, K.; Chudnovsky, M.; Fox, J.; Loebl, M.; Scott, A.; Seymour, P.; Thomasse, S. (2013), "Tournaments and coloring", Journal of Combinatorial Theory, Series B, 103 (1): 1–20, doi:10.1016/j.jctb.2012.08.003.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.