BZPEER

preprint2022arXiv

Best possible bounds on the number of distinct differences in intersecting families

For a family $\mathcal F$ , let $\mathcal D(\mathcal F)$ stand for the family of all sets that can be expressed as $F\setminus G$ , where $F,G\in \mathcal F$ . A family $\mathcal F$ is intersecting if any two sets from the family have non-empty intersection. In 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 \ge 50k\ln k$ and $k \ge 50$ . At the same time, we provide a counterexample for $n< 4k$ .

preprint2022arXiv

Choice number of Kneser graphs

In this short note, we show that for any $ε>0$ and $k<n^{0.5-ε}$ the choice number of the Kneser graph $KG_{n,k}$ is $Θ(n\log n)$ .

preprint2022arXiv

Nearly $k$ -distance sets

We say that a set of points $S\subset \mathbb{R}^d$ is an $\varepsilon$ -nearly $k$ -distance set if there exist $1\le t_1\le \ldots\le t_k,$ such that the distance between any two distinct points in $S$ falls into $[t_1,t_1+\varepsilon]\cup\ldots\cup[t_k,t_k+\varepsilon]$ . In this paper, we study the quantity $M_k(d) = \lim_{\varepsilon\to 0}\max\{|S|\ :\ S\text{ is an }\varepsilon\text{-nearly } k \text{-distance set in } \mathbb{R}^d\}$ and its relation to the classical quantity $m_k(d)$ : the size of the largest $k$ -distance set in $\mathbb{R}^d$ . We obtain that $M_k(d) = m_k(d)$ for $k=2,3$ , as well as for any fixed $k$ , provided that $d$ is sufficiently large. The last result answers a question, proposed by Erdős, Makai and Pach. We also address a closely related Turán-type problem, studied by Erdős, Makai, Pach, and Spencer in the 80's: given $n$ points in $\mathbb{R}^d$ , how many pairs of them form a distance that belongs to $[t_1,t_1+1]\cup\ldots\cup[t_k,t_k+1],$ where $t_1,\ldots, t_k$ are fixed and any two points in the set are at distance at least $1$ apart? We establish the connection between this quantity and a quantity closely related to $M_k(d-1)$ , as well as obtain an exact answer for the same ranges $k,d$ as above.

preprint2022arXiv

Octopuses in the Boolean cube: families with pairwise small intersections, part I

Let $\mathcal F_1, \ldots, \mathcal F_\ell$ be families of subsets of $\{1, \ldots, n\}$ . Suppose that for distinct $k, k'$ and arbitrary $F_1 \in \mathcal F_{k}, F_2 \in \mathcal F_{k'}$ we have $|F_1 \cap F_2|\le m.$ What is the maximal value of $|\mathcal F_1|\ldots |\mathcal F_\ell|$ ? In this work we find the asymptotic of this product as $n$ tends to infinity for constant $\ell$ and~ $m$ . This question is related to a conjecture of Bohn et al. that arose in the 2-level polytope theory and asked for the largest product of the number of facets and vertices in a two-level polytope. This conjecture was recently resolved by Weltge and the first author. The main result can be rephrased in terms of colorings. We give an asymptotic answer to the following question. Given an edge coloring of a complete $m$ -uniform hypergraph into $\ell$ colors, what is the maximum of $\prod M_i$ , where $M_i$ is the number of monochromatic cliques in $i$ -th color?

preprint2022arXiv

Perfect matchings in down-sets

In this paper, we show that, given two down-sets (simplicial complexes) there is a matching between them that matches disjoint sets and covers the smaller of the two down-sets. This result generalizes an unpublished result of Berge from circa 1980. The result has nice corollaries for cross-intersecting families and Chvátal's conjecture. More concretely, we show that Chvátal's conjecture is true for intersecting families with covering number $2$ . A family $\mathcal F\subset 2^{[n]}$ is intersection-union (IU) if for any $A,B\in\mathcal F$ we have $1\le |A\cap B|\le n-1$ . Using the aforementioned result, we derive several exact product- and sum-type results for IU-families.

preprint2022arXiv

Rainbow version of the Erd\H os Matching Conjecture via Concentration

We say that the families $\mathcal F_1,\ldots, \mathcal F_{s+1}$ of $k$ -element subsets of $[n]$ are cross-dependent if there are no pairwise disjoint sets $F_1,\ldots, F_{s+1}$ , where $F_i\in \mathcal F_i$ for each $i$ . The rainbow version of the Erd\H os Matching Conjecture due to Aharoni and Howard and independently to Huang, Loh and Sudakov states that $\min_{i} |\mathcal F_i|\le \max\big\{{n\choose k}-{n-s\choose k}, {(s+1)k-1\choose k}\big\}$ for $n\ge (s+1)k$ . In this paper, we prove this conjecture for $n>3e(s+1)k$ and $s>10^7$ . One of the main tools in the proof is a concentration inequality due to Frankl and the author.

preprint2022arXiv

Reconstructing the degree sequence of a sparse graph from a partial deck

The deck of a graph $G$ is the multiset of cards $\{G-v:v\in V(G)\}$ . Myrvold (1992) showed that the degree sequence of a graph on $n\geq7$ vertices can be reconstructed from any deck missing one card. We prove that the degree sequence of a graph with average degree $d$ can reconstructed from any deck missing $O(n/d^3)$ cards. In particular, in the case of graphs that can be embedded on a fixed surface (e.g. planar graphs), the degree sequence can be reconstructed even when a linear number of the cards are missing.

preprint2022arXiv

Trivial colors in colorings of Kneser graphs

We show that any proper coloring of a Kneser graph $KG_{n,k}$ with $n-2k+2$ colors contains a trivial color (i.e., a color consisting of sets that all contain a fixed element), provided $n>(2+\varepsilon)k^2$ , where $\varepsilon\to 0$ as $k\to \infty$ . This bound is essentially tight. This is a consequence of a more general result on the minimum number of non-trivial colors needed to properly color $KG_{n,k}$ .

preprint2021arXiv

Intersection theorems for triangles

Given a family of sets on the plane, we say that the family is intersecting if for any two sets from the family their interiors intersect. In this paper, we study intersecting families of triangles with vertices in a given set of points. In particular, we show that if a set $P$ of $n$ points is in convex position, then the largest intersecting family of triangles with vertices in $P$ contains at most $(\frac{1}{4}+o(1))\binom{n}{3}$ triangles.

preprint2020arXiv

Beyond the Erdős Matching Conjecture

A family $\mathcal F\subset {[n]\choose k}$ is $U(s,q)$ of for any $F_1,\ldots, F_s\in \mathcal F$ we have $|F_1\cup\ldots\cup F_s|\le q$ . This notion generalizes the property of a family to be $t$ -intersecting and to have matching number smaller than $s$ . In this paper, we find the maximum $|\mathcal F|$ for $\mathcal F$ that are $U(s,q)$ , provided $n>C(s,q)k$ with moderate $C(s,q)$ . In particular, we generalize the result of the first author on the Erdős Matching Conjecture and prove a generalization of the Erdős-Ko-Rado theorem, which states that for $n> s^2k$ the largest family $\mathcal F\subset {[n]\choose k}$ with property $U(s,s(k-1)+1)$ is the star and is in particular intersecting. (Conversely, it is easy to see that any intersecting family in ${[n]\choose k}$ is $U(s,s(k-1)+1)$ .) We investigate the case $k=3$ more thoroughly, showing that, unlike in the case of the Erdős Matching Conjecture, in general there may be $3$ extremal families.

preprint2020arXiv

Binary scalar products

Let $A,B \subseteq \mathbb{R}^d$ both span $\mathbb{R}^d$ such that $\langle a, b \rangle \in \{0,1\}$ holds for all $a \in A$ , $b \in B$ . We show that $|A| \cdot |B| \le (d+1) 2^d$ . This allows us to settle a conjecture by Bohn, Faenza, Fiorini, Fisikopoulos, Macchia, and Pashkovich (2015) concerning 2-level polytopes. Such polytopes have the property that for every facet-defining hyperplane $H$ there is a parallel hyperplane $H'$ such that $H \cup H'$ contain all vertices. The authors conjectured that for every $d$ -dimensional 2-level polytope $P$ the product of the number of vertices of $P$ and the number of facets of $P$ is at most $d 2^{d+1}$ , which we show to be true.

preprint2020arXiv

Intersection theorems for $(-1,0,1)$ -vectors

In this paper, we investigate Erd\H os--Ko--Rado type theorems for families of vectors from $\{0,\pm 1\}^n$ with fixed numbers of $+1$ 's and $-1$ 's. Scalar product plays the role of intersection size. In particular, we sharpen our earlier result on the largest size of a family of such vectors that avoids the smallest possible scalar product. We also obtain an exact result for the largest size of a family with no negative scalar products.

preprint2020arXiv

Maximal degrees in subgraphs of Kneser graphs

In this paper, we study the maximum degree in non-empty induced subgraphs of the Kneser graph $KG(n,k)$ . One of the main results asserts that, for $k>k_0$ and $n>64k^2$ , whenever a non-empty subgraph has $m\ge k{n-2\choose k-2}$ vertices, its maximum degree is at least $\frac 12(1-\frac {k^2}n) m - {n-2\choose k-2}\ge 0.49 m$ . This bound is essentially best possible. One of the intermediate steps is to obtain structural results on non-empty subgraphs with small maximum degree.

preprint2020arXiv

Simple juntas for shifted families

We say that a family $\mathcal F$ of $k$ -element sets is a {\it $j$ -junta} if there is a set $J$ of size $j$ such that, for any $F$ , its presence in $\mathcal F$ depends on its intersection with $J$ only. Approximating arbitrary families by $j$ -juntas with small $j$ is a recent powerful technique in extremal set theory. The weak point of all known junta approximation results is that they work in the range $n>Ck$ , where $C$ is an extremely fast growing function of the input parameters, such as the quality of approximation or the number of families we simultaneously approximate. We say that a family $\mathcal F$ is {\it shifted} if for any $F=\{x_1,\ldots, x_k\}\in \mathcal F$ and any $G =\{y_1,\ldots, y_k\}$ such that $y_i\le x_i$ , we have $G\in \mathcal F$ . For many extremal set theory problems, including the Erd\H os Matching Conjecture, or the Complete $t$ -Intersection Theorem, it is sufficient to deal with shifted families only. In this paper, we present very general approximation by juntas results for shifted families with explicit (and essentially linear) dependency on the input parameters. The results are best possible up to some constant factors. Moreover, they give meaningful statements for almost all range of values of $n$ . The proofs are shorter than the proofs of the previous approximation by juntas results and are completely self-contained. As an application of our junta approximation, we give a nearly-linear bound for the multi-family version of the Erd\H os Matching Conjecture. More precisely, we prove the following result. Let $n\ge 12sk\log(e^2s)$ and suppose that the families $\mathcal F_1,\ldots, \mathcal F_s\subset {[n]\choose k}$ do not contain $F_1\in\mathcal F_1,\ldots, F_s\in \mathcal F_s$ such that $F_i$ 's are pairwise disjoint. Then $\min_{i}|\mathcal F_i|\le {n\choose k}-{n-s+1\choose k}.$

preprint2020arXiv

The right acute angles problem?

The Danzer--Grünbaum acute angles problem asks for the largest size of a set of points in ${\mathbb R}^d$ that determines only acute angles. Recently, the problem was essentially solved thanks to the results of the second author and of Gerencsér and Harangi: now, the lower and the upper bounds are $2^{d-1}+1$ and $2^d-1$ , respectively. The lower-bound construction is surprisingly simple. In this note, we suggest the following variant of the problem, which is one way to "save" the problem. Put $F(α) = \lim_{d\to \infty} f(d,α)^{1/d}$ , where $f(d,α)$ is the largest set of points in ${\mathbb R}^d$ with no angle greater than $α$ . Then the question is to find $c:= \lim_{α\to π/2^-}F(α).$ Although one may expect that $c=2$ in view of the result of Gerencsér and Harangi, the best lower bound we could get is $c\ge \sqrt 2$ . We also solve a related problem of Erdos and Füredi on the "stability" of the acute angles problem and refute another conjecture stated in the same paper.

preprint2020arXiv

The VC-dimension of k-vertex d-polytopes

In this short note, we show that the VC-dimension of the class of $k$ -vertex polytopes in $\mathbb R^d$ is at most $8d^2k\log_2k$ , answering an old question of Long and Warmuth.

preprint2020arXiv

When are epsilon-nets small?

In many interesting situations the size of epsilon-nets depends only on $ε$ together with different complexity measures. The aim of this paper is to give a systematic treatment of such complexity measures arising in Discrete and Computational Geometry and Statistical Learning, and to bridge the gap between the results appearing in these two fields. As a byproduct, we obtain several new upper bounds on the sizes of epsilon-nets that generalize/improve the best known general guarantees. In particular, our results work with regimes when small epsilon-nets of size $o(\frac{1}ε)$ exist, which are not usually covered by standard upper bounds. Inspired by results in Statistical Learning we also give a short proof of the Haussler's upper bound on packing numbers.

preprint2018arXiv

Embedding graphs in Euclidean space

The dimension of a graph $G$ is the smallest $d$ for which its vertices can be embedded in $d$ -dimensional Euclidean space in the sense that the distances between endpoints of edges equal $1$ (but there may be other unit distances). Answering a question of Erdős and Simonovits [Ars Combin. 9 (1980) 229--246], we show that any graph with less than $\binom{d+2}{2}$ edges has dimension at most $d$ . Improving their result, we prove that that the dimension of a graph with maximum degree $d$ is at most $d$ . We show the following Ramsey result: if each edge of the complete graph on $2d$ vertices is coloured red or blue, then either the red graph or the blue graph can be embedded in Euclidean $d$ -space. We also derive analogous results for embeddings of graphs into the $(d-1)$ -dimensional sphere of radius $1/\sqrt{2}$ .

Andrey Kupavskii

Research overview

Is this your work?

18 publications

Best possible bounds on the number of distinct differences in intersecting families

Choice number of Kneser graphs

Nearly $k$ -distance sets

Octopuses in the Boolean cube: families with pairwise small intersections, part I

Perfect matchings in down-sets

Rainbow version of the Erd\H os Matching Conjecture via Concentration

Reconstructing the degree sequence of a sparse graph from a partial deck

Trivial colors in colorings of Kneser graphs

Intersection theorems for triangles

Beyond the Erdős Matching Conjecture

Binary scalar products

Intersection theorems for $(-1,0,1)$ -vectors

Maximal degrees in subgraphs of Kneser graphs

Simple juntas for shifted families

The right acute angles problem?

The VC-dimension of k-vertex d-polytopes

When are epsilon-nets small?

Embedding graphs in Euclidean space

See the researcher in context

Building this map preview

Andrey Kupavskii

Research overview

Is this your work?

18 publications

Best possible bounds on the number of distinct differences in intersecting families

Choice number of Kneser graphs

Nearly kkk-distance sets

Octopuses in the Boolean cube: families with pairwise small intersections, part I

Perfect matchings in down-sets

Rainbow version of the Erd\H os Matching Conjecture via Concentration

Reconstructing the degree sequence of a sparse graph from a partial deck

Trivial colors in colorings of Kneser graphs

Intersection theorems for triangles

Beyond the Erdős Matching Conjecture

Binary scalar products

Intersection theorems for (−1,0,1)(-1,0,1)(−1,0,1)-vectors

Maximal degrees in subgraphs of Kneser graphs

Simple juntas for shifted families

The right acute angles problem?

The VC-dimension of k-vertex d-polytopes

When are epsilon-nets small?

Embedding graphs in Euclidean space

See the researcher in context

Building this map preview

Nearly $k$ -distance sets

Intersection theorems for $(-1,0,1)$ -vectors