HOME

TheInfoList



OR:

In
graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, a branch of mathematics, the Erdős–Hajnal conjecture states that families of graphs defined by
forbidden induced subgraph In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidd ...
s have either large
cliques A clique ( AusE, CanE, or ; ), in the social sciences, is a small group of individuals who interact with one another and share similar interests rather than include others. Interacting with cliques is part of normative social development regardle ...
or large independent sets. It is named for
Paul Erdős Paul Erdős ( ; 26March 191320September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in discrete mathematics, g ...
and
András Hajnal András Hajnal (May 13, 1931 – July 30, 2016) was a professor of mathematics at Rutgers University and a member of the Hungarian Academy of Sciences known for his work in set theory and combinatorics. Biography Hajnal was born on 13 May 1931,< ...
, who first posed it as an open problem in a paper from 1977.. More precisely, for an arbitrary
undirected graph In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called '' vertices'' (also call ...
H, let \mathcal_H be the family of graphs that do not have H as an
induced subgraph In graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges, from the original graph, connecting pairs of vertices in that subset. Definition Formally, let G=(V,E) ...
. Then, according to the conjecture, there exists a constant \delta_H > 0 such that the n-vertex graphs in \mathcal_H have either a clique or an independent set of size \Omega(n^). In other words, for any
hereditary Heredity, also called inheritance or biological inheritance, is the passing on of traits from parents to their offspring; either through asexual reproduction or sexual reproduction, the offspring cells or organisms acquire the genetic inform ...
family \mathcal of graphs that is not the family of all graphs, there exists a constant \delta_>0 such that the n-vertex graphs in \mathcal have either a clique or an independent set of size \Omega(n^). A convenient and symmetric reformulation of the Erdős–Hajnal conjecture is that for every graph H, the H-free graphs necessarily contain a
perfect Perfect commonly refers to: * Perfection; completeness, and excellence * Perfect (grammar), a grammatical category in some languages Perfect may also refer to: Film and television * ''Perfect'' (1985 film), a romantic drama * ''Perfect'' (20 ...
induced subgraph of polynomial size. This is because every perfect graph necessarily has either a clique or independent set of size proportional to the square root of their number of vertices, and conversely every clique or independent set is itself perfect. Background on the conjecture can be found in two surveys, one of
András Gyárfás András Gyárfás (born 1945) is a Hungarian mathematician who specializes in the study of graph theory. He is famous for two conjectures: * Together with Paul Erdős he conjectured what is now called the Erdős–Gyárfás conjecture which sta ...
and the other of Maria Chudnovsky...


Graphs without large cliques or independent sets

In contrast, for
random graph In mathematics, random graph is the general term to refer to probability distributions over graphs. Random graphs may be described simply by a probability distribution, or by a random process which generates them. The theory of random graphs l ...
s in the
Erdős–Rényi model In the mathematical field of graph theory, the Erdős–Rényi model refers to one of two closely related models for generating random graphs or the evolution of a random network. These models are named after Hungarians, Hungarian mathematicians ...
with edge probability 1/2, both the
maximum clique In graph theory, a clique ( or ) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph G is an induced subgraph of G that is complete. Cliques are one of th ...
and the
maximum independent set In mathematical analysis, the maximum and minimum of a function are, respectively, the greatest and least value taken by the function. Known generically as extremum, they may be defined either within a given range (the ''local'' or ''relative ...
are much smaller: their size is proportional to the
logarithm In mathematics, the logarithm of a number is the exponent by which another fixed value, the base, must be raised to produce that number. For example, the logarithm of to base is , because is to the rd power: . More generally, if , the ...
of n, rather than growing polynomially.
Ramsey's theorem In combinatorics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. To demonstrate the theorem for two colours (sa ...
proves that no graph has both its maximum clique size and maximum independent set size smaller than logarithmic. Ramsey's theorem also implies the special case of the Erdős–Hajnal conjecture when H itself is a clique or independent set.


Partial results

This conjecture is due to
Paul Erdős Paul Erdős ( ; 26March 191320September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in discrete mathematics, g ...
and
András Hajnal András Hajnal (May 13, 1931 – July 30, 2016) was a professor of mathematics at Rutgers University and a member of the Hungarian Academy of Sciences known for his work in set theory and combinatorics. Biography Hajnal was born on 13 May 1931,< ...
, who proved it to be true when H is a
cograph In graph theory, a cograph, or complement-reducible graph, or ''P''4-free graph, is a graph that can be generated from the single-vertex graph ''K''1 by complementation and disjoint union. That is, the family of cographs is the smallest class of ...
.. They also showed, for arbitrary H, that the size of the largest clique or independent set grows superlogarithmically. More precisely, for every H there is a constant c such that the n-vertex H-free graphs have cliques or independent sets containing at least \exp c\sqrt vertices. The graphs H for which the conjecture is true also include those with four verticies or less, all five-vertex graphs, and any graph that can be obtained from these and the cographs by
modular decomposition In Graph (discrete mathematics), graph theory, the modular decomposition is a decomposition of a Graph (discrete mathematics), graph into subsets of Vertex (graph theory), vertices called modules. A ''module'' is a generalization of a Connected c ...
.. As of 2024, however, the full conjecture has not been proven, and remains an open problem. An earlier formulation of the conjecture, also by Erdős and Hajnal, concerns the special case when H is a 5-vertex
cycle graph In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with vertices is called ...
. This case has been resolved by Maria Chudnovsky, Alex Scott, Paul Seymour, and Sophie Spirkl.


Relation to the chromatic number of tournaments

Alon et al. showed that the following statement concerning
tournaments A tournament is a competition involving at least three competitors, all participating in a sport or game. More specifically, the term may be used in either of two overlapping senses: # One or more competitions held at a single venue and concentr ...
is equivalent to the Erdős–Hajnal conjecture. :Conjecture. For every tournament T, there exists \varepsilon(T) > 0 and c >0 such that for every T-free tournament G with n vertices \chi(G) \leq c \cdot n^. Here \chi(G) denotes the chromatic number of G, which is the smallest k \in \mathbb such that there is a k-coloring for G. A coloring of a tournament G is a mapping \phi:V(G) \rightarrow \ such that the color classes \ are transitive for all i = 1, \ldots , k. The class of tournaments H with the property that every H-free tournament G has \chi(G) \leq c(H) for some constant c(H) satisfies this equivalent Erdős–Hajnal conjecture (with \varepsilon = 1). Such tournaments H, called heroes, were considered by Berger et al.. 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 \Delta(H,k,1) or \Delta(H,1,k) for some hero H and some integer k \geq 0. Here \Delta(H,k,1) denotes the tournament with the three components H, the transitive tournament of size k and a single node q. The arcs between the three components are defined as follows: A = \. The tournament \Delta(H,1,k) is defined analogously.


References


External links


The Erdös-Hajnal Conjecture
The Open Problem Garden {{DEFAULTSORT:Erdos-Hajnal conjecture Ramsey theory Conjectures Unsolved problems in graph theory Hajnal conjecture