{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,23]],"date-time":"2026-02-23T15:53:14Z","timestamp":1771861994906,"version":"3.50.1"},"reference-count":40,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2015,3,6]],"date-time":"2015-03-06T00:00:00Z","timestamp":1425600000000},"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":[[2016,3]]},"abstract":"<jats:p>Let <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548315000061_inline1\"\/><jats:tex-math>$\\mathcal{F}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> be a family of <jats:italic>r<\/jats:italic>-uniform hypergraphs. The <jats:italic>chromatic threshold<\/jats:italic> of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548315000061_inline1\"\/><jats:tex-math>$\\mathcal{F}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is the infimum of all non-negative reals <jats:italic>c<\/jats:italic> such that the subfamily of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548315000061_inline1\"\/><jats:tex-math>$\\mathcal{F}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> comprising hypergraphs <jats:italic>H<\/jats:italic> with minimum degree at least <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548315000061_inline2\"\/><jats:tex-math>$c \\binom{| V(H) |}{r-1}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> has bounded chromatic number. This parameter has a long history for graphs (<jats:italic>r<\/jats:italic> = 2), and in this paper we begin its systematic study for hypergraphs.<\/jats:p><jats:p>\u0141uczak and Thomass\u00e9 recently proved that the chromatic threshold of the so-called near bipartite graphs is zero, and our main contribution is to generalize this result to <jats:italic>r<\/jats:italic>-uniform hypergraphs. For this class of hypergraphs, we also show that the exact Tur\u00e1n number is achieved uniquely by the complete (<jats:italic>r<\/jats:italic> + 1)-partite hypergraph with nearly equal part sizes. This is one of very few infinite families of non-degenerate hypergraphs whose Tur\u00e1n number is determined exactly. In an attempt to generalize Thomassen's result that the chromatic threshold of triangle-free graphs is 1\/3, we prove bounds for the chromatic threshold of the family of 3-uniform hypergraphs not containing {<jats:italic>abc, abd, cde<\/jats:italic>}, the so-called generalized triangle.<\/jats:p><jats:p>In order to prove upper bounds we introduce the concept of <jats:italic>fibre bundles<\/jats:italic>, which can be thought of as a hypergraph analogue of directed graphs. This leads to the notion of <jats:italic>fibre bundle dimension<\/jats:italic>, a structural property of fibre bundles that is based on the idea of Vapnik\u2013Chervonenkis dimension in hypergraphs. Our lower bounds follow from explicit constructions, many of which use a hypergraph analogue of the Kneser graph. Using methods from extremal set theory, we prove that these Kneser hypergraphs have unbounded chromatic number. This generalizes a result of Szemer\u00e9di for graphs and might be of independent interest. Many open problems remain.<\/jats:p>","DOI":"10.1017\/s0963548315000061","type":"journal-article","created":{"date-parts":[[2015,3,6]],"date-time":"2015-03-06T05:36:44Z","timestamp":1425620204000},"page":"172-212","source":"Crossref","is-referenced-by-count":2,"title":["On the Chromatic Thresholds of Hypergraphs"],"prefix":"10.1017","volume":"25","author":[{"given":"J\u00d3ZSEF","family":"BALOGH","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JANE","family":"BUTTERFIELD","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"PING","family":"HU","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JOHN","family":"LENZ","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"DHRUV","family":"MUBAYI","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2015,3,6]]},"reference":[{"key":"S0963548315000061_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579190"},{"key":"S0963548315000061_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579292"},{"key":"S0963548315000061_ref40","doi-asserted-by":"publisher","DOI":"10.1007\/s002220100188"},{"key":"S0963548315000061_ref30","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2012.09.005"},{"key":"S0963548315000061_ref4","unstructured":"Balogh J. and Lenz J. Hypergraphs with zero chromatic threshold. Submitted."},{"key":"S0963548315000061_ref18","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20249"},{"key":"S0963548315000061_ref16","unstructured":"Goldwasser J. On the Tur\u00e1n number of {123, 124, 345}. Manuscript."},{"key":"S0963548315000061_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2012.11.016"},{"key":"S0963548315000061_ref38","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-007-0054-1"},{"key":"S0963548315000061_ref3","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(74)90133-2"},{"key":"S0963548315000061_ref17","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2007.166.897"},{"key":"S0963548315000061_ref12","first-page":"287","article-title":"Weighted multiply intersecting families.","volume":"40","author":"Frankl","year":"2003","journal-title":"Studia Sci. Math. Hungar."},{"key":"S0963548315000061_ref9","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1946-08715-7"},{"key":"S0963548315000061_ref25","unstructured":"\u0141uczak T. and Thomass\u00e9 S. Coloring dense graphs via VC-dimension. Submitted."},{"key":"S0963548315000061_ref13","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548305006905"},{"key":"S0963548315000061_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(89)90067-8"},{"key":"S0963548315000061_ref36","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2005.11.006"},{"key":"S0963548315000061_ref39","first-page":"42","article-title":"Theory of uniform convergence of frequencies of events to their probabilities and problems of search for an optimal solution from empirical data","author":"Vapnik","year":"1971","journal-title":"Avtomat. i Telemeh."},{"key":"S0963548315000061_ref19","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139004114.004"},{"key":"S0963548315000061_ref37","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-002-0009-5"},{"key":"S0963548315000061_ref26","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2005.06.001"},{"key":"S0963548315000061_ref28","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20117"},{"key":"S0963548315000061_ref21","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-005-0034-2"},{"key":"S0963548315000061_ref6","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1999.1938"},{"key":"S0963548315000061_ref15","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20505"},{"key":"S0963548315000061_ref35","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(74)90044-2"},{"key":"S0963548315000061_ref24","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-006-0028-8"},{"key":"S0963548315000061_ref22","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(66)80012-1"},{"key":"S0963548315000061_ref20","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2004.05.003"},{"key":"S0963548315000061_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(73)90126-X"},{"key":"S0963548315000061_ref14","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548305006784"},{"key":"S0963548315000061_ref27","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2005.06.013"},{"key":"S0963548315000061_ref31","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20017"},{"key":"S0963548315000061_ref5","unstructured":"Brandt S. and Thomass\u00e9 S. Dense triangle-free graphs are four colorable: A solution to the Erd\u0151s-Simonovits problem. J. Combin. Theory Ser. B, to appear."},{"key":"S0963548315000061_ref33","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90029-Y"},{"key":"S0963548315000061_ref34","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(72)90019-2"},{"key":"S0963548315000061_ref23","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2006.02.003"},{"key":"S0963548315000061_ref29","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-008-2187-2"},{"key":"S0963548315000061_ref32","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20108"},{"key":"S0963548315000061_ref2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1986-0857448-8"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548315000061","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,19]],"date-time":"2019-04-19T20:51:24Z","timestamp":1555707084000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548315000061\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,3,6]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,3]]}},"alternative-id":["S0963548315000061"],"URL":"https:\/\/doi.org\/10.1017\/s0963548315000061","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,3,6]]}}}