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 ...
, let
be the family of graphs that do not have
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
such that the
-vertex graphs in
have either a clique or an independent set of size
. 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
of graphs that is not the family of all graphs, there exists a constant
such that the
-vertex graphs in
have either a clique or an independent set of size
.
A convenient and symmetric reformulation of the Erdős–Hajnal conjecture is that for every graph
, the
-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
, 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
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
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
, 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.
The graphs
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
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
, 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.
[.] 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
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