Hypergraphs without Subgraphs of Given Connectivity
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911604339113984 |
|---|---|
| author | Ma, Jie Xie, Shengjie Zheng, Zhiheng |
| author_facet | Ma, Jie Xie, Shengjie Zheng, Zhiheng |
| contents | In this paper, we study the problem of determining the maximum number of edges in an $n$-vertex $r$-uniform hypergraph that contains no $(k+1)$-connected subgraph. The graph case is a classical problem initiated by Mader, central to graph theory, and still open. First, for all $r \ge 3$, we determine this maximum up to an $O(n)$ error term, thereby identifying its leading 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_17038 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Hypergraphs without Subgraphs of Given Connectivity Ma, Jie Xie, Shengjie Zheng, Zhiheng Combinatorics In this paper, we study the problem of determining the maximum number of edges in an $n$-vertex $r$-uniform hypergraph that contains no $(k+1)$-connected subgraph. The graph case is a classical problem initiated by Mader, central to graph theory, and still open. First, for all $r \ge 3$, we determine this maximum up to an $O(n)$ error term, thereby identifying its leading 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. |
| title | Hypergraphs without Subgraphs of Given Connectivity |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2604.17038 |