{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,28]],"date-time":"2026-01-28T04:24:35Z","timestamp":1769574275554,"version":"3.49.0"},"reference-count":24,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2013,1,30]],"date-time":"2013-01-30T00:00:00Z","timestamp":1359504000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2013,3]]},"abstract":"<jats:p>A<jats:italic>partial Steiner (n,r,l)-system<\/jats:italic>is an<jats:italic>r<\/jats:italic>-uniform hypergraph on<jats:italic>n<\/jats:italic>vertices in which every set of<jats:italic>l<\/jats:italic>vertices is contained in at most one edge. A partial Steiner (<jats:italic>n,r,l<\/jats:italic>)-system is<jats:italic>complete<\/jats:italic>if every set of<jats:italic>l<\/jats:italic>vertices is contained in exactly one edge. In a hypergraph<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548312000557_char1\"\/><\/jats:private-char>, the independence number \u03b1(<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548312000557_char1\"\/><\/jats:private-char>) denotes the maximum size of a set of vertices in<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548312000557_char1\"\/><\/jats:private-char>containing no edge. In this article we prove the following. Given integers<jats:italic>r,l<\/jats:italic>such that<jats:italic>r<\/jats:italic>\u2265 2<jats:italic>l<\/jats:italic>\u2212 1 \u2265 3, we prove that there exists a partial Steiner (<jats:italic>n,r,l<\/jats:italic>)-system<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548312000557_char1\"\/><\/jats:private-char>such that<jats:disp-formula-group><jats:disp-formula><jats:alternatives><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" orientation=\"portrait\" mime-subtype=\"gif\" mimetype=\"image\" position=\"float\" xlink:type=\"simple\" xlink:href=\"S0963548312000557_eqnU1\"\/><jats:tex-math>$$\\alpha(\\HH) \\lesssim \\biggl(\\frac{l-1}{r-1}(r)_l\\biggr)^{\\frac{1}{r-1}}n^{\\frac{r-l}{r-1}} (\\log n)^{\\frac{1}{r-1}} \\quad \\mbox{ as }n \\rightarrow \\infty.$$<\/jats:tex-math><\/jats:alternatives><\/jats:disp-formula><\/jats:disp-formula-group>This improves earlier results of Phelps and R\u00f6dl, and R\u00f6dl and \u015cinajov\u00e1. We conjecture that it is best possible as it matches the independence number of a random<jats:italic>r<\/jats:italic>-uniform hypergraph of the same density. If<jats:italic>l<\/jats:italic>= 2 or<jats:italic>l<\/jats:italic>= 3, then for infinitely many<jats:italic>r<\/jats:italic>the partial Steiner systems constructed are complete for infinitely many<jats:italic>n<\/jats:italic>.<\/jats:p>","DOI":"10.1017\/s0963548312000557","type":"journal-article","created":{"date-parts":[[2013,1,30]],"date-time":"2013-01-30T15:45:55Z","timestamp":1359560755000},"page":"241-252","source":"Crossref","is-referenced-by-count":11,"title":["On the Independence Number of Steiner Systems"],"prefix":"10.1017","volume":"22","author":[{"given":"ALEX","family":"EUSTIS","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JACQUES","family":"VERSTRA\u00cbTE","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2013,1,30]]},"reference":[{"key":"S0963548312000557_ref24","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(75)90067-9"},{"key":"S0963548312000557_ref23","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(83)90273-X"},{"key":"S0963548312000557_ref20","first-page":"167","article-title":"Steiner triple systems with minimum independence number.","volume":"21","author":"Phelps","year":"1986","journal-title":"Ars Combin."},{"key":"S0963548312000557_ref18","doi-asserted-by":"crossref","unstructured":"Kostochka A. , Mubayi D. and Verstra\u00ebte J. (2011) On independent sets in hypergraphs. Random Struct. Alg. (accepted).","DOI":"10.1002\/rsa.20453"},{"key":"S0963548312000557_ref17","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-25.1.13"},{"key":"S0963548312000557_ref16","first-page":"191","article-title":"On a problem in combinations","volume":"II","author":"Kirkman","year":"1847","journal-title":"The Cambridge and Dublin Mathematical Journal"},{"key":"S0963548312000557_ref15","unstructured":"Keevash P. , Sudakov B. and Verstra\u00ebte J. (2011) On a conjecture of Erd\u0151s and Simonovits: Even Cycles. Combinatorica. (accepted)."},{"key":"S0963548312000557_ref19","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199807)12:4<381::AID-RSA5>3.0.CO;2-P"},{"key":"S0963548312000557_ref8","unstructured":"Eustis A. and Verstra\u00ebte J. (2012) Independent sets in randomized construction of Steiner (n,r,r-1)-systems. Preprint."},{"key":"S0963548312000557_ref22","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240050117"},{"key":"S0963548312000557_ref12","doi-asserted-by":"publisher","DOI":"10.1137\/0404019"},{"key":"S0963548312000557_ref2","doi-asserted-by":"crossref","unstructured":"Alon N. , Mellinger K. , Mubayi D. and Verstra\u00ebte J. (2011) The de Bruijn\u2013Erd\u0151s theorem for hypergraphs. Submitted.","DOI":"10.1007\/s10623-011-9555-4"},{"key":"S0963548312000557_ref13","unstructured":"Haemers W. (1980) Eigenvalue techniques in design and graph theory. PhD thesis, Technical University Eindhoven. Math. Centre Tract 121, Mathematical Centre, Amsterdam."},{"key":"S0963548312000557_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(85)80023-8"},{"key":"S0963548312000557_ref11","unstructured":"Frieze A. and Mubayi D. (2008) Coloring simple hypergraphs. Preprint."},{"key":"S0963548312000557_ref14","first-page":"601","article-title":"Proof of a conjecture of Erd\u0151s.","volume":"2","author":"Hajnal","year":"1970","journal-title":"Combin. Theory Appl."},{"key":"S0963548312000557_ref6","volume-title":"Finite Geometries","author":"Dembowski","year":"1996"},{"key":"S0963548312000557_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(82)90049-8"},{"key":"S0963548312000557_ref10","doi-asserted-by":"crossref","first-page":"R121","DOI":"10.37236\/845","article-title":"On the chromatic number of simple triangle-free triple systems","volume":"15","author":"Frieze","year":"2008","journal-title":"Electron. J. Combin."},{"key":"S0963548312000557_ref3","doi-asserted-by":"publisher","DOI":"10.1002\/0471722154"},{"key":"S0963548312000557_ref4","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190150110"},{"key":"S0963548312000557_ref5","doi-asserted-by":"publisher","DOI":"10.1201\/9781420049954"},{"key":"S0963548312000557_ref7","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240060208"},{"key":"S0963548312000557_ref9","doi-asserted-by":"crossref","first-page":"10","DOI":"10.5486\/PMD.1963.10.1-4.02","article-title":"On a limit theorem in combinatorial analysis.","volume":"10","author":"Erd\u0151s","year":"1963","journal-title":"Publ. Math. Debrecen"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548312000557","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,29]],"date-time":"2023-06-29T02:04:14Z","timestamp":1688004254000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548312000557\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1,30]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,3]]}},"alternative-id":["S0963548312000557"],"URL":"https:\/\/doi.org\/10.1017\/s0963548312000557","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1,30]]}}}