اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدAn upper bound for the size of a $k$-uniform intersecting family with covering number $k$
112
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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}$.
قيم البحث
اقرأ أيضاً
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}$.
An ordered hypergraph is a hypergraph $H$ with a specified linear ordering of the vertices, and the appearance of an ordered hypergraph $G$ in $H$ must respect the specified order on $V(G)$. In on-line Ramsey theory, Builder iteratively presents edge
s that Painter must immediately color. The $t$-color on-line size Ramsey number $tilde R_t (G)$ of an ordered hypergraph $G$ is the minimum number of edges Builder needs to play (on a large ordered set of vertices) to force Painter using $t$ colors to produce a monochromatic copy of $G$. The monotone tight path $P_r^{(k)}$ is the ordered hypergraph with $r$ vertices whose edges are all sets of $k$ consecutive vertices. We obtain good bounds on $tilde R_t (P_r^{(k)})$. Letting $m=r-k+1$ (the number of edges in $P_r^{(k)}$), we prove $m^{t-1}/(3sqrt t)letilde R_t (P_r^{(2)})le tm^{t+1}$. For general $k$, a trivial upper bound is ${R choose k}$, where $R$ is the least number of vertices in a $k$-uniform (ordered) hypergraph whose $t$-colorings all contain $P_r^{(k)}$ (and is a tower of height $k-2$). We prove $R/(klg R)letilde R_t(P_r^{(k)})le R(lg R)^{2+epsilon}$, where $epsilon$ is any positive constant and $t(m-1)$ is sufficiently large. Our upper bounds improve prior results when $t$ grows faster than $m/log m$. We also generalize our results to $ell$-loose monotone paths, where each successive edge begins $ell$ vertices after the previous edge.
The Wiener index of a connected graph is the summation of all distances between unordered pairs of vertices of the graph. In this paper, we give an upper bound on the Wiener index of a $k$-connected graph $G$ of order $n$ for integers $n-1>k ge 1$:
[W(G) le frac{1}{4} n lfloor frac{n+k-2}{k} rfloor (2n+k-2-klfloor frac{n+k-2}{k} rfloor).] Moreover, we show that this upper bound is sharp when $k ge 2$ is even, and can be obtained by the Wiener index of Harary graph $H_{k,n}$.
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$.
A fan $F_n$ is a graph consisting of $n$ triangles, all having precisely one common vertex. Currently, the best known bounds for the Ramsey number $R(F_n)$ are $9n/2-5 leq R(F_n) leq 11n/2+6$, obtained by Chen, Yu and Zhao. We improve the upper bound to $31n/6+O(1)$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
