Number of sizes of edge intersections in a \(3\)-chromatic \(r\)-graph
Home
Search
Subjects
About Erdös
About This Site
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 the edge-intersections of \(3\)-chromatic hypergraphs (proposed by Erdös and Lovász [1])
Let \(g(r)\) denote the least integer such that in any \(3\)-chromatic \(r\)-graph \(H\), the cardinalities \(|E\cap F|\), for edges \(E, F\) in \(H\), take on at least \(g(r)\) values.Is it true that \[ g(r) \rightarrow \infty \] as \(r \rightarrow \infty\)?
Is it true that \[ g(r) = r-2? \]