Unavoidable stars
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\).
Let us call a family \( {\mathcal S } = (S_1, S_2, \ldots, S_r)\) of \( r\)-graphs \( S_i\), a \( t\)-star with center \( A\), if for all \( i <j\), \( S_i \cap S_j = A \) (possibly empty). Stars were introduced by Erdös and Rado [1] in 1960 under the name strong delta systems, where they proved that every large \( r\)-graph contains a \( t\)-star. Let \( f(r,t)\) denote the maximum number of \( r\)-sets one can have without containing a \( t\)-star. Erdös and Rado [1] showed that
A problem on unavoidable stars $1000 (proposed by Erdös and Rado [1] in 1960)
For given integers \(r\) and for any \(t \geq 3\), decide if \[ f(r,t) \leq c_t^r \] where \(c_t\) depends only on \(t\) (and is independent of \(r\)).In Erdös' problem papers, he often liked to mention the case of \( t=3\) (e.g., see [2]). See also this problem.