Skip to content
Preprint

Codegree-Constrained Tur\'an Problems for $F_5$ and Its Blow-ups

Oct 2026 · 0 citations · 10 references
Mathematics

Abstract

Let $F_5$ denote the $3$-uniform hypergraph with edge set $\{abc,abd,cde\}$. For a hypergraph property $\mathcal P$, let $ex_{\mathcal P}(n,F_5)$ be the maximum number of edges in an $n$-vertex $F_5$-free $3$-uniform hypergraph satisfying $\mathcal P$. Let $\Delta_2(H)$ denote the maximum codegree of a pair of vertices in a $3$-uniform hypergraph $H$. We determine the exact value of $ex_{\Delta_2\ge m}(n,F_5)$ when $m$ is bounded away from $n/3$ by a fixed positive proportion. More precisely, for every constant $c\in (1/3,1)$, there exists $n_0$ such that for all $n\ge n_0$ and $m=cn$, \[ ex_{\Delta_2\ge m}(n,F_5) = m\left\lceil\frac{n-m}{2}\right\rceil \left\lfloor\frac{n-m}{2}\right\rfloor. \] The unique extremal hypergraph is the complete tripartite $3$-graph $K^3_{m,\lceil (n-m)/2\rceil,\lfloor (n-m)/2\rfloor}$. We also prove the corresponding exact result for the blow-ups $F_5^t$, together with stability theorems showing that every near-extremal configuration is close to the relevant tripartite construction.

View source

Similar papers

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\g...

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

NP-hardness of additive approximation for generalized Tur\'{a}n problems

Given a graph $T$ and a nonempty family $\mathcal{F}$ of graphs, let $\operatorname{ex}(G, T, \mathcal{F})$ denote the maximum number of copies of $T$ in an $\mathcal{F}$-free subgraph of a host graph $G$. Alon and Shikhelman [Algorithmica, 2022] conjectured that if $e(T)>0$ and no member of $\mathcal{F}$ is a subgraph...

Yi-Han Chen, Jia-Lin He, Xi-He Li et al. · 1 citation · ⚡1
Preprint Oct 2026

NP-Hardness of Generalized-Tur\'an Graph Modification Problems

The Alon-Shikhelman conjecture for finite families $\mathcal{H}$ is proved and an elementary proof of the Alon-Shapira-Sudakov result when $\mathcal{H}$ is finite is obtained.

Lior Gishboliner, Yevgeny Levanzov, A. Shapira · 1 citation
Preprint Oct 2026

Degree-square Tur\'an problem for two self-converse tournaments

For a fixed digraph $F$, let $\operatorname{ex}_2^+(n,F)$ be the maximum of $\sum_{v\in V(D)}d_D^+(v)^2$ over all $n$-vertex $F$-free digraphs. Ai et al. [arXiv:2606.03520, 2026] asked for which self-converse tournament $F$ one can determine $\operatorname{ex}_2^+(n,F)$. Let $TT_r$ denote a transitive tournament on $r$...

Zhuo-Ran Han, Yao-Jun Chen · 0 citations
Preprint Aug 2026

Forbidding $r$-extension of $C_4$ -- a counterexample of the Anstee-Sali conjecture

In this note we prove $\mathrm{forb}(n,\mathbf{1}_{r-2}\times C_4)=\Theta(n^{r-1/2})$, thus providing a series of counterexamples of a 2005 conjecture of the first two authors. Here $\mathbf{1}_{r-2}\times C_4$ is the $r$-extension of the 4-cycle, that is the $r$-uniform hypergraph of four edges obtained by joining a s...

R. Anstee, A. Sali, Pei Wu · 0 citations
Preprint Oct 2026

Tur\'an Numbers of Linear Stars and Expanded Trees

For an $r$-uniform hypergraph $\mathcal H$, let $\ex_r(n,\mathcal H)$ denote the maximum number of edges in an $n$-vertex $r$-uniform hypergraph containing no copy of $\mathcal H$. The $r$-uniform expansion $T^{(r)}$ of a tree $T$ is obtained by adding $r-2$ new vertices to each edge, with the added sets pairwise disjo...

Xin-Min Hou, An-Yao Wang · 0 citations

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