Extremal numbers for cycles in a hypercube

2022/11/23 by Maria Axenovich, Axenovich, Maria · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2211.12842

openalex publication_date 2022/11/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let ex(Q_n, H) be the largest number of edges in a subgraph G of a hypercube Q_n such that there is no subgraph of G isomorphic to H. We show that for any integer k≥ 3, ex(Q_n, C_4k+2)= O(n^{(5)/(6) + (1)/(3(2k-2))} 2ⁿ).

Cited by

• Ramsey problems for graphs in Euclidean spaces and Cartesian powers

Related

• An extremal theorem in the hypercube
• Generalized Turán densities in the hypercube
• Cycles in enhanced hypercubes
• On extremal numbers of the triangle plus the four-cycle
• A Generalization of the Methods of Brass, Harboth, and Nieborg