An extremal theorem in the hypercube

MaRDI QIDQ986719zbMATH OpenFDO

Authors David Conlon

Publication date 12 August 2010

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1005.0582, https://eudml.org/doc/233597, http://www.emis.de/journals/EJC/Volume_17/Abstracts/v17i1r111.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Extremal combinatorics (05D99)

Abstract: The hypercube Q_n is the graph whose vertex set is {0,1}^n and where two vertices are adjacent if they differ in exactly one coordinate. For any subgraph H of the cube, let ex(Q_n, H) be the maximum number of edges in a subgraph of Q_n which does not contain a copy of H. We find a wide class of subgraphs H, including all previously known examples, for which ex(Q_n, H) = o(e(Q_n)). In particular, our method gives a unified approach to proving that ex(Q_n, C_{2t}) = o(e(Q_n)) for all t >= 4 other than 5.

Recommendations

• Generalized Turán densities in the hypercube
• Some Turán type results on the hypercube
• A note on short cycles in a hypercube
• Subgraphs of a hypercube containing no small even cycles
• scientific article; zbMATH DE number 3845613

Cited in

(41)

• Bounding the size of square-free subgraphs of the hypercube
• Bulky subgraphs of the hypercube
• A characterization of cube-hypergraphs
• Maximum density of vertex-induced perfect cycles and paths in the hypercube
• Triangle-free subgraphs of hypergraphs
• The vertex Turán density in 3-ary \(n\)-cubes
• Generalized Turán densities in the hypercube
• On even-cycle-free subgraphs of the doubled Johnson graphs
• Extremal even-cycle-free subgraphs of the complete transposition graphs
• On crown-free families of subsets
• A note on short cycles in a hypercube
• Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube
• Vertex Turán problems for the oriented hypercube
• On a theorem of Erdős and Simonovits on graphs not containing the cube
• scientific article; zbMATH DE number 434690 (Why is no real title available?)
• Subcubes of hypercubes
• Minimum critical squarefree subgraph of a hypercube
• scientific article; zbMATH DE number 19183 (Why is no real title available?)
• Subgraphs of a hypercube containing no small even cycles
• scientific article; zbMATH DE number 125454 (Why is no real title available?)
• On $r$-extendability of the hypercube $Q\sb n$
• On the maximum number of edges in a c₄‐free subgraph of q_n
• New Tricks for Old Trees: Maps and the Pigeonhole Principle
• scientific article; zbMATH DE number 2170330 (Why is no real title available?)
• Turán problems on non-uniform hypergraphs
• On a covering problem in the hypercube
• On quadrilaterals in layers of the cube and extremal problems for directed and oriented graphs
• 2-Factors without close edges in the n-dimensional cube
• Relative Turán problems for uniform hypergraphs
• Saturated subgraphs of the hypercube
• Saturation in the hypercube and bootstrap percolation
• Packing the hypercube
• On even-cycle-free subgraphs of the hypercube
• Extremal numbers for cycles in a hypercube
• Uniform Turán density of cycles
• Pairing strategies for the maker-breaker game on the hypercube with subcubes as winning sets
• Inducibility in the hypercube
• A class of graphs of zero Turán density in a hypercube
• Layered subgraphs of the hypercube
• On graphs embeddable in a layer of a hypercube and their extremal numbers
• \(C_{10}\) has positive Turán density in the hypercube

This page was built for publication: An extremal theorem in the hypercube

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q986719)