Conjecture on covering a hypergraph
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 conjecture on covering a hypergraph (proposed by Erdös and Lovász [2])
Let \(f(n)\) denote the smallest integer \(m\) such that for any \(n\)-element sets \(A_1, \dots, A_m\) with \(A_i \cap A_j \neq \emptyset\) for \(i \neq j\), and for every set \(S\) with at most \(n-1\) elements, there is an \(A_i\) disjoint from \(S\). Determine \(f(n)\).By considering the lines of a finite geometry, the following upper bound can be easily obtained:
\(\displaystyle f(n) \leq n^2-n+1. \)
Erdös and Lovász [2] proved that
\(\displaystyle \frac 8 3 n -3 \leq f(n) \leq c n^{3/2} \log n. \)
Kahn [3] showed that
\( f(n) = O(n)\). For the lower bound for \( f(n)\), Dow et al [1] proved that \( f(n) > 3n\) for \( n \geq 4\).
Bibliography | |
---|---|
1 | S. J. Dow, D. A. Drake, Z. Füredi and J. A. Larson. A lower bound for the cardinality of a maximal family of mutually
intersecting sets of equal size. Proceedings of the sixteenth Southeastern International Conference on Combinatorics, Graph Theory and Computing, Congr. Numer. 48 (1985), 47-48.
|
2 |
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,
Amsterdam, 1975.
|
3 |
J. Kahn, On a problem of Erdös and Lovász: random lines in a
projective plane, Combinatorica 12 (1992), 417-423.
|