{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,4]],"date-time":"2025-06-04T04:30:53Z","timestamp":1749011453279},"reference-count":18,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2024,3,5]],"date-time":"2024-03-05T00:00:00Z","timestamp":1709596800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2024,5]]},"abstract":"Abstract<\/jats:title>For a graph \n$H$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and a hypercube \n$Q_n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, \n$\\textrm{ex}(Q_n, H)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is the largest number of edges in an \n$H$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-free subgraph of \n$Q_n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. If \n$\\lim _{n \\rightarrow \\infty } \\textrm{ex}(Q_n, H)\/|E(Q_n)| \\gt 0$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, \n$H$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is said to have a positive Tur\u00e1n density in a hypercube or simply a positive Tur\u00e1n density; otherwise, it has zero Tur\u00e1n density. Determining \n$\\textrm{ex}(Q_n, H)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and even identifying whether \n$H$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> has a positive or zero Tur\u00e1n density remains a widely open question for general \n$H$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. By relating extremal numbers in a hypercube and certain corresponding hypergraphs, Conlon found a large class of graphs, ones having so-called partite representation, that have zero Tur\u00e1n density. He asked whether this gives a characterisation, that is, whether a graph has zero Tur\u00e1n density if and only if it has partite representation. Here, we show that, as suspected by Conlon, this is not the case. We give an example of a class of graphs which have no partite representation, but on the other hand, have zero Tur\u00e1n density. In addition, we show that any graph whose every block has partite representation has zero Tur\u00e1n density in a hypercube.<\/jats:p>","DOI":"10.1017\/s0963548324000063","type":"journal-article","created":{"date-parts":[[2024,3,5]],"date-time":"2024-03-05T07:15:56Z","timestamp":1709622956000},"page":"404-410","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":2,"title":["A class of graphs of zero Tur\u00e1n density in a hypercube"],"prefix":"10.1017","volume":"33","author":[{"given":"Maria","family":"Axenovich","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2024,3,5]]},"reference":[{"key":"S0963548324000063_ref5","unstructured":"[5] Baber, R. (2012) Tur\u00e1n densities of hypercubes. Arxiv preprint 2012, arXiv:\u00a01201.3587."},{"key":"S0963548324000063_ref12","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1016\/j.endm.2009.07.085","article-title":"On even-cycle-free subgraphs of the hypercube","volume":"34","author":"F\u00fcredi","year":"2009","journal-title":"Electron. Notes Discrete Math."},{"key":"S0963548324000063_ref6","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.ejc.2013.06.003","article-title":"Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube","volume":"35","author":"Balogh","year":"2014","journal-title":"Eur. J. Comb."},{"key":"S0963548324000063_ref7","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1002\/jgt.3190190104","article-title":"On the maximum number of edges in a \n\n\n\n$C_4$\n\n\n-free subgraph of \n\n\n\n$Q_n$","volume":"19","author":"Brass","year":"1995","journal-title":"J. Graph Theory"},{"key":"S0963548324000063_ref18","unstructured":"[18] Tomon, I. Robust (rainbow) subdivisions and simplicial cycles. Adv. Comb. ArXiv preprint 2022: arXiv:\u00a02201.12309."},{"key":"S0963548324000063_ref11","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1007\/BF02759942","article-title":"On extremal problems of graphs and generalized graphs","volume":"2","author":"Erd\u0151s","year":"1964","journal-title":"Israel J. Math."},{"key":"S0963548324000063_ref10","article-title":"An extremal theorem in the hypercube","volume":"17","author":"Conlon","year":"2010","journal-title":"Electron. J. Comb."},{"key":"S0963548324000063_ref16","doi-asserted-by":"crossref","first-page":"2905","DOI":"10.1016\/j.disc.2008.07.025","article-title":"Some Tur\u00e1n type results on the hypercube","volume":"309","author":"Offner","year":"2009","journal-title":"Discrete Math."},{"key":"S0963548324000063_ref1","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1137\/060649422","article-title":"Tur\u00e1n\u2019s theorem in the hypercube","volume":"21","author":"Alon","year":"2007","journal-title":"SIAM J. Discrete Math."},{"key":"S0963548324000063_ref8","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1002\/jgt.3190160311","article-title":"Subgraphs of a hypercube containing no small even cycles","volume":"16","author":"Chung","year":"1992","journal-title":"J. Graph Theory"},{"key":"S0963548324000063_ref15","unstructured":"[15] Marquardt, F. (2022) On the characterization of graphs with zero Tur\u00e1n density in the hypercube, Master thesis. Karlsruhe Institute of Technology."},{"key":"S0963548324000063_ref13","doi-asserted-by":"crossref","first-page":"1816","DOI":"10.1016\/j.jcta.2011.02.009","article-title":"On even-cycle-free subgraphs of the hypercube","volume":"118","author":"F\u00fcredi","year":"2011","journal-title":"J. Comb. Theory Ser. A"},{"key":"S0963548324000063_ref3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.dam.2023.07.021","article-title":"Extremal numbers for cycles in a hypercube","volume":"341","author":"Axenovich","year":"2023","journal-title":"Discrete Appl. Math."},{"key":"S0963548324000063_ref2","unstructured":"[2] Axenovich, M. , Martin, R. and Winter, C. (2023) On graphs embeddable in a layer of a hypercube and their extremal numbers. ArXiv preprint 2023: arXiv:\u00a02303.15529."},{"key":"S0963548324000063_ref17","doi-asserted-by":"crossref","first-page":"1730","DOI":"10.1016\/j.disc.2008.02.015","article-title":"Bounding the size of square-free subgraphs of the hypercube","volume":"309","author":"Thomason","year":"2009","journal-title":"Discrete Math."},{"key":"S0963548324000063_ref14","doi-asserted-by":"crossref","first-page":"338","DOI":"10.21136\/CMJ.1972.101102","article-title":"B-valuations of graphs","volume":"22","author":"Havel","year":"1972","journal-title":"Czechoslovak Math. J."},{"key":"S0963548324000063_ref9","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1002\/jgt.3190170405","article-title":"Hexagon-free subgraphs of hypercubes","volume":"17","author":"Conder","year":"1993","journal-title":"J. Graph Theory"},{"key":"S0963548324000063_ref4","unstructured":"[4] Axenovich, M. , Manske, J. and Martin, R. (2011) Extremal functions for $Q_2$ in a Boolean lattice, Order. Online First."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548324000063","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,5]],"date-time":"2024-04-05T10:18:37Z","timestamp":1712312317000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548324000063\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,5]]},"references-count":18,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,5]]}},"alternative-id":["S0963548324000063"],"URL":"https:\/\/doi.org\/10.1017\/s0963548324000063","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,5]]},"assertion":[{"value":"\u00a9 The Author(s), 2024. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (https:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}