ترغب بنشر مسار تعليمي؟ اضغط هنا

On Mubayis Conjecture and conditionally intersecting sets

59   0   0.0 ( 0 )
 نشر من قبل Adam Mammoliti
 تاريخ النشر 2017
  مجال البحث
والبحث باللغة English




اسأل ChatGPT حول البحث

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.

قيم البحث

اقرأ أيضاً

A family of subsets of $[n]$ is intersecting if every pair of its sets intersects. Determining the structure of large intersecting families is a central problem in extremal combinatorics. Frankl-Kupavskii and Balogh-Das-Liu-Sharifzadeh-Tran independe ntly showed that for $ngeq 2k + csqrt{kln k}$, almost all $k$-uniform intersecting families are stars. Improving their result, we show that the same conclusion holds for $ngeq 2k+ 100ln k$. Our proof uses, among others, Sapozhenkos graph container lemma and the Das-Tran removal lemma.
For positive integers $n,r,k$ with $nge r$ and $kge2$, a set ${(x_1,y_1),(x_2,y_2),dots,(x_r,y_r)}$ is called a $k$-signed $r$-set on $[n]$ if $x_1,dots,x_r$ are distinct elements of $[n]$ and $y_1dots,y_rin[k]$. We say a $t$-intersecting family cons isting of $k$-signed $r$-sets on $[n]$ is trivial if each member of this family contains a fixed $k$-signed $t$-set. In this paper, we determine the structure of large maximal non-trivial $t$-intersecting families. In particular, we characterize the non-trivial $t$-intersecting families with maximum size for $tge2$, extending a Hilton-Milner-type result for signed sets given by Borg.
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.
70 - Paul A. Russell 2007
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, Grah am, 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.
80 - P. Frankl , G.O.H. Katona 2021
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 sh adow $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.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا