×

Note on independent sets in Steiner systems. (English) Zbl 0793.05020

Summary: A partial Steiner \((n,k,l)\)-system or briefly \((n,k,l)\)-system is a pair \((V,{\mathbf S})\), where \(V\) is an \(n\)-set and \({\mathbf S}\) is a collection of \(k\)-subsets of \(V\), such that every \(l\)-subset of \(V\) is contained in at most one \(k\)-subset of \({\mathbf S}\). A subset \(X\subset V\) is called independent if \([X]^ k\cap{\mathbf S}=\varnothing\). The size of the largest independent set in \({\mathbf S}\) is denoted by \(\alpha({\mathbf S})\). Define \[ f(n,k,l)=\min\bigl\{\alpha({\mathbf S}),\;{\mathbf S}\text{ is an }(n,k,l)\text{-system}\bigr\}. \] The purpose of this note is to prove that for every \(k\), \(l\), \(k>l\), \[ cn^{{k-l\over k-1}}(\log n)^{{1\over k-1}}\leq f(n,k,l)\leq dn^{{k-l\over k-1}}(\log n)^{{1\over k-1}} \] holds, where \(c\), \(d\) are positive constants depending on \(k\) and \(l\) only.

MSC:

05B07 Triple systems
60C05 Combinatorial probability
05C65 Hypergraphs
Full Text: DOI

References:

[1] Ajtai, J. Combinat. Theory A 32 pp 321– (1982)
[2] , and , On an anti-Ramsey type result (manuscript).
[3] DeBrandes, SIAM J. Alg. 3 pp 242– (1982)
[4] Erdös, Acta Math. Acad. Sci. Hung. 17 pp 61– (1966)
[5] and , Problems and results on 3-chromatic hypergraphs and some related questions. in Infinite and Finite Sets, , and , Eds., North-Holland, Amsterdam, 1975, pp. 609–628.
[6] Furedi, SIAM J. Alg. 4 pp 2– (1991)
[7] and , Numbers in Ramsey theory, Surv. Combinat. (1987), London Math. Soc., Lect. Notes Ser., 123.
[8] and , Design Theory, Cambridge University Press, Cambridge, England, 1985. · doi:10.1017/CBO9780511566066
[9] Phelps, Ars Combinat. 21 pp 167– (1986)
[10] Spencer, Discrete Math. 20 pp 69– (1977)
[11] An existence theory for pairwise balanced designs, J. Combinat. Theory A, 220–245 (1972). · Zbl 0263.05014
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.