Unavoidable stars with fixed intersection size
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 problem on unavoidable stars (proposed by Duke and Erdös [3])
Let \(f(n,r,k,t)\) denote the smallest integer \(m\) with the property that any \(r\)-graph on \(n\) vertices and \(m\) edges must contain a \(k\)-star with common intersection of size \(t\).Determine \(f(n,r,k,t)\).
Duke and Erdös [3] proved that \( f(n,r,k,1) \leq c n^{r-2}\), where \( c\) depends only on \( r\) and \( k\). For the case of \( r=3\), tight bounds are obtained by Chung and Frankl [1] (see also [4], [2]).
Bibliography | |
---|---|
1 |
F. R. K. Chung and P. Frankl,
The maximum number of edges in a \( 3\)-graph not containing a given star, Graphs and Combinatorics 3 (1987), 111-126.
|
2 | F. R. K. Chung,
Unavoidable stars in \( 3\)-graphs,
J. Comb. Theory Ser. A 35 (1983), 252-261.
|
3 |
P. Erdös and R. Duke,
Systems of finite sets having a common intersection,
Proceedings of the Eighth Southeastern Conference on
Combinatorics, Graph Theory and Computing (Louisiana State Univ.,
Baton Rouge, La., 1977), Congress. Numer. XIX, 247-252,
Utilitas Math., Winnipeg, Man., 1977.
|
4 | P. Frankl,
An extremal problem for \( 3\)-graphs,
Acta Math. Acad. Sci. Hungar. 32 (1978), 157-160.
|