TY - JOUR
T1 - Maximum size intersecting families of bounded minimum positive co-degree
AU - BALOGH, JOZSEF
AU - LEMONS, NATHAN
AU - PALMER, CORY
N1 - \\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]).
PY - 2021
Y1 - 2021
N2 - 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.
AB - 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.
KW - Co-degree
KW - Hypergraph
KW - Intersecting
UR - http://www.scopus.com/inward/record.url?scp=85110390757&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85110390757&partnerID=8YFLogxK
U2 - 10.1137/20M1336989
DO - 10.1137/20M1336989
M3 - Article
AN - SCOPUS:85110390757
SN - 0895-4801
VL - 35
SP - 1525
EP - 1535
JO - SIAM Journal on Discrete Mathematics
JF - SIAM Journal on Discrete Mathematics
IS - 3
ER -