The reviewed record of science sign in
Pith

arxiv: 1901.09278 · v4 · pith:YC7KO3Y6 · submitted 2019-01-26 · math.CO · cs.DM

Beyond the ErdH{o}s Matching Conjecture

Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel pith:YC7KO3Y6record.jsonopen to challenge →

classification math.CO cs.DM
keywords mathcalfamilymatchingchooseconjectureintersectingcaseldots
0
0 comments X
read the original abstract

A family $\mathcal F\subset {[n]\choose k}$ is $U(s,q)$ of for any $F_1,\ldots, F_s\in \mathcal F$ we have $|F_1\cup\ldots\cup F_s|\le q$. This notion generalizes the property of a family to be $t$-intersecting and to have matching number smaller than $s$. In this paper, we find the maximum $|\mathcal F|$ for $\mathcal F$ that are $U(s,q)$, provided $n>C(s,q)k$ with moderate $C(s,q)$. In particular, we generalize the result of the first author on the Erd\H{o}s Matching Conjecture and prove a generalization of the Erd\H{o}s-Ko-Rado theorem, which states that for $n> s^2k$ the largest family $\mathcal F\subset {[n]\choose k}$ with property $U(s,s(k-1)+1)$ is the star and is in particular intersecting. (Conversely, it is easy to see that any intersecting family in ${[n]\choose k}$ is $U(s,s(k-1)+1)$.) We investigate the case $k=3$ more thoroughly, showing that, unlike in the case of the Erd\H{o}s Matching Conjecture, in general there may be $3$ extremal families.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.