Maximum unavoidable hypergraphs
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 \( r\)-graph \( H\) is said to be \( (n,e)\)-unavoidable if \( H\) is contained in every \( r\)-graph with \( n\) vertices and \( e\) edges. Let \( f_r(n,e)\) denote the largest integer \( m\) with the property that there exists an \( (n,e)\)-unavoidable \( r\)-graph having \( m\) edges.
A problem on unavoidable hypergraphs (proposed by Chung and Erdös [1])
Determine \(f_r(n,e)\).For the case of \( r=2\) and \( 3\), the solutions can be found in [2], [1].
Bibliography | |
---|---|
1 |
F. R. K. Chung and P. Erdös, On unavoidable hypergraphs, J.
Graph Theory 11 (1987), 251-263.
|
2 |
F. R. K. Chung and P. Erdös, On unavoidable graphs, Combinatorica 3 (1983), 167-176.
|