Source author record

Zuzana Safernová

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

3works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2014arXiv

Lower bounds on geometric Ramsey functions

We continue a sequence of recent works studying Ramsey functions for semialgebraic predicates in $\mathbb{R}^d$ . A $k$ -ary semialgebraic predicate $Φ(x_1,\ldots,x_k)$ on $\mathbb{R}^d$ is a Boolean combination of polynomial equations and inequalities in the $kd$ coordinates of $k$ points $x_1,\ldots,x_k\in\mathbb{R}^d$ . A sequence $P=(p_1,\ldots,p_n)$ of points in $\mathbb{R}^d$ is called $Φ$ -homogeneous if either $Φ(p_{i_1}, \ldots,p_{i_k})$ holds for all choices $1\le i_1 < \cdots < i_k\le n$ , or it holds for no such choice. The Ramsey function $R_Φ(n)$ is the smallest $N$ such that every point sequence of length $N$ contains a $Φ$ -homogeneous subsequence of length $n$ . Conlon, Fox, Pach, Sudakov, and Suk constructed the first examples of semialgebraic predicates with the Ramsey function bounded from below by a tower function of arbitrary height: for every $k\ge 4$ , they exhibit a $k$ -ary $Φ$ in dimension $2^{k-4}$ with $R_Φ$ bounded below by a tower of height $k-1$ . We reduce the dimension in their construction, obtaining a $k$ -ary semialgebraic predicate $Φ$ on $\mathbb{R}^{k-3}$ with $R_Φ$ bounded below by a tower of height $k-1$ . We also provide a natural geometric Ramsey-type theorem with a large Ramsey function. We call a point sequence $P$ in $\mathbb{R}^d$ order-type homogeneous if all $(d+1)$ -tuples in $P$ have the same orientation. Every sufficiently long point sequence in general position in $\mathbb{R}^d$ contains an order-type homogeneous subsequence of length $n$ , and the corresponding Ramsey function has recently been studied in several papers. Together with a recent work of Bárány, Matoušek, and Pór, our results imply a tower function of $Ω(n)$ of height $d$ as a lower bound, matching an upper bound by Suk up to the constant in front of $n$ .

preprint2014arXiv

Simplifying inclusion-exclusion formulas

Let $\mathcal{F}=\{F_1,F_2, \ldots,F_n\}$ be a family of $n$ sets on a ground set $S$ , such as a family of balls in $\mathbb{R}^d$ . For every finite measure $μ$ on $S$ , such that the sets of $\mathcal{F}$ are measurable, the classical inclusion-exclusion formula asserts that $μ(F_1\cup F_2\cup\cdots\cup F_n)=\sum_{I:\emptyset\ne I\subseteq[n]} (-1)^{|I|+1}μ\Bigl(\bigcap_{i\in I} F_i\Bigr)$ ; that is, the measure of the union is expressed using measures of various intersections. The number of terms in this formula is exponential in $n$ , and a significant amount of research, originating in applied areas, has been devoted to constructing simpler formulas for particular families $\mathcal{F}$ . We provide an upper bound valid for an arbitrary $\mathcal{F}$ : we show that every system $\mathcal{F}$ of $n$ sets with $m$ nonempty fields in the Venn diagram admits an inclusion-exclusion formula with $m^{O(\log^2n)}$ terms and with $\pm1$ coefficients, and that such a formula can be computed in $m^{O(\log^2n)}$ expected time. For every $\varepsilon>0$ we also construct systems with Venn diagram of size $m$ for which every valid inclusion-exclusion formula has the sum of absolute values of the coefficients at least $Ω(m^{2-\varepsilon})$ .

preprint2010arXiv

On the nonexistence of k-reptile tetrahedra

A d-dimensional simplex S is called a k-reptile if it can be tiled without overlaps by simplices S_1,S_2,...,S_k that are all congruent and similar to S. For d=2, k-reptile simplices (triangles) exist for many values of k and they have been completely characterized by Snover, Waiveris, and Williams. On the other hand, for d > 2, only one construction of k-reptile simplices is known, the Hill simplices, and it provides only k of the form m^d, m=2,3,.... We prove that for d=3, k-reptile simplices (tetrahedra) exist only for k=m^3. This partially confirms a conjecture of Hertel, asserting that the only k-reptile tetrahedra are the Hill tetrahedra. Our research has been motivated by the problem of probabilistic packet marking in theoretical computer science, introduced by Adler in 2002.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.