\(3\)-chromatic cliques have edges with large intersection
- 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 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.
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\).
P. Erdös and L. Lovász, Problems and results on 3-chromatic
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, 609-627, North-Holland,
|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. 217-227, János Bolyai Math. Soc., Budapest, 1994.