Stronger 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\).
The following is a strengthened version of this conjecture.
Conjecture [1]
For every \(c>0\), there is an \(\epsilon >0\) such that if \(n\) is sufficiently large and \(\{A_i: 1 \leq i \leq cn\}\) is a collection of intersecting \(n\)-sets, then there is a set \(S\) satisfying \(|S| < n(1-\epsilon)\) and \(A_i \cap S \not = \emptyset\) for all \(1 \leq i \leq cn\).
Bibliography | |
---|---|
1 |
P. Erdös, Some of my favourite unsolved problems, A
Tribute to Paul Erdös, 467-478, Cambridge Univ. Press,
Cambridge, 1990.
|