{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,2,15]],"date-time":"2023-02-15T09:16:12Z","timestamp":1676452572272},"reference-count":20,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2012,10,3]],"date-time":"2012-10-03T00:00:00Z","timestamp":1349222400000},"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,1]]},"abstract":"<jats:p>The discrete cube {0, 1}<jats:sup><jats:italic>d<\/jats:italic><\/jats:sup> is a fundamental combinatorial structure. A subcube of {0, 1}<jats:sup><jats:italic>d<\/jats:italic><\/jats:sup> is a subset of 2<jats:italic><jats:sup>k<\/jats:sup><\/jats:italic> of its points formed by fixing <jats:italic>k<\/jats:italic> coordinates and allowing the remaining <jats:italic>d<\/jats:italic> \u2212 <jats:italic>k<\/jats:italic> to vary freely. This paper is concerned with patterns of intersections among subcubes of the discrete cube. Two sample questions along these lines are as follows: given a family of subcubes in which no <jats:italic>r<\/jats:italic> + 1 of them have non-empty intersection, how many pairwise intersections can we have? How many subcubes can we have if among them there are no <jats:italic>k<\/jats:italic> which have non-empty intersection and no <jats:italic>l<\/jats:italic> which are pairwise disjoint?<\/jats:p><jats:p>These questions are naturally expressed using intersection graphs. The intersection graph of a family of sets has one vertex for each set in the family with two vertices being adjacent if the corresponding subsets intersect. 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=\"S0963548312000429_inline1\" \/><jats:tex-math>$\\I(n,d)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> be the set of all <jats:italic>n<\/jats:italic> vertex graphs which can be represented as the intersection graphs of subcubes in {0, 1}<jats:sup><jats:italic>d<\/jats:italic><\/jats:sup>. With this notation our first question above asks for the largest number of edges in a <jats:italic>K<\/jats:italic><jats:sub><jats:italic>r<\/jats:italic>+1<\/jats:sub>-free graph in <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548312000429_inline1\" \/><jats:tex-math>$\\I(n,d)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. As such it is a Tur\u00e1n-type problem. We answer this question asymptotically for some ranges of <jats:italic>r<\/jats:italic> and <jats:italic>d<\/jats:italic>. More precisely we show that if <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548312000429_inline2\" \/><jats:tex-math>$(k+1)2^{\\lfloor\\frac{d}{k+1}\\rfloor}&lt;n\\leq k2^{\\lfloor\\frac{d}{k}\\rfloor}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> for some integer <jats:italic>k<\/jats:italic> \u2265 2 then the maximum edge density is <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548312000429_inline3\" \/><jats:tex-math>$\\bigl(1-\\frac{1}{k}-o(1)\\bigr)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> provided that <jats:italic>n<\/jats:italic> is not too close to the lower limit of the range.<\/jats:p><jats:p>The second question can be thought of as a Ramsey-type problem. The maximum such <jats:italic>n<\/jats:italic> can be defined in the same way as the usual Ramsey number but only considering graphs which are in <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548312000429_inline1\" \/><jats:tex-math>$\\I(n,d)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. We give bounds for this maximum <jats:italic>n<\/jats:italic> mainly concentrating on the case that <jats:italic>l<\/jats:italic> is fixed, and make some comparisons with the usual Ramsey number.<\/jats:p>","DOI":"10.1017\/s0963548312000429","type":"journal-article","created":{"date-parts":[[2012,10,3]],"date-time":"2012-10-03T12:05:18Z","timestamp":1349265918000},"page":"55-70","source":"Crossref","is-referenced-by-count":1,"title":["Tur\u00e1n and Ramsey Properties of Subcube Intersection Graphs"],"prefix":"10.1017","volume":"22","author":[{"given":"J. ROBERT","family":"JOHNSON","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"KLAS","family":"MARKSTR\u00d6M","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2012,10,3]]},"reference":[{"key":"S0963548312000429_ref5","volume-title":"Latin Squares and their Applications","author":"D\u00e9nes","year":"1974"},{"key":"S0963548312000429_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(80)90030-8"},{"key":"S0963548312000429_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/s00222-010-0247-x"},{"key":"S0963548312000429_ref12","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548398003459"},{"key":"S0963548312000429_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579292"},{"key":"S0963548312000429_ref7","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1966-014-3"},{"key":"S0963548312000429_ref19","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(77)90044-9"},{"key":"S0963548312000429_ref16","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548308009085"},{"key":"S0963548312000429_ref13","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240070302"},{"key":"S0963548312000429_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0619-4"},{"key":"S0963548312000429_ref2","doi-asserted-by":"publisher","DOI":"10.4169\/000298910x474961"},{"key":"S0963548312000429_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/BF02783298"},{"key":"S0963548312000429_ref9","volume-title":"Ramsey Theory","author":"Graham","year":"1990"},{"key":"S0963548312000429_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2008.09.036"},{"key":"S0963548312000429_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/BF02761162"},{"key":"S0963548312000429_ref15","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-2010-05189-X"},{"key":"S0963548312000429_ref14","doi-asserted-by":"crossref","unstructured":"McKee T. A. and McMorris F. R. (1999) Topics in Intersection Graph Theory, SIAM Monographs on Discrete Mathematics and Applications.","DOI":"10.1137\/1.9780898719802"},{"key":"S0963548312000429_ref17","first-page":"301","volume-title":"Recent Progress in Combinatorics: Proc. Third Waterloo Conference on Combinatorics","author":"Roberts","year":"1968"},{"key":"S0963548312000429_ref18","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(85)80023-8"},{"key":"S0963548312000429_ref20","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579163"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548312000429","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,24]],"date-time":"2019-04-24T20:06:07Z","timestamp":1556136367000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548312000429\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,10,3]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["S0963548312000429"],"URL":"https:\/\/doi.org\/10.1017\/s0963548312000429","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,10,3]]}}}