Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn strengthenings of the intersecting shadow theorem
81
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let $n > k > t geq j geq 1$ be integers. Let $X$ be an $n$-element set, ${Xchoose k}$ the collection of its $k$-subsets. A family $mathcal F subset {Xchoose k}$ is called $t$-intersecting if $|F cap F| geq t$ for all $F, F in mathcal F$. The $j$th shadow $partial^j mathcal F$ is the collection of all $(k - j)$-subsets that are contained in some member of~$mathcal F$. Estimating $|partial^j mathcal F|$ as a function of $|mathcal F|$ is a widely used tool in extremal set theory. A classical result of the second author (Theorem ref{th:1.3}) provides such a bound for $t$-intersecting families. It is best possible for $|mathcal F| = {2k - tchoose k}$. Our main result is Theorem ref{th:1.4} which gives an asymptotically optimal bound on $|partial^j mathcal F| / |mathcal F|$ for $|mathcal F|$ slightly larger, e.g., $|mathcal F| > frac32 {2k - tchoose k}$. We provide further improvements for $|mathcal F|$ very large as well.
rate research
Read More
A fundamental result in extremal set theory is Katonas shadow intersection theorem, which extends the Kruskal-Katona theorem by giving a lower bound on the size of the shadow of an intersecting family of $k$-sets in terms of its size. We improve this classical result and a related result of Ahlswede, Aydinian, and Khachatrian by proving tight bounds for families that can be quite small. For example, when $k=3$ our result is sharp for all families with $n$ points and at least $3n-7$ triples. Katonas theorem was extended by Frankl to families with matching number $s$. We improve Frankls result by giving tight bounds for large $n$.
A family of sets is said to be emph{symmetric} if its automorphism group is transitive, and emph{intersecting} if any two sets in the family have nonempty intersection. Our purpose here is to study the following question: for $n, kin mathbb{N}$ with $k le n/2$, how large can a symmetric intersecting family of $k$-element subsets of ${1,2,ldots,n}$ be? As a first step towards a complete answer, we prove that such a family has size at most [expleft(-frac{c(n-2k)log n}{k( log n - log k)} right) binom{n}{k},] where $c > 0$ is a universal constant. We also describe various combinatorial and algebraic approaches to constructing such families.
We shall be interested in the following Erdos-Ko-Rado-type question. Fix some subset B of [n]. How large a family A of subsets of [n] can we find such that the intersection of any two sets in A contains a cyclic translate (modulo n) of B? Chung, Graham, Frankl and Shearer have proved that, in the case where B is a block of length t, we can do no better than to take A to consist of all supersets of B. We give an alternative proof of this result, which is in a certain sense more direct.
Mubayis Conjecture states that if $mathcal{F}$ is a family of $k$-sized subsets of $[n] = {1,ldots,n}$ which, for $k geq d geq 2$, satisfies $A_1 capcdotscap A_d eq emptyset$ whenever $|A_1 cupcdotscup A_d| leq 2k$ for all distinct sets $A_1,ldots,A_d inmathcal{F}$, then $|mathcal{F}|leq binom{n-1}{k-1}$, with equality occurring only if $mathcal{F}$ is the family of all $k$-sized subsets containing some fixed element. This paper proves that Mubayis Conjecture is true for all families that are invariant with respect to shifting; indeed, these families satisfy a stronger version of Mubayis Conjecture. Relevant to the conjecture, we prove a fundamental bijective duality between $(i,j)$-unstable families and $(j,i)$-unstable families. Generalising previous intersecting conditions, we introduce the $(d,s,t)$-conditionally intersecting condition for families of sets and prove general results thereon. We conjecture on the size and extremal structures of families $mathcal{F}inbinom{[n]}{k}$ that are $(d,2k)$-conditionally intersecting but which are not intersecting, and prove results related to this conjecture. We prove fundamental theorems on two $(d,s)$-conditionally intersecting families that generalise previous intersecting families, and we pose an extension of a previous conjecture by Frankl and Furedi on $(3,2k-1)$-conditionally intersecting families. Finally, we generalise a classical result by ErdH{o}s, Ko and Rado by proving tight upper bounds on the size of $(2,s)$-conditionally intersecting families $mathcal{F}subseteq 2^{[n]}$ and by characterising the families that attain these bounds. We extend this theorem for certain parametres as well as for sufficiently large families with respect to $(2,s)$-conditionally intersecting families $mathcal{F}subseteq 2^{[n]}$ whose members have at most a fixed number $u$ members.
For $n > 2k geq 4$ we consider intersecting families $mathcal F$ consisting of $k$-subsets of ${1, 2, ldots, n}$. Let $mathcal I(mathcal F)$ denote the family of all distinct intersections $F cap F$, $F eq F$ and $F, Fin mathcal F$. Let $mathcal A$ consist of the $k$-sets $A$ satisfying $|A cap {1, 2, 3}| geq 2$. We prove that for $n geq 50 k^2$ $|mathcal I(mathcal F)|$ is maximized by $mathcal A$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
