Abstract
Let H be an r-uniform hypergraph. The minimum positive co-degree of H , denoted by δ + r 1(H ), is the minimum k such that if S is an (r 1)-set contained in a hyperedge of H , then S is contained in at least k hyperedges of H . For r ≥ k fixed and n sufficiently large, we determine the maximum possible size of an intersecting r-uniform n-vertex hypergraph with minimum positive co-degree δ + r 1(H ) ≥ k and characterize the unique hypergraph attaining this maximum. This generalizes the Erdos-Ko-Rado theorem which corresponds to the case k = 1. Our proof is based on the delta-system method.
| Original language | English |
|---|---|
| Pages (from-to) | 1525-1535 |
| Number of pages | 11 |
| Journal | SIAM Journal on Discrete Mathematics |
| Volume | 35 |
| Issue number | 3 |
| DOIs | |
| State | Published - 2021 |
Funding
\ast Received by the editors May 11, 2020; accepted for publication (in revised form) March 28, 2021; published electronically July 1, 2021. https://doi.org/10.1137/20M1336989 Funding: The first author was partially supported by NSF grant DMS-1764123 and by Arnold O. Beckman Research Award (UIUC) Campus Research Board 18132, a Simons Fellowship, and the Langan Scholar Fund (UIUC). The third author's research was supported by a grant from the Simons Foundation, 712036. \dagger Department of Mathematics, University of Illinois at Urbana-Champaign, Urbana, IL 61801 USA, and Moscow Institute of Physics and Technology (MIPT), Dolgoprudny, Moscow Region, 141701, Russian Federation ([email protected]). \ddagger Theoretical Division, Los Alamos National Labratory, Los Alamos, NM 87545 USA (nlemons@ lanl.gov). \S Department of Mathematical Sciences, University of Montana, Missoula, MT 59801 USA ([email protected]).
| Funders | Funder number |
|---|---|
| DMS-1764123 | |
| 1764123 | |
| Simons Foundation | 712036 |
| University of Illinois at Urbana-Champaign | 18132 |
Keywords
- Co-degree
- Hypergraph
- Intersecting