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

(37)

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

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)