اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOn the maximum number of distinct intersections in an intersecting family
198
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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$.
قيم البحث
اقرأ أيضاً
For a family $mathcal F$, let $mathcal D(mathcal F)$ stand for the family of all sets that can be expressed as $Fsetminus G$, where $F,Gin mathcal F$. A family $mathcal F$ is intersecting if any two sets from the family have non-empty intersection. I
n this paper, we study the following question: what is the maximum of $|mathcal D(mathcal F)|$ for an intersecting family of $k$-element sets? Frankl conjectured that the maximum is attained when $mathcal F$ is the family of all sets containing a fixed element. We show that this holds if $n>50klog k$ and $k>50$. At the same time, we provide a counterexample for $n< 4k.$
A family $mathcal F$ has covering number $tau$ if the size of the smallest set intersecting all sets from $mathcal F$ is equal to $s$. Let $m(n,k,tau)$ stand for the size of the largest intersecting family $mathcal F$ of $k$-element subsets of ${1,ld
ots,n}$ with covering number $tau$. It is a classical result of ErdH os and Lovasz that $m(n,k,k)le k^k$ for any $n$. In this short note, we explore the behaviour of $m(n,k,tau)$ for $n<k^2$ and large $tau$. The results are quite surprising: For example, we show that $m(k^{3/2},k,tau) = (1-o(1)){n-1choose k-1}$ for $taule k-k^{3/4+o(1)}$. At the same time, $m(k^{3/2},k,tau)<e^{-ck^{1/2}}{nchoose k}$ if $tau>k-frac 12k^{1/2}$.
Let $r(k)$ denote the maximum number of edges in a $k$-uniform intersecting family with covering number $k$. ErdH{o}s and Lovasz proved that $ lfloor k! (e-1) rfloor leq r(k) leq k^k.$ Frankl, Ota, and Tokushige improved the lower bound to $r(k) geq
left( k/2 right)^{k-1}$, and Tuza improved the upper bound to $r(k) leq (1-e^{-1}+o(1))k^k$. We establish that $ r(k) leq (1 + o(1)) k^{k-1}$.
Wilfs Sixth Unsolved Problem asks for any interesting properties of the set of partitions of integers for which the (nonzero) multiplicities of the parts are all different. We refer to these as emph{Wilf partitions}. Using $f(n)$ to denote the number
of Wilf partitions, we establish lead-order asymptotics for $ln{f(n)}$.
In this paper, we give bounds on the dichromatic number $vec{chi}(Sigma)$ of a surface $Sigma$, which is the maximum dichromatic number of an oriented graph embeddable on $Sigma$. We determine the asymptotic behaviour of $vec{chi}(Sigma)$ by showing
that there exist constants $a_1$ and $a_2$ such that, $ a_1frac{sqrt{-c}}{log(-c)} leq vec{chi}(Sigma) leq a_2 frac{sqrt{-c}}{log(-c)} $ for every surface $Sigma$ with Euler characteristic $cleq -2$. We then give more explicit bounds for some surfaces with high Euler characteristic. In particular, we show that the dichromatic numbers of the projective plane $mathbb{N}_1$, the Klein bottle $mathbb{N}_2$, the torus $mathbb{S}_1$, and Dycks surface $mathbb{N}_3$ are all equal to $3$, and that the dichromatic numbers of the $5$-torus $mathbb{S}_5$ and the $10$-cross surface $mathbb{N}_{10}$ are equal to $4$. We also consider the complexity of deciding whether a given digraph or oriented graph embedabble in a fixed surface is $k$-dicolourable. In particular, we show that for any surface, deciding whether a digraph embeddable on this surface is $2$-dicolourable is NP-complete, and that deciding whether a planar oriented graph is $2$-dicolourable is NP-complete unless all planar oriented graphs are $2$-dicolourable (which was conjectured by Neumann-Lara).
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
