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.



Project Number22-11-00131

Project titleAlgebraic and random combinatorial structures

Project LeadPetrov Fedor

AffiliationFederal State Budgetary Educational Institution of Higher Education "Saint-Petersburg State University",

Implementation period 2022 - 2024 

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

Keywordsrandom graphs, extremal statistics, asymptotic independence, extremal set theory, saturation, matchings, intersecting families, algebraic graph theory, additive combinatorics, tensor rank, matroids, polynomial method



Combinatorics is one of the most intensively developed areas of mathematics, which is due to both the internal logic of its development and numerous applications - both within mathematics and in related areas (primarily computer science). The project is intended to unite the efforts of established and actively working teams in St. Petersburg and at the Moscow Institute of Physics and Technology dealing with both algebraic methods in combinatorics (spectral graph theory, polynomial method) and probabilistic methods (random graphs, extremal combinatorics). The existing solid background allows us to expect new serious results.

Expected results
Lower bounds on the size or measure of a sum of sets play a key role both in convex geometry (the Brunn - Minkowski inequality, etc.) and in additive combinatorics (the Cauchy - Davenport theorem, Freiman's theorem, etc.) Moreover, these theories are weakly connected and develop in many ways independently. One of the objectives of the project is to construct a way to approximate a finite set by continuous one so as to reduce, for example, the problem of estimating the size of sums of the form A+T(A), where A is a set in an Abelian group, T is its endomorphism (for example, multiplication by a number) to a similar problem on measures of compact sets. The corresponding theory should have many other applications as well. Unlike the matrix rank, which is quickly calculated and has a clear meaning, the tensor rank for tensors of order 3 or more behaves mysteriously and little is known about it. One of the basic results is the classical Kruskal theorem, which provides a sufficient condition for a given decomposition of a tensor into a sum of rank 1 tensors to be minimal (so called minimal tensor rank decomposition). One of the goals of the project is to generalize this theorem in a number of directions using the combinatorial technique of the structural theory of matroids. Alon's Combinatorial Nullstellensatz, which connects the values ​​of a polynomial on a grid with its coefficients, has many important applications. It is expected to obtain a generalization of this statement to the case of more complex sets than grids. An important test question here is the Macdonald identities for root systems. In computer science, information technologies, biology and social sciences, practical problems related to verification of properties of large networks appear frequently. Even polynomial problems (such as the classical subgraph isomorphism problem) appear to be hard (in the worst case) when networks are very large. However, it is much more useful to efficiently solve problems on typical graphs, not in the worst case. Therefore, a fundamental question about a graph characteristic is the question about its asymptotic behavior on a typical graph. Formally, we are interested in asymptotic distribution of characteristics of random graphs and asymptotic probabilities of graph properties. We expect to solve the following problems: find the exact asymptotic distribution of some extremal statistics related to extensions in binomial random graphs and random graphs with a given degree sequence; find the minimum probability of a graph property such that changing one adjacency is enough to get the property. These questions are open, the related problems were studied by hundreds outstanding researchers in extremal combinatorics, random graphs and coding theory (among them M. Krivelevich, B. McKay, J. Spencer, B. Sudakov, L. Warnke, N. Wormald, G.A. Kabatianskii and many others). We plan to obtain several results in the domain of extremal set theory, connected to different properties of the so-called Kneser graphs, as well as to the effect of measure concentration of the values of random variables in combinatorial setting. In particular, this is applicable to the intersection with a random matching random variable. In general, different effects related to random restrictions of families are fruitful for combinatorics in general and extremal set theory in particular. We plan on strengthening the existing results in the field, as well as find their new applications to several problems in extremal set theory. In particular, we plan to use them in the question of minimizing the number of disjoint pairs, as well as to maximizing the number of differences and symmetric differences. Developing such methods is fundamental and important for extremal combinatorics. We also note that extremal set theory results play an important role in theoretical computer science. The next question belongs both to the theory of classes of graphs defined by a finite number of prohibited induced subgraphs, and to spectral graph theory. Namely, we are going to describe the spectral properties of graphs defining such classes, which is a continuation of the recent work of Jiang and Polyansky. All indicated results correspond to the world level.