\(3\)chromatic cliques have edges with large intersection
Search
Subjects
 All (170)
 Ramsey Theory (40)
 Extremal Graph Theory (40)
 Coloring, Packing, and Covering (25)
 Random Graphs and Graph Enumeration (16)
 Hypergraphs (35)
 Infinite Graphs (14)
About Erdös
About This Site
A hypergraph \( H\) consists of a vertex set \( V\) together with a family \( E\) of subsets of \( V\), which are called the edges of \( H\). A \( r\)uniform hypergraph, or \( r\)graph, for short, is a hypergraph whose edge set consists of \( r\)subsets of \( V\). A graph is just a special case of an \( r\)graph with \( r=2\).
A hypergraph \( H\) is said to be \( k\)chromatic if the vertices of \( H\) can be colored in \( k\) colors so that every edge has at least \( 2\) colors.
A problem on \(3\)chromatic \(r\)cliques ($100) (proposed by Erdös and Lovász [1], [2])
Let \(H\) be an \(r\)graph in which every two edges have a nontrivial intersection (that is, \(H\) is an \(r\)clique). Suppose that \(H\) is \(3\)chromatic. Is it true that \(H\) contains two edges \(E\) and \(F\) for which \[ E \cap F \geq r2 ? \]Erdösand Lovász [1], [2] proved that there are always two edges \( E\) and \( F\) in such an \( r\)clique such that
They also showed that in a \( 3\)chromatic \( r\)clique there are at least three different values which are the sizes of the pairwise intersection of edges for large enough \( r\).
Bibliography  

1 
P. Erdös and L. Lovász, Problems and results on 3chromatic
hypergraphs and some related questions,
Infinite and finite sets (Colloq., Keszthely,
1973; dedicated to P. Erdös on his 60th birthday), Vol. I; Colloq.
Math. Soc. János Bolyai, Vol. 10, 609627, NorthHolland,
Amsterdam, 1975.

2  P. Erdös. Problems and results on set systems and hypergraphs. Extremal problems for finite sets (Visegrád, 1991), Bolyai Soc. Math. Stud., 3, pp. 217227, János Bolyai Math. Soc., Budapest, 1994.
