Annotation of the results obtained in 2022
The following results were obtained. Taken together, they significantly exceed our expectations for the first year. Let us briefly present the main mathematical results obtained in the framework of the project. A graph with weights on edges equal to plus or minus 1 is called edge-dominated if for each edge the sum of its weight and the weights of all adjacent edges is positive. The lower bound on the sum of weights of all edges in an edge-dominated graph on n vertices is improved to -1/30 n^2. Consider a disc of unit diameter in the plane. Let a collection of other congruent disks touch the original one; call this group the first layer. Let another group of disks touch some disks of the first layer, call this group the second layer; and so on. If the number of layers is n, and no two disks have a common interior point, then we are interested in the largest possible number of disks. We have proved the hypothesis of Laszlo Fejes Toth that if n=3 this number is 37. Consider a set of n decomposable 3-tensors x_i\otimes y_i\otimes z_i, where x_i, y_i, z_i are chosen from some linear spaces X,Y,Z over the field K. Suppose that for any k=1,...,n a linear combination of any k 2-tensors of the form y_i\otimes z_i with nonzero coefficients has a rank at least min(k,n-d+2), where d is the dimension of the span of vectors x_i. In addition, suppose that all x_i are nonzero and no two of them are proportional. Then the sum of all n of our tensors cannot be represented as a sum of less than n decomposable tensors, and the representation as a sum of n decomposable tensors is unique. A graph property is a set of graphs closed with respect to isomorphism. It is called anti-probabilistic if the fraction of graphs on n vertices for which this property is satisfied tends to 0 with increasing n, but the fraction of graphs where it is enough to change just one edge for this property to be satisfied tends to 1. If we get rid of the closedness requirement with respect to isomorphism, we know from the works of Kabatianskii and Panchenko that the minimum probability of this property is asymptotically equal to 2/n^2. We managed to prove that the same asymptotics is also true for imposing the closedness requirement with respect to isomorphism - the asymptotics of the lowest probability of anti-likelihood property is 2/n^2, where n is the number of vertices of the graph. Moreover, we have proved a lower (1/n lnn) and an upper (2/n ln n) estimate of the asymptotics of the probability of the anti-likelihood property expressed purely in terms of the sequence of degrees of the graph. A family of graphs F is said to possess the property of FNFIS (presence of a finite number of forbidden induced subgraphs characterizing this family) if for some finite family of graphs H the family F consists exactly of graphs having no induced subgraphs from H. We explicitly described all m for which the family of graphs with the smallest eigenvalue at least -m has the property of FNFIS. We also extrapolated this approach and applied it to graphs with signs. In particular, we found those m for which the family of sign graphs with the largest eigenvalue not exceeding m enjoys the FNFIS property. We also described a set of such m that there exists n such that if a symmetric matrix with integer elements and zero diagonals has all eigenvalues not exceeding m, then there will be a principal minor of size n with eigenvalues not exceeding m. We also found a connection with the problem of the number of points in a set with two fixed distances. Erdos asked for the maximum size of a family of k-element subsets in the set of the first n natural numbers which do not contain s-matchings. Erdos suggested a particular kind of these families. When n is relatively large compared to sk, this extremum must be reached on the family of all k-element sets containing one of the s-1 first natural numbers. But when sk is close to n, i.e. the pairing covers almost all elements of the base set, then the family of all k-element subsets of the set {1,...,sk-1} should be the family of extremum, according to the hypothesis. Note that its size does not depend on n. We established the validity of this hypothesis in the range sk<=n<=(k+1/100k)s and s>101k^3. A new generalization of the Combinatorial Nullstellesatz was formulated, and we show how the main results of recent work by B. Nica and analogous generalizations of the combinatorial null theorem in the case of multiple roots follow from it. Let the function f_c(n, r) denote the largest number f such that for any graph on f vertices in which the chromatic number of any neighborhood of radius r does not exceed c, the chromatic number of the whole graph does not exceed n. Given a fixed n, a polynomial (with respect to r) estimate on f_c(n, r) of degree [(n - 1)/(c - 1)] was known. In the framework of the project we obtained a series of examples showing the accuracy of the exponent [(n - 1)/(c - 1)]; in particular, it follows that for values of the form n = k(c-1) + 1 this exponent "jumps" by 1. More exactly, we constructed a graph on O((2r)^{k-1}c^k) vertices, where the chromatic number of any neighborhood of radius r is not greater than c, and the chromatic number of the whole graph is not smaller than k(c -1) + 1. Let g(n) be the greatest value of the least common multiple of several natural numbers whose sum does not exceed n, provided that these numbers are differences of some pairwise non-intersecting bi-infinite integer arithmetic progressions. We proved that log^3 g(n) behaves like (1/4+o(1)) n log^{2} n. We proved that if A is a set consisting of n real numbers, then the minimal value of |A+sqrt(2)A| is (3+2sqrt(2)+o(1))n. We obtain an answer to the question about the exact lower bound of the measure of sets of the form A+TA, where T is a given linear endomorphism in R^n and A is a compact set of unit measure: this exact bound is prod(1+|lambda_i|), where lambda_i's are the eigenvalues of the operator T.

 

Publications

---

Annotation of the results obtained in 2023
A covering number of a family is the size of the smallest set intersecting all sets of the family. Let F be an intersecting subfamily in the downward closed family D. Suppose that the covering number of F is two. Then the size of F does not exceed the size of a largest star in D (a star is a family of sets with non-empty intersection). We obtain the convergence of the scaled maximum number of symmetric extensions in sufficiently dense random graphs to a non-degenerate distribution (a limit distribution may not belong to the family of Gumbel distributions). The saturation numbers of Kneser graphs for the triangle pattern were studied. Namely, exact values were found for small Kneser graphs, and the asymptotic behavior of the saturation numbers of Kneser graphs was also found. Andy Fingerhut's hypothesis has been proven. Namely, for an even set of points on the plane, consider a perfect matching that maximizes the sum of Euclidean distances between edges. For each edge of this matching, consider the ellipse with foci at the edge vertices and the eccentricity \sqrt{3}/2. Then the convex sets bounded by these ellipses have a non-empty intersection. It is shown that a degree (vertex) enumerator of spanning trees of a connected weighted graph G (with complex coefficients) is a stable polynomial if and only if G can be obtained from a graph with one vertex by weight-preserving copying of vertices (with or without adding an edge of arbitrary positive weight), gluing of two weighted stable graphs by the common vertex and multiplying the weights of all edges emanating from one vertex by a positive number, as well as multiplying all weights of the edges of the graph by some (complex) constant. Consider a class of signed edge-dominated graphs such that any edge connecting vertices with positive and negative sums of adjacent edge weights has weight -1. Then the sum of weights of edges in such a graph on n vertices is at least (3 - 2sqrt(2))n^2, and this estimate is asymptotically exact. It is proven that for an integer algebraic t the lower limit of the ratio |A+tA|/|A| is equal to the product |a_i|+|b_i|, where the product of the factors (a_i*x+b_i) is the complete factorization over the field of complex numbers of a minimal irreducible polynomial over the ring of integers with root t.

 

Publications

---