Weak \(\Delta\)-systems

Home
Search
Subjects

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 family \( {\mathcal A} = (A_1, \ldots, A_s)\) is called a weak \( \Delta\)-system if \( A_i \cap A_j\), for \( i \not = j\), are all of the same size. Let \( g(n,k)\) denote the least size for a family of n-sets forcing a weak \( \Delta\)-system of \( k\) sets. Erdös, Milner and Rado [2] proposed the following problem:

A conjecture on weak \(\Delta\)-systems \[ g (n,3) < c^n. \]

Recently, Axenovich, Fon der Flaass and Kostochka [1] proved

\(\displaystyle g(n,3) < (n!)^{1/2+ \epsilon}. \)

Bibliography
1	M. Axenovich, D. Fon der Flaass and A. V. Kostochka, On set systems without weak \( 3\)-\( \Delta\)-subsystems, 14th British Combinatorial Conference, Keele, 1993, Discrete Math. 138 (1995), 57-62.
2	P. Erdös, E. Milner and R. Rado, Intersection theorems for systems of sets, III, Collection of articles dedicated to the memory of Hanna Neumann IX, J. Austral. Math. Soc. l18 (1974), 22-40.

Bibliography

M. Axenovich, D. Fon der Flaass and A. V. Kostochka, On set systems without weak \( 3\)-\( \Delta\)-subsystems, 14th British Combinatorial Conference, Keele, 1993, Discrete Math. 138 (1995), 57-62.

P. Erdös, E. Milner and R. Rado, Intersection theorems for systems of sets, III, Collection of articles dedicated to the memory of Hanna Neumann IX, J. Austral. Math. Soc. l18 (1974), 22-40.