Skip to content
Preprint

On the Tur\'an Density of $C_{10}$ in the Hypercube

Aug 2026 · 0 citations · 13 references
Mathematics

Abstract

The $n$-dimensional hypercube $Q_n$ is the graph with vertex set $\{0,1\}^n$ in which two vertices are adjacent if they differ in exactly one coordinate. For a graph $H$, let $\operatorname{ex}(Q_n,H)$ be the maximum number of edges in an $H$-free subgraph of $Q_n$. The hypercube Tur\'an density of $H$ is defined by $\pi_{\square}(H)=\lim_{n\rightarrow\infty}\operatorname{ex}(Q_n,H)/|E(Q_n)|$. In this note, we prove \[ \frac{1}{8} \leq \pi_{\square}(C_{10}) \leq 0.36577. \] For the upper bound, we prove $\pi_{\square}(C_{10}) \leq \pi_{\square}(C_6)$, which, together with a result of Baber, gives the stated upper bound. For the lower bound, we prove that $\operatorname{ex}(Q_n,C_{10})>|E(Q_n)|/8$ for every $n \geq 2$.

View source

Similar papers

Preprint Aug 2026

On high-girth layered graphs of positive Tur\'an density in a hypercube

For a graph $H$, let $\operatorname{ex}(Q_n, H)$ be the largest number of edges in a subgraph of the hypercube $Q_n$ of dimension $n$ that contains no subgraph isomorphic to $H$. The Tur\'an density of $H$ in a hypercube, denoted $\pi_\square(H)$, is defined as $\lim_{n\rightarrow \infty} \operatorname{ex}(Q_n, H)/|E(Q...

M. Axenovich, Marko Pejić · 0 citations
Preprint Aug 2026

The exact Tur\'{a}n number of the even wheel $W_{2k+2}$ among non-$3$-partite graphs

Let $\mathrm{ex}(n,H)$ denote the Tur\'{a}n number of $H$. A graph is color-critical if there exists an edge $e\in E(H)$ such that $\chi(H-e)<\chi(H)$. For a color-critical graph $H$ with $\chi(H)=r+1$, Simonovits'chromatic critical edge theorem implies that there exists an $n_0(H)$ such that $\mathrm{ex}(n,H)=e(T_{n,r...

Qi-Xuan Yuan, Rui-Fang Liu, Sanming Zhou · 0 citations
Preprint Sep 2026

Tur\'an problems with bounded matching number in $k$-uniform hypergraphs

For a family $\mathcal{F}$ of $k$-graphs, $\ex_k(n,\mathcal{F})$ denotes the maximum number of edges in an $n$-vertex $\mathcal{F}$-free $k$-graph. Let $M_{s+1}^k$ denote a matching of size $s+1$ in $k$-uniform hypergraphs. Recently, Alon and Frankl (JCTB, 2024) determined $\ex_2(n,\{M_{s+1}^2,K_{\ell+1}\})$ for all $n...

Jia-Lin Liu, Ming-Yang Guo, Xiu-Mei Wang · 0 citations
Preprint Sep 2026

On the Exact Tur\'an Number of $F^-_{4,3}$

For a $3$-graph $F$, the Tur\'an number of $F$, denoted by $\ex(n,F)$, is the maximum number of edges in a $3$-graph on $n$ vertices containing no subgraph isomorphic to $F$. Let $F^-_{4,3}$ be the $3$-graph formed by a complete four-vertex core and three outer vertices, with all but one of the twelve triples containin...

Chun-Qiu Fang · 0 citations
Preprint Aug 2026

Large Cliques and Clique Spectral Radius in the Erd\H{o}s--S\'{o}s Problem

For graphs $H$ and $F$, let $ex(n,H,F)$ be the maximum number of copies of $H$ in an $n$-vertex $F$-free graph. We study this problem when $H$ is a clique and $F=T_t$which is a fixed tree on $t$ vertices. The Erd\H{o}s--S\'{o}s conjecture concerns the value of $ex(n,K_2, T_t)$. Gerbner and Palmer proposed a more genera...

Xiaojun Zhao, Yue-jian Peng · 2 citations · ⚡2
Preprint Sep 2026

A Tur\'an-type extremal problem for the number of spanning trees in $C_4$-free graphs

For a graph \(F\), the Tur\'an number \(\ex(n,F)\) is the maximum number of edges in an \(F\)-free graph on \(n\) vertices. Let \(q\ge 2\) be an integer and set \(n=q^{2}+q+1\). Brown and Erd\H{o}s, R\'enyi and S\'os independently proved that $\ex(n,C_{4})\ge \frac12 q(q+1)^{2}$ for every prime power \(q\), and F\"ured...

Shao-Han Xu, Feng-Ming Dong, Ke-Xiang Xu · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.