INFORMATION ABOUT PROJECT,
SUPPORTED BY RUSSIAN SCIENCE FOUNDATION

The information is prepared on the basis of data from the information-analytical system RSF, informative part is represented in the author's edition. All rights belong to the authors, the use or reprinting of materials is permitted only with the prior consent of the authors.

 

COMMON PART


Project Number21-71-10092

Project titleExtremal problems on the interface of discrete probability and combinatorial geometry

Project LeadKupavskii Andrey

AffiliationMoscow Institute of Physics and Technology,

Implementation period 07.2021 - 06.2024 

Research area 01 - MATHEMATICS, INFORMATICS, AND SYSTEM SCIENCES, 01-114 - Discrete mathematics and mathematical cybernetics

KeywordsExtremal combinatorics, semi-algebraic graphs, coverings, hypergraphs, random graphs, quantifier depth, Euclidean Ramsey theory.


 

PROJECT CONTENT


Annotation
This proposal is devoted to a number of questions in mathematics and computer science that have extremal and Ramsey nature and appear on the interface of extremal graph and hypergraph theory, geometry, probabilistic method, and their applications. One of our main goals is to develop the ‘dialogue’ between these areas. In the current proposal we consider several promising directions connecting these areas of research that can be briefly characterized as follows: 1) Extremal properties of point configurations: maximization or minimization of the number of different patterns that may be formed by a subset of the point set, study of the structure of near-extremal examples. 2) Problems that appear on the interface of random graph theory, model theory, and algorithms on graphs. Connections to problems in extremal graph theory. 3) Higher-dimensional combinatorics: extremal questions for objects with rich geometric structure. 4) Geometric Ramsey-type problems, related problems on coverings and tilings and the use of probabilistic method. This project is at the interface of probability theory, discrete geometry and combinatorics, and it touches on some parts of theoretical computer science. There are numerous connections between these areas, which lead to several interesting and important developments. At the same time, it is clear that this area of research is still fruitful and that the explosive development of combinatorics and theoretical computer science supplies these fields with many novel ideas. For example, the development of the ideas of pseudorandomness lead to major progress in the central question of Ramsey theory, that of bounding diagonal Ramsey numbers. The idea of random restrictions in the context of DNF formulas lead to a breakthrough on the old question of Erdos and Rado on sunflowers, and further on thresholds of properties of random structures. Algebraic method in discrete geometry, developed over the last 10 years, allowed for a lot of recent results in the domain of point and line configurations. Therefore, we may conclude that this area of research is very active and has great potential. Below we list the problems that we are going to work on within the framework of this project (the numeration corresponds to the themes pointed out above): 1. Upper bounds in the question of Erdos and Purdy on the number of simplices congruent to a given one. A variant of this problem for diameter graphs. Problems that generalize Tverberg theorem for point sets on the plane, in terms of Tverberg graphs. Problem on the number of different directions determined by a point set, and, in particular, structural results for near-extremal configurations. Problem on the number of edges in the geometric graph on n vertices, in which each edge crosses all but at most m other edges. 2. Questions related to the conjecture of Samuels on the deviations of sums of random variables. Study of random frames. Upper and lower bounds on the size of a family that avoids projections of certain type. 3. Improving the existing upper and lower bounds on the maximum number of edges in a (d+1)-hypergraph that has no triangulation of a d-sphere. Bounds on the number of edges in semi-algebraic graphs that have no complete bipartite subgraphs. 4. Bounding the size of the largest subset of a cartesian product of linear sets (with the max-norm) that avoids isometric copies of certain metric spaces. Bounds on the respective chromatic numbers in the max-norm. Study of related covering problems in the spirit of Erdos-Rogers for 3-dimensional spaces. Study of the problem of partitioning the integer line into congruent tiles. Suggested methods and ideas to tackle these question reflect the essence of this project: they consist of a blend of geometric and probabilistic considerations, as well as ideas from theoretical computer science, with various combinatorial methods. In particular, we are going to use classical combinatorial methods, double counting, quasirandomness, supersaturation, algebraic and probabilistic methods in discrete geometry, methods of the theory of random graphs and additive combinatorics. All the proposed results are novel and would significantly contribute to the joint development of the areas in study. The research group has already obtained significant progress on related questions, as well as it has a lot of experience in joint projects.

Expected results
All the expected scientific results will correspond to the world level of research (will have a world novelty). These results will contribute significantly to advance the relevant scientific areas. Also they will have a significant impact on the development of more applied research in the field of computer science. In particular, the results obtained can become the basis for building more efficient algorithms for data analysis, image recognition, and other machine learning tasks, as well as for optimizing complex computations. The following scientific results are expected to be obtained: 1) Finding the maximum cardinality of a subset of a metric space [n]^d with max-norm that does not contain an arithmetic progression of length n with difference 1. Generalizing this result to different linear metric spaces and their Cartesian products. 2) For every positive integer k, we are going to construct (explicitly) a set C of `critical’ rational numbers c in (1/(k+1),1/k) of order k^4 such that the minimum number of cubes in a covering of the torus [R\Z]^3 changes when the length of edges of small cubes jumps through these values. We plan to find the exact solution of the task in case of a range of parameters. 3) A refinement the theorem of Samuels about small deviations of sums of independent identically distributed random variables with 2 values, which will allow us to get an ordering of such distributions with respect to the values of the probabilities of the small deviations. 4) Checking that it is true that for any even set of points there is a Hamiltonian cycle that is a Tverberg graph. 5) Obtaining new upper bounds in the conjecture of Erdos and Purdy of the form n^{cd}, where c<1. 6) Solving the problem of Erdos and Purdy for diameter graphs, i.e., the aforementioned problem for point sets with diameter 1. 7) Obtaining upper and lower bounds on the sizes of families with no projections on subsets of size 4 that contain 4-cycles. 8) Proving that modal formulae that are almost sure valid for binomial random frames with probability parameter p can not be finitely axiomatized over the set of all extension axioms for almost all p. 9) Proving Jamison’s conjecture in the case when n points in general position determine n+O(\sqrt{n}) directions. We plan to show that in this case the points lie on a quadric and, moreover, they are vertices of an affine image of a certain regular m-gon. 10) Obtaining new upper bounds on the number of semi-algebraic graphs with no complete bipartite subgraphs with sizes of parts equal to t, where t is growing polynomially with the number of vertices. 11) Obtaining better upper and lower bounds on the number of edges in (d+1)-uniform hypergraphs with no triangulation of a d-sphere. 12) The solution of the Schmidt-Tuller problem on the optimal covering of the line by translations of a fixed three-point tile. 13) Finding the tight bound on the maximum number of edges in a geometric graph on n vertices such that every edge intersect all other edges but at most m (in the case when n is much larger than m). 14) Getting new upper and lower bound on the size of a set family that satisfies the following bipartite analogue of the VC-dimension property: none of its projections on 2m-element sets contains a complete m-partite hypergraph with parts of size 2.


 

REPORTS


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

1. Peter Frankl, Sergei Kiselev, Andrey Kupavskii On the maximum number of distinct intersections in an intersecting family Discrete Mathematics, Том 345, Выпуск 4, Номер статьи 112757 (year - 2022).

2. Volkov N.A., Dmitriev D.I., Zhukovskii M.E. О поведении биномиального распределения вблизи медианы / BEHAVIOUR OF BINOMIAL DISTRIBUTIONS NEAR ITS MEDIANS ДОКЛАДЫ РОССИЙСКОЙ АКАДЕМИИ НАУК. МАТЕМАТИКА, ИНФОРМАТИКА, ПРОЦЕССЫ УПРАВЛЕНИЯ / Doklady Mathematics, - (year - 2022).

3. Bogdanov I.I., Grigoryan O.R., Zhukovskii M.E. О покрытии тора кубами / ON COVERINGS OF TORI WITH CUBES ДОКЛАДЫ РОССИЙСКОЙ АКАДЕМИИ НАУК. МАТЕМАТИКА, ИНФОРМАТИКА, ПРОЦЕССЫ УПРАВЛЕНИЯ / Doklady Mathematics, - (year - 2022).