Английская Википедия:Erdős–Faber–Lovász conjecture

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Файл:Erdős–Faber–Lovász conjecture.svg
An instance of the Erdős–Faber–Lovász conjecture: a graph formed from four cliques of four vertices each, any two of which intersect in a single vertex, can be four-colored.

In graph theory, the Erdős–Faber–Lovász conjecture is a problem about graph coloring, named after Paul Erdős, Vance Faber, and László Lovász, who formulated it in 1972.[1] It says:

If Шаблон:Mvar complete graphs, each having exactly Шаблон:Mvar vertices, have the property that every pair of complete graphs has at most one shared vertex, then the union of the graphs can be properly colored with Шаблон:Mvar colors.

The conjecture for all sufficiently large values of Шаблон:Mvar was proved by Dong Yeap Kang, Tom Kelly, Daniela Kühn, Abhishek Methuku, and Deryk Osthus.[2]

Equivalent formulations

Шаблон:Harvtxt introduced the problem with a story about seating assignment in committees: suppose that, in a university department, there are Шаблон:Mvar committees, each consisting of Шаблон:Mvar faculty members, and that all committees meet in the same room, which has Шаблон:Mvar chairs. Suppose also that at most one person belongs to the intersection of any two committees. Is it possible to assign the committee members to chairs in such a way that each member sits in the same chair for all the different committees to which he or she belongs? In this model of the problem, the faculty members correspond to graph vertices, committees correspond to complete graphs, and chairs correspond to vertex colors.

A linear hypergraph (also known as partial linear space) is a hypergraph with the property that every two hyperedges have at most one vertex in common. A hypergraph is said to be uniform if all of its hyperedges have the same number of vertices as each other. The Шаблон:Mvar cliques of size Шаблон:Mvar in the Erdős–Faber–Lovász conjecture may be interpreted as the hyperedges of an Шаблон:Mvar-uniform linear hypergraph that has the same vertices as the underlying graph. In this language, the Erdős–Faber–Lovász conjecture states that, given any Шаблон:Mvar-uniform linear hypergraph with Шаблон:Mvar hyperedges, one may Шаблон:Mvar-color the vertices such that each hyperedge has one vertex of each color.[3]

A simple hypergraph is a hypergraph in which at most one hyperedge connects any pair of vertices and there are no hyperedges of size at most one. In the graph coloring formulation of the Erdős–Faber–Lovász conjecture, it is safe to remove vertices that belong to a single clique, as their coloring presents no difficulty; once this is done, the hypergraph that has a vertex for each clique, and a hyperedge for each graph vertex, forms a simple hypergraph. And, the hypergraph dual of vertex coloring is edge coloring. Thus, the Erdős–Faber–Lovász conjecture is equivalent to the statement that any simple hypergraph with Шаблон:Mvar vertices has chromatic index (edge coloring number) at most Шаблон:Mvar.[4]

The graph of the Erdős–Faber–Lovász conjecture may be represented as an intersection graph of sets: to each vertex of the graph, correspond the set of the cliques containing that vertex, and connect any two vertices by an edge whenever their corresponding sets have a nonempty intersection. Using this description of the graph, the conjecture may be restated as follows: if some family of sets has Шаблон:Mvar total elements, and any two sets intersect in at most one element, then the intersection graph of the sets may be Шаблон:Mvar-colored.[5]

The intersection number of a graph Шаблон:Mvar is the minimum number of elements in a family of sets whose intersection graph is Шаблон:Mvar, or equivalently the minimum number of vertices in a hypergraph whose line graph is Шаблон:Mvar. Шаблон:Harvtxt define the linear intersection number of a graph, similarly, to be the minimum number of vertices in a linear hypergraph whose line graph is Шаблон:Mvar. As they observe, the Erdős–Faber–Lovász conjecture is equivalent to the statement that the chromatic number of any graph is at most equal to its linear intersection number.

Шаблон:Harvtxt present another yet equivalent formulation, in terms of the theory of clones.

History, partial results, and eventual proof

Paul Erdős, Vance Faber, and László Lovász formulated the harmless looking conjecture at a party in Boulder Colorado in September 1972. Its difficulty was realised only slowly.[1] Paul Erdős originally offered US$50 for proving the conjecture in the affirmative, and later raised the reward to US$500.[1][6] In fact, Paul Erdős considered this to be one of his three most favourite combinatorial problems.[1][7]

Шаблон:Harvtxt proved that the chromatic number of the graphs in the conjecture is at most <math>\tfrac{3}{2} k - 2</math>, and Шаблон:Harvtxt improved this to Шаблон:Math.

Almost 50 years after the original conjecture was stated,[1] it was resolved for all sufficiently large Шаблон:Math by Dong Yeap Kang, Tom Kelly, Daniela Kühn, Abhishek Methuku, and Deryk Osthus.[8]

Related problems

It is also of interest to consider the chromatic number of graphs formed as the union of Шаблон:Mvar cliques of Шаблон:Mvar vertices each, without restricting how big the intersections of pairs of cliques can be. In this case, the chromatic number of their union is at most Шаблон:Math, and some graphs formed in this way require this many colors.[9]

A version of the conjecture that uses the fractional chromatic number in place of the chromatic number is known to be true. That is, if a graph Шаблон:Mvar is formed as the union of Шаблон:Mvar Шаблон:Mvar-cliques that intersect pairwise in at most one vertex, then Шаблон:Mvar can be Шаблон:Mvar-colored.[10]

In the framework of edge coloring simple hypergraphs, Шаблон:Harvtxt defines a number Шаблон:Mvar from a simple hypergraph as the number of hypergraph vertices that belong to a hyperedge of three or more vertices. He shows that, for any fixed value of Шаблон:Mvar, a finite calculation suffices to verify that the conjecture is true for all simple hypergraphs with that value of Шаблон:Mvar. Based on this idea, he shows that the conjecture is indeed true for all simple hypergraphs with Шаблон:Math. In the formulation of coloring graphs formed by unions of cliques, Hindman's result shows that the conjecture is true whenever at most ten of the cliques contain a vertex that belongs to three or more cliques. In particular, it is true for Шаблон:Math.

See also

Notes

Шаблон:Reflist

References

Шаблон:Refbegin

Шаблон:Refend

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ 1,0 1,1 1,2 1,3 1,4 Шаблон:Harvtxt.
  2. ↑ Шаблон:Harvtxt; Шаблон:Harvtxt; Шаблон:Harvtxt
  3. ↑ Шаблон:Harvtxt.
  4. ↑ Шаблон:Harvtxt. Шаблон:Harvtxt describes an equivalent problem in the language of set systems instead of hypergraphs.
  5. ↑ Шаблон:Harvtxt.
  6. ↑ Шаблон:Harvtxt.
  7. ↑ Шаблон:Harvtxt.
  8. ↑ Шаблон:Harvtxt.
  9. ↑ Шаблон:Harvtxt; Шаблон:Harvtxt.
  10. ↑ Шаблон:Harvtxt.
Источник — http://wikihandbk.com/ruwiki/index.php?title=Английская_Википедия:Erdős–Faber–Lovász_conjecture&oldid=14560516