{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T15:08:16Z","timestamp":1648566496292},"reference-count":8,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2020,8,7]],"date-time":"2020-08-07T00:00:00Z","timestamp":1596758400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2020,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A well-known observation of Lov\u00e1sz is that if a hypergraph is not 2-colourable, then at least one pair of its edges intersect at a single vertex. In this short paper we consider the quantitative version of Lov\u00e1sz\u2019s criterion. That is, we ask how many pairs of edges intersecting at a single vertex should belong to a non-2-colourable <jats:italic>n<\/jats:italic>-uniform hypergraph. Our main result is an <jats:italic>exact<\/jats:italic> answer to this question, which further characterizes all the extremal hypergraphs. The proof combines Bollob\u00e1s\u2019s two families theorem with Pluhar\u2019s randomized colouring algorithm.<\/jats:p>","DOI":"10.1017\/s0963548320000334","type":"journal-article","created":{"date-parts":[[2020,8,7]],"date-time":"2020-08-07T05:41:30Z","timestamp":1596778890000},"page":"956-960","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["A quantitative Lov\u00e1sz criterion for Property B"],"prefix":"10.1017","volume":"29","author":[{"given":"Asaf","family":"Ferber","sequence":"first","affiliation":[]},{"given":"Asaf","family":"Shapira","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2020,8,7]]},"reference":[{"key":"S0963548320000334_ref2","first-page":"325","article-title":"Zur Theorie der trigonometrische Reihen","volume":"60","author":"Bernstein","year":"1908","journal-title":"Leipz. Ber."},{"key":"S0963548320000334_ref4","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20556"},{"key":"S0963548320000334_ref1","volume-title":"The Probabilistic Method","author":"Alon","year":"1992"},{"key":"S0963548320000334_ref8","doi-asserted-by":"publisher","DOI":"10.1093\/qmath\/25.1.303"},{"key":"S0963548320000334_ref6","first-page":"31","article-title":"On a property of families of sets","volume":"30","author":"Miller","year":"1937","journal-title":"Comput. Rend. Varsovie"},{"key":"S0963548320000334_ref5","volume-title":"Combinatorial Problems and Exercises","author":"Lov\u00e1sz","year":"1979"},{"key":"S0963548320000334_ref7","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20267"},{"key":"S0963548320000334_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/BF01904851"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548320000334","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,11]],"date-time":"2020-11-11T12:43:20Z","timestamp":1605098600000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548320000334\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,7]]},"references-count":8,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,11]]}},"alternative-id":["S0963548320000334"],"URL":"https:\/\/doi.org\/10.1017\/s0963548320000334","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,7]]},"assertion":[{"value":"\u00a9 The Author(s), 2020. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}