View PDF HTML (experimental)

Abstract:In this paper, we study the problem of determining the maximum number $F_r(n,k)$ of edges in an $n$-vertex $r$-uniform hypergraph that contains no $(k+1)$-connected subgraph. The graph case, initiated by Mader, is a classical problem in graph theory that remains open. We first establish a limit theorem for $F_r(n,k)$ for all $k\ge r\ge 2$. As a consequence, we prove for the first time that, in Mader's problem (i.e., $r=2$), there exists a constant $c_k>0$ such that $F_2(n,k)=c_k n+O_k(1)$, and, for every $r\ge 3$, we determine $F_r(n,k)$ up to an $O(n)$ error term, thereby identifying its leading asymptotic term. We also address a related question of Carmesin by establishing a tight bound for $r$-uniform hypergraphs with no $(k+1)$-connected subgraph on more than $Ck$ vertices for any constant $C>2$ and sufficiently large $r$, and further obtain an asymptotically tight bound in the case $C=2$. Our proof combines the separator tree method introduced by Carmesin with several new combinatorial and optimization techniques, and we conclude with related remarks and open problems.

Submission history

From: Shengjie Xie [view email]
[v1] Sat, 18 Apr 2026 15:48:36 UTC (30 KB)
[v2] Sun, 5 Jul 2026 06:11:33 UTC (30 KB)