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

On the number of containments in $P$-free families

51   0   0.0 ( 0 )
 نشر من قبل Abhishek Methuku
 تاريخ النشر 2018
  مجال البحث
والبحث باللغة English




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

A subfamily ${F_1,F_2,dots,F_{|P|}}subseteq mathcal F$ is a copy of the poset $P$ if there exists a bijection $i:Prightarrow {F_1,F_2,dots,F_{|P|}}$ such that $ple_P q$ implies $i(p)subseteq i(q)$. A family $mathcal F$ is $P$-free, if it does not contain a copy of $P$. In this paper we establish basic results on the maximum possible number of $k$-chains in a $P$-free family $mathcal Fsubseteq 2^{[n]}$. We prove that if the height of $P$, $h(P) > k$, then this number is of the order $Theta(prod_{i=1}^{k+1}binom{l_{i-1}}{l_i})$, where $l_0=n$ and $l_1ge l_2ge dots ge l_{k+1}$ are such that $n-l_1,l_1-l_2,dots, l_k-l_{k+1},l_{k+1}$ differ by at most one. On the other hand if $h(P)le k$, then we show that this number is of smaller order of magnitude. Let $vee_r$ denote the poset on $r+1$ elements $a, b_1, b_2, ldots, b_r$, where $a < b_i$ for all $1 le i le r$ and let $wedge_r$ denote its dual. For any values of $k$ and $l$, we construct a ${wedge_k,vee_l}$-free family and we conjecture that it contains asymptotically the maximum number of pairs in containment. We prove that this conjecture holds under the additional assumption that a chain of length 4 is forbidden. Moreover, we prove the conjecture for some small values of $k$ and $l$. We also derive the asymptotics of the maximum number of copies of certain tree posets $T$ of height 2 in ${wedge_k,vee_l}$-free families $mathcal F subseteq 2^{[n]}$.



قيم البحث

اقرأ أيضاً

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.$
We count the ordered sum-free triplets of subsets in the group $mathbb{Z}/pmathbb{Z}$, i.e., the triplets $(A,B,C)$ of sets $A,B,C subset mathbb{Z}/pmathbb{Z}$ for which the equation $a+b=c$ has no solution with $ain A$, $b in B$ and $c in C$. Our ma in theorem improves on a recent result by Semchankau, Shabanov, and Shkredov using a different and simpler method. Our proof relates previous results on the number of independent sets of regular graphs by Kahn, Perarnau and Perkins, and Csikvari to produce explicit estimates on smaller order terms. We also obtain estimates for the number of sum-free triplets of subsets in a general abelian group.
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}$.
299 - Xiaolan Hu , Xing Peng 2021
For a simple graph $G$, let $chi_f(G)$ be the fractional chromatic number of $G$. In this paper, we aim to establish upper bounds on $chi_f(G)$ for those graphs $G$ with restrictions on the clique number. Namely, we prove that for $Delta geq 4$, if $ G$ has maximum degree at most $Delta$ and is $K_{Delta}$-free, then $chi_f(G) leq Delta-tfrac{1}{8}$ unless $G= C^2_8$ or $G = C_5boxtimes K_2$. This im proves the result in [King, Lu, and Peng, SIAM J. Discrete Math., 26(2) (2012), pp. 452-471] for $Delta geq 4$ and the result in [Katherine and King, SIAM J.Discrete Math., 27(2) (2013), pp. 1184-1208] for $Delta in {6,7,8}$.
168 - Younjin Kim 2020
A subset $A$ of the $k$-dimensional grid ${1,2, cdots, N}^k$ is called $k$-dimensional corner-free if it does not contain a set of points of the form ${ a } cup { a + de_i : 1 leq i leq k }$ for some $a in {1,2, cdots, N}^k$ and $d > 0$, where $e_1,e _2, cdots, e_k$ is the standard basis of $mathbb{R}^k$. We define the maximum size of a $k$-dimensional corner-free subset of ${1,2, cdots, N}^k$ by $c_k(N)$. In this paper, we show that the number of $k$-dimensional corner-free subsets of the $k$-dimensional grid ${1,2, cdots, N}^k$ is at most $2^{O(c_k(N))}$ for infinitely many values of $N$. Our main tool for the proof is a supersaturation result for $k$-dimensional corners in sets of size $Theta(c_k(N))$ and the hypergraph container method.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

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