Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA note on the colorful fractional Helly theorem
234
0
0.0
(
0
)
Authors
Minki Kim
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 different 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
