A note on short cycles in a hypercube

DOI10.1016/J.DISC.2006.05.008MaRDI QIDQ2509296zbMATH OpenOpenAlexFDO

Authors Ryan R. Martin, Maria Axenovich

Publication date 19 October 2006

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1605.06572

zbMATH Keywords

Ramsey property

Mathematics Subject Classification ID

Paths and cycles (05C38) Generalized Ramsey theory (05C55)

Abstract: How many edges can a quadrilateral-free subgraph of a hypercube have? This question was raised by Paul ErdH{o}s about $27$ years ago. His conjecture that such a subgraph asymptotically has at most half the edges of a hypercube is still unresolved. Let $f(n,C_l)$ be the largest number of edges in a subgraph of a hypercube $Q_n$ containing no cycle of length $l$. It is known that $f(n,C_l)=o(|E(Q_n)|)$, when $l=4k$, $kgeq2$ and that $f(n,C_6)geqfrac13|E(Q_n)|$. It is an open question to determine $f(n,C_l)$ for $l=4k+2$, $kgeq2$. Here, we give a general upper bound for $f(n,C_l)$ when $l=4k+2$ and provide a coloring of $E(Q_n)$ by $4$ colors containing no induced monochromatic $C_{10}$.

Review text

The graph \(Q_n\) (called hypercube of dimension \(n\)) is defined as follows: The set of vertices of \(Q_n\) consists of subsets of \(\{1,\dots,n\}\), and the set of edges \(E(Q_n)\) corresponds to pairs of sets with symmetric difference of size \(1\). Let \(f(n,C_l)\) be the largest number of edges in a subgraph of \(Q_n\) with no cycle of length \(l\). It is known for example that \(f(n,C_4)\leq 0.623\cdot | E(Q_n)| \). The authors provide a general upper bound for \(f(n,C_l)\) when \(l=4k+2\) as well as a coloring of \(E(Q_n)\) by four colors containing no induced monochromatic \(C_{10}\).

Recommendations

• An extremal theorem in the hypercube
• Largest induced subgraphs of the n-cube that contain no 4-cycles
• Subgraphs of a hypercube containing no small even cycles
• A remark on rainbow 6-cycles in hypercubes
• Rainbows in the hypercube

Cites work

• A Ramsey-type result for the hypercube
• Cycles of even length in graphs
• Hexagon-free subgraphs of hypercubes
• scientific article; zbMATH DE number 2123255 (Why is no real title available?)
• On arithmetic progressions of cycle lengths in graphs
• Subgraphs of a hypercube containing no small even cycles

Cited in

(23)

• Some Turán type results on the hypercube
• Maximum density of vertex-induced perfect cycles and paths in the hypercube
• Bounding the size of the subgraph induced by \(m\) vertices and extra edge-connectivity of hypercubes
• Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube
• A note about shortest cycle covers
• How many triangles and quadrilaterals are there in an \(n\)-dimensional augmented cube?
• scientific article; zbMATH DE number 4177100 (Why is no real title available?)
• scientific article; zbMATH DE number 3880754 (Why is no real title available?)
• On 14-Cycle-Free Subgraphs of the Hypercube
• scientific article; zbMATH DE number 4029610 (Why is no real title available?)
• Subgraphs of a hypercube containing no small even cycles
• scientific article; zbMATH DE number 2170330 (Why is no real title available?)
• Component edge connectivity of hypercubes
• Largest induced subgraphs of the n-cube that contain no 4-cycles
• On even-cycle-free subgraphs of the hypercube
• On even-cycle-free subgraphs of the hypercube
• Extremal numbers for cycles in a hypercube
• Pairing strategies for the maker-breaker game on the hypercube with subcubes as winning sets
• Inducibility in the hypercube
• On graphs embeddable in a layer of a hypercube and their extremal numbers
• Highly symmetric subgraphs of hypercubes
• \(C_{10}\) has positive Turán density in the hypercube
• An extremal theorem in the hypercube

This page was built for publication: A note on short cycles in a hypercube

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