Annotation of the results obtained in 2021
Ramsey theory in space with Chebyshev metric. One of the classical problems in combinatorial geometry was posed by Nelson in 1950: what is the minimum number of colors needed to color the Euclidean plane so that no two points of the same color are at unit distance apart? We split our results into three groups. The first one deals with ‘one-dimensional' metric spaces, called batons. We significantly simplify some of the arguments from the paper of Kupavskii and Sagdeev for such metric spaces, obtain asymptotically optimal values of the base of the exponent from their main Theorem, and uncover its connection to a certain well-studied one-dimensional number-theoretical problem. The second group of results extends the scope of these propositions to Cartesian products of arithmetic progressions. Finally, the last group deals with infinite forbidden metric spaces. Let’s describe the results in more detail. Our first result uncovers a tight relationship between the chromatic number of the max-norm space avoiding a given integer baton and the maximum density C of the subset of the integers that avoids copies of the same baton (either the baton itself or its reflection). Namely, the former is equal to C^{-n+o(n)}. We note that such densities have been extensively studied in different contexts, and there are numerous reformulations and variants of such problems in terms of packings, coverings, tilings, blocking sets, avoiding sets, colorings etc. In particular, we understand pretty well the behavior of C for k-element batons as k tends to infinity. Furthermore, let us note that there is an algorithm that calculates the exact value of C for any given integer baton. However, the problem of finding the closed-form expression for C seems to be very hard in general. The problem is trivial for 2-element batons. We are going to study the case of 3-element batons in a separate paper. We also proved an extension of the `connecting’ result for not necessarily integer batons. In particular, for a set of numbers a_1,...,a_k that are linearly independent over Z, we get that the corresponding chromatic number grows as ((k+1)/k+o(1))^n. Next, we discuss results concerning Cartesian products, with a natural definition of metric as the maximum of the two distances. First, we managed to give a very precise upper and lower bounds on the chromatic number of powers of B_k. In particular, the bounds imply that it grows as ((k+1)/k+o(1))^n. We get such a sharp estimate for the chromatic number because we can determine the independence number of a certain relevant hypergraph exactly. One challenging problem that remains is to understand the behavior of the chromatic number of Cartesian products of different batons, and in particular if it is true that the base of the exponent would be the minimum of the two bases of exponents for the sets in the product. We could not resolve this question in general, however, we managed we resolve this conjecture in the particular case when all these batons are arithmetic progressions that may have different common differences. In particular, it implies that the chromatic number of the max-norm spaces grows as (2+o(1))^d when we forbid a Cartesian product of arbitrary 2-element sets, i.e., vertices of a box. Finally, we turn our attention to infinite forbidden metric spaces. In the Euclidean case the situation is simple: for any dimension n and any infinite metric space X, there exists a 2-coloring of the space with no monochromatic copy of X. In fact, a much stronger statement is true, see the work of Erdos et al. The picture in the max-norm turns out to be much more complicated. Observe that, unlike in the finite case, not all infinite X can be embedded into R_{\infty}^n for some n. However, we may assume without loss of generality that this is the case, otherwise the problem is trivial. First, we managed to show that, for any infinite metric space, the respective chromatic number in the max-norm is bounded by n+1. Moreover, this bound is tight for all geometric progressions with sufficiently small common multiple (depending on n). This result, however, does not show the existence of a single infinite metric space with chromatic number tending to infinity, or, in other words, it does not imply that an infinite l_\infty-Ramsey metric space exists. This is guaranteed by another theorem that we prove. However, we only managed to show the rate of growth that is logarithmic. Improving this bound to linear or at least polynomial is a challenging open problem. Covering the torus with cubes. We studied the problem of finding the minimum number of cubes with side c<1 needed to cover a d-dimensional torus [R/Z]^d for d=3. We have found exact values of the number of cubes in a covering for all c in [7/15,1). Moreover, for all integers k>1 we have found these values for all c between (k^3-1)/(k^4-1) and (k^2-1)/(k^3-k-1). To prove the results we have shown that the problem is equivalent to its discrete analogue: what is the minimum number of integer cubes with sides s that cover [Z/tZ]^d where s,t are chosen in a way such that s/t is close to c. Having this, we proved that in order to solve the initial problem it is sufficient to consider a countable set of values of c such that its intersection with any set [1/r,1/(r-1)] is finite. Monotonicity of the binomial random variable distribution function. The famous Samuels conjecture about probabilities of small deviations of sums of random variables from their expectations have direct corollaries in combinatorics - for example, for the conjecture of Erdos about matchings in uniform hypergraphs. In 2018, Zhukovskii (in joint work with D. Dmitriev) proved that the theorem of Samuels for random variables with 2 values and identical distributions is equivalent to a result about the maximum of the distribution function of a binomial random variable with parameters n and b/(n+c) at b. In the same paper, it was proven that, if c=0, then this function increases for n>3b+2 and decreases for n<3b+1. During the project, for every positive c at most 1 we have found an asymptotics of the point where the monotonicity (in b) of F(b) changes, where F is the CDF of a binomial random variable with parameters b and b/(n+c). Moreover, for c=1 we have proved that F(b) is strictly increasing. From the latter result we have derived a complete ranking of distributions of random variables in the theorem of Samuels in accordance to the probabilities of their deviations from the expectation (if the parameter in the theorem equals to 1). Tverberg graphs. Let G be a graph whose vertex set is a finite set of points in the Euclidean d-space. We say that G is a Tverberg graph if the intersection of balls induced by its edges is not empty. A perfect matching for an even set of points in the Euclidean d-space is called a Tverberg matching if it is a Tverberg graph. Analogously, a Hamiltonian cycle for a set of points in the Euclidean d-space is called a Tverberg cycle if it is a Tverberg graph. During the project, using the idea of halving lines, we have proved the following results: For any finite set of points in the plane, there exists a Tverberg cycle. For any set of n red points and n blue points in the plane, there exists a Tverberg red-blue matching. Also, using the method of infinite descent, we managed to show the following results: For any even set of distinct points in the Euclidean d-space, there exists an open Tverberg matching. For n red points and n blue points in the Euclidean d-space, there exists a red-blue Tverberg matching.

 

Publications

---

Annotation of the results obtained in 2022
We study problems connected to the famous Erdos’s problem about unit distances as part of the second year of the project. What is the maximum number of unit distances among n points on the plane? This question is far from being solved. However, in a dimension d > 3 it becomes much simpler. There exists non-trivial generalization of it for arbitrary dimension. Let C(d, k, n) be the maximum over all k-simplices S and subsets P ⊂ R^d, |P|=n, of isometric copies of S in P. The following conjecture was proposed by Erdös and Purdy: For all d > 3 and k <= d, we have C(d, k, n) = O_d(min{n^k, n^{d/2}}) if d is even, and C(d, k, n) = O_d(min{n^k, n^{d/2 - 1/6}}) if d is odd. This conjecture was also proposed by Agarwal and Sharir. Before our work, there was progress only for d < 7. We managed to prove the following: For any d > 3, k < d + 2 and epsilon > 0, we have C(d,k,n)=O_{d, epsilon}(n^{5d/8 + k/8 + epsilon}). In particular, we get C(d,k,n)=O_{d,epsilon}(n^{3d/4 + epsilon}) for any k < d + 1. As a corollary, we obtain new upper bounds on the number of homothetic simplices on n points in R^d. Our result significantly improves results of Agarwal, Apfelbaum, Purdy and Sharir, who proved a bound of the form O_d(n^{d-const}) for some small constant. It appears that C(d,k,n) does not change significantly when changing an arbitrary simplex to a unit simplex. However, there is another natural setup, in which the answer is significantly different. Let DIAM(d,k,n) be the maximum number of unit k-simplices on a set of diameter 1, which consists of n points in d-dimensional space. We managed to prove the following result: For each 1<k <d+2 and epsilon>0 we have DIAM(d,k,n)=O_{d,epsilon}(n^{d/2+epsilon}). In order to obtain these results, we used different probabilistic methods that allow to produce cuttings. For their efficient use, we needed to carefully analyze certain recurrence relations, that could be reduced to a class of linear programming problems. In order to study these linear programs, we needed to analyze their geometric meaning, as well as use different combinatorial methods. The next research topic was devoted to the study of random distance graphs, that is, random subgraphs of distance graphs G(n,r,s). Graph G(n,r,s) has vertices that are elements of {0,1}^n of weight r, and edges connect vertices with scalar product s. We proved, that in order for G(n,r,s) to have asymptotically the same number of simple cycles of length t as walks of length t is for a cycle size t=t(n) to satisfy t=o(min(N1/2,N1)), where N is the number of vertices in G(n,r,s) and N1 is the degree of a vertex in G(n,r,s) (the graph G(n,r,s) is regular, i.e., all vertices have the same degree). We also managed to obtain exact asymptotic expressions for the number of simple cycles of size t=o(min(N1/2,N1)) in G(n,r,s) under the assumption that t=t(n) falls inside certain intervals If t(n) is superlogarithmic, i.e., t>>ln(n), then the number of simple cycles is asymptotically N1t/(2t). If t(n) is logarithmic, i.e., t~c⋅ln(n), then, depending on c, the asymptotics of the number of simple cycles is described by different functions of certain form that we do not list here for clarity. In order to prove this, we use the spectrum of G(n,r,s). We also studied the number of disjoint pairs in geometric graphs. Concretely, we studied the following two questions: 1) Find the exact maximum of the edges in a geometric graph on n vertices, in which each edge is intersecting all but at most m others (for n significantly bigger than m). 2) Find the smallest d(e,n) such that for any geometric graph on n vertices and with e edges we have d(e,n) pairwise disjoint edges. In order to solve these problems, we used a rather complicated induction combined with the charging-decharging method. We managed to solve the first problem completely, while the second one we solved under the assumption that the vertices of the graph are in convex position. Besides the aforementioned problem, we also studied several other problems, mostly related to the properties of Kneser graphs and intersecting families. A family is intersecting if any two of its sets have non-empty intersection. Intersecting families play an important role in extremal set theory. A very important and common type of intersecting families are stars: all subsets that contain some fixed element. Let n > k > 0 be two integers. Consider intersecting families of k-subsets of {1, …, n}. In the paper “On the number of distinct differences in an intersecting family” Frankl showed that if n > k (k + 3) then for any intersecting family cF the family of its differences D(cF) = {F\F’ : F, F’ ∊ cF} has the largest cardinality if cF is a star. He also conjectured that this is true for any n > 2k. In this research project, we managed to give counterexamples to his conjecture and show that if n = c * k for some c ∊ (2, 4) and k is sufficiently large, then there is an intersecting family with a family of differences bigger than that for a star. Our main result in this direction is a proof of Frankl’s conjecture for n > 50 k ln(k) and k >= 50. A Kneser graph with parameters n,k is a graph which set of vertices consists of k-subsets of {1, …, n} and two subsets being connected by an edge if they do not intersect. We studied the choice number of such graphs. Fix an arbitrary s >= 3. We managed to show that ch(KG_{n,k})\ge 1/(2 s^2) n ln(n) if n is sufficiently large and 3 <= k <= n^{½ - 1/s}. If k = 2 then we showed that ch(KG_{n,2})\ge n ln(n) / 32 for sufficiently large n. The proof technique uses a certain variant of container method and a probabilistic argument. We also managed to obtain an upper bound: ch(KG_{n,k}\le n + n ln(n/k) for all n >= 2k > 0. Here, we used probabilistic method again. Finally, we studied metric problems of the following sort. Let M be a metric space. We studied the sizes of the largest sets with only odd distances, as well as the largest sequences of points that are right-equidistant. We call a sequence s_1, …, s_t right-equidistant if for any i < j < k we have d(s_i, d_j) = d(s_i, d_k). Previously, these characteristics were mostly studied for the Euclidean space. In this research project, we studied the cases of Manhattan and max-norm. In particular, we showed that 1) The maximum cardinality of a set with only odd distances in R^n with max-norm is equal to 2^n. 2) The maximum cardinality of a right-equidistant set in R^n with max-norm is 2^n - 1. 3) The maximum cardinality of a set with only odd distances in R^n with Manhattan metric is at least 4n - 1. 4) The maximum cardinality of a right-equidistant set in R^n with Manhattan metric is at most n! * n * ln(n) * (4 + o(1)).

 

Publications

---