اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدA note on the colorful fractional Helly theorem
234
0
0.0
(
0
)
تأليف
Minki Kim
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Hellys theorem is a classical result concerning the intersection patterns of convex sets in $mathbb{R}^d$. Two important generalizations are the colorful version and the fractional version. Recently, B{a}r{a}ny et al. combined the two, obtaining a colorful fractional Helly theorem. In this paper, we give an improved version of their result.
قيم البحث
اقرأ أيضاً
Hellys theorem and its variants show that for a family of convex sets in Euclidean space, local intersection patterns influence global intersection patterns. A classical result of Eckhoff in 1988 provided an optimal fractional Helly theorem for axis-
aligned boxes, which are Cartesian products of line segments. Answering a question raised by Barany and Kalai, and independently Lew, we generalize Eckhoffs result to Cartesian products of convex sets in all dimensions. In particular, we prove that given $alpha in (1-frac{1}{t^d},1]$ and a finite family $mathcal{F}$ of Cartesian products of convex sets $prod_{iin[t]}A_i$ in $mathbb{R}^{td}$ with $A_isubset mathbb{R}^d$ if at least $alpha$-fraction of the $(d+1)$-tuples in $mathcal{F}$ are intersecting then at least $(1-(t^d(1-alpha))^{1/(d+1)})$-fraction of sets in $mathcal{F}$ are intersecting. This is a special case of a more general result on intersections of $d$-Leray complexes. We also provide a construction showing that our result on $d$-Leray complexes is optimal. Interestingly the extremal example is representable as a family of cartesian products of convex sets, implying the bound $alpha>1-frac{1}{t^d}$ and the fraction $(1-(t^d(1-alpha))^{1/(d+1)})$ above are also best possible. The well-known optimal construction for fractional Helly theorem for convex sets in $mathbb{R}^d$ does not have $(p,d+1)$-condition for sublinear $p$. Inspired by this we give constructions showing that, somewhat surprisingly, imposing additional $(p,d+1)$-condition has negligible effect on improving the quantitative bounds in neither the fractional Helly theorem for convex sets nor Cartesian products of convex sets. Our constructions offer a rich family of distinct extremal configurations for fractional Helly theorem, implying in a sense that the optimal bound is stable.
We give the following extension of Baranys colorful Caratheodory theorem: Let M be an oriented matroid and N a matroid with rank function r, both defined on the same ground set V and satisfying rank(M) < rank(N). If every subset A of V with r(V - A)
< rank (M) contains a positive circuit of M, then some independent set of N contains a positive circuit of M.
The Hales-Jewett theorem for alphabet of size 3 states that whenever the Hales-Jewett cube [3]^n is r-coloured there is a monochromatic line (for n large). Conlon and Kamcev conjectured that, for any n, there is a 2-colouring of [3]^n for which there
is no monochromatic line whose active coordinate set is an interval. In this note we disprove this conjecture.
If L is a partition of n, the rank of L is the size of the largest part minus the number of parts. Under the uniform distribution on partitions, Bringmann, Mahlburg, and Rhoades showed that the rank statistic has a limiting distribution. We identify
the limit as the difference between two independent extreme value distributions and as the distribution of B(T) where B(t) is standard Brownian motion and T is the first time that an independent three-dimensional Brownian motion hits the unit sphere. The same limit holds for the crank.
In 1990, Alon and Kleitman proposed an argument for the sum-free subset problem: every set of n nonzero elements of a finite Abelian group contains a sum-free subset A of size |A|>frac{2}{7}n. In this note, we show that the argument confused two diff
erent randomness. It applies only to the finite Abelian group G = (Z/pZ)^s where p is a prime. For the general case, the problem remains open.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
