{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,28]],"date-time":"2026-01-28T07:24:29Z","timestamp":1769585069663,"version":"3.49.0"},"reference-count":21,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2012,8,2]],"date-time":"2012-08-02T00:00:00Z","timestamp":1343865600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Random Struct Algorithms"],"published-print":{"date-parts":[[2014,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The <jats:italic>independence number<\/jats:italic> <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/rsa20453-math-0001.gif\" xlink:title=\"urn:x-wiley::media:rsa20453:rsa20453-math-0001\"\/> of a hypergraph <jats:italic>H<\/jats:italic> is the size of a largest set of vertices containing no edge of <jats:italic>H<\/jats:italic>. In this paper, we prove that if <jats:italic>H<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> is an <jats:italic>n<\/jats:italic>\u2010vertex <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/rsa20453-math-0002.gif\" xlink:title=\"urn:x-wiley::media:rsa20453:rsa20453-math-0002\"\/>\u2010uniform hypergraph in which every <jats:italic>r<\/jats:italic>\u2010element set is contained in at most <jats:italic>d<\/jats:italic> edges, where <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/rsa20453-math-0003.gif\" xlink:title=\"urn:x-wiley::media:rsa20453:rsa20453-math-0003\"\/>, then\n<jats:disp-formula>\n<jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" position=\"anchor\" xlink:href=\"graphic\/rsa20453-math-0004.gif\"><jats:alt-text>urn:x-wiley::media:rsa20453:rsa20453-math-0004<\/jats:alt-text><\/jats:graphic>\n<\/jats:disp-formula>\nwhere <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/rsa20453-math-0005.gif\" xlink:title=\"urn:x-wiley::media:rsa20453:rsa20453-math-0005\"\/> satisfies <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/rsa20453-math-0006.gif\" xlink:title=\"urn:x-wiley::media:rsa20453:rsa20453-math-0006\"\/> as <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/rsa20453-math-0007.gif\" xlink:title=\"urn:x-wiley::media:rsa20453:rsa20453-math-0007\"\/>. The value of <jats:italic>c<\/jats:italic><jats:sub><jats:italic>r<\/jats:italic><\/jats:sub> improves and generalizes several earlier results that all use a theorem of Ajtai, Koml\u00f3s, Pintz, Spencer and Szemer\u00e9di (J Comb Theory Ser A 32 (1982), 321\u2013335). Our relatively short proof extends a method due to Shearer (Random Struct Algorithms 7 (1995), 269\u2013271) and Alon (Random Struct Algorithms 9 (1996), 271\u2013278). The above statement is close to best possible, in the sense that for each <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/rsa20453-math-0008.gif\" xlink:title=\"urn:x-wiley::media:rsa20453:rsa20453-math-0008\"\/> and all values of <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/rsa20453-math-0009.gif\" xlink:title=\"urn:x-wiley::media:rsa20453:rsa20453-math-0009\"\/>, there are infinitely many <jats:italic>H<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> such that\n<jats:disp-formula>\n<jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" position=\"anchor\" xlink:href=\"graphic\/rsa20453-math-0010.gif\"><jats:alt-text>urn:x-wiley::media:rsa20453:rsa20453-math-0010<\/jats:alt-text><\/jats:graphic>\n<\/jats:disp-formula>\nwhere <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/rsa20453-math-0011.gif\" xlink:title=\"urn:x-wiley::media:rsa20453:rsa20453-math-0011\"\/> depends only on <jats:italic>r<\/jats:italic>. In addition, for many values of <jats:italic>d<\/jats:italic> we show <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/rsa20453-math-0012.gif\" xlink:title=\"urn:x-wiley::media:rsa20453:rsa20453-math-0012\"\/> as <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/rsa20453-math-0013.gif\" xlink:title=\"urn:x-wiley::media:rsa20453:rsa20453-math-0013\"\/>, so the result is almost sharp for large <jats:italic>r<\/jats:italic>. We give an application to hypergraph Ramsey numbers involving independent neighborhoods.Copyright \u00a9 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 224\u2010239, 2014<\/jats:p>","DOI":"10.1002\/rsa.20453","type":"journal-article","created":{"date-parts":[[2012,8,3]],"date-time":"2012-08-03T17:47:01Z","timestamp":1344016021000},"page":"224-239","source":"Crossref","is-referenced-by-count":32,"title":["On independent sets in hypergraphs"],"prefix":"10.1002","volume":"44","author":[{"given":"Alexandr","family":"Kostochka","sequence":"first","affiliation":[{"name":"Department of Mathematics University of Illinois, Urbana\u2010Champaign Urbana Illinois"}]},{"given":"Dhruv","family":"Mubayi","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Statistics, and Computer Science University of Illinois Chicago Illinois 60607"}]},{"given":"Jacques","family":"Verstra\u00ebte","sequence":"additional","affiliation":[{"name":"Department of Mathematics University of California, San Diego (UCSD) La Jolla California 92093\u20100112"}]}],"member":"311","published-online":{"date-parts":[[2012,8,2]]},"reference":[{"key":"e_1_2_11_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(82)90049-8"},{"key":"e_1_2_11_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(80)90030-8"},{"key":"e_1_2_11_4_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199610)9:3<271::AID-RSA1>3.0.CO;2-U"},{"key":"e_1_2_11_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1999.1910"},{"key":"e_1_2_11_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-010-2474-6"},{"key":"e_1_2_11_7_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729330"},{"key":"e_1_2_11_8_1","first-page":"187","volume-title":"Extremal problems for finite sets","author":"Caen D.","year":"1994"},{"key":"e_1_2_11_9_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240060208"},{"key":"e_1_2_11_10_1","first-page":"97","volume-title":"Combinatorial mathematics and its applications","author":"Erd\u0151s P.","year":"1971"},{"key":"e_1_2_11_11_1","doi-asserted-by":"crossref","first-page":"27","DOI":"10.37236\/845","article-title":"On the chromatic number of simple triangle\u2010free triple systems","volume":"15","author":"Frieze A.","year":"2008","journal-title":"Electron J Combin"},{"key":"e_1_2_11_12_1","unstructured":"A.FriezeandD.Mubayi Coloring simple hypergraphs (submitted for publication)."},{"key":"e_1_2_11_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404019"},{"key":"e_1_2_11_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2008.01.008"},{"key":"e_1_2_11_15_1","doi-asserted-by":"publisher","DOI":"10.2307\/2045427"},{"key":"e_1_2_11_16_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548305006905"},{"key":"e_1_2_11_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240070302"},{"key":"e_1_2_11_18_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-25.1.13"},{"key":"e_1_2_11_19_1","first-page":"195","volume-title":"Algorithms Combin","author":"McDiarmid C.","year":"1998"},{"key":"e_1_2_11_20_1","first-page":"167","article-title":"Steiner triple systems with minimum independence number","volume":"21","author":"Phelps K.","year":"1986","journal-title":"Ars Combin"},{"key":"e_1_2_11_21_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240050117"},{"key":"e_1_2_11_22_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240070305"}],"container-title":["Random Structures &amp; Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.20453","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.20453","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.20453","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,3]],"date-time":"2023-10-03T22:20:26Z","timestamp":1696371626000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/rsa.20453"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,8,2]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,3]]}},"alternative-id":["10.1002\/rsa.20453"],"URL":"https:\/\/doi.org\/10.1002\/rsa.20453","archive":["Portico"],"relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"value":"1042-9832","type":"print"},{"value":"1098-2418","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,8,2]]}}}