We use cookies.
By using the site, you agree to our Privacy Policy.

Laboratory for Combinatorial and Geometrical Structures

Contract number
075-15-2019-1926
Time span of the project
2019-2021

As of 01.11.2022

24
Number of staff members
75
scientific publications
1
Objects of intellectual property
General information

Name of the project: Combinatorics, computational geometry and analysis of complex structures

Goals and objectives

Project objective: Creation of a new world-class laboratory on the grounds of the Moscow Institute of Physics and Technology to study combinatorics, discrete and computational geometry as well as their applications to machine learning, statistical physics, computer visitors and information search

The practical value of the study

Scientific results:

In 2019 – 2021, we obtained a number of results in the field of extremal, probabilistic and additive combinatorics as well as discrete and computational geometry. In particular, we obtained a positive answer to Linial’s conjecture on the threshold for the existence of the torus in the 3-uniform hypergraph, we solved the problem of the polynomial growth of VC-dimensionality for a class of k-vertex polygons, obtained various extremal results with regards to families of sets and vectors. We proved a generalization of Janson's inequality, demonstrated the possibility of its use in some problems of the distribution of powers in a random graph. We have obtained a proof of Aharoni and Howard’s conjecture at new values of parameters. We proved new statements on a           for shifted families with explicit dependencies on input parameters, this approach was applied to prove the almost linear estimate in the Erdős conjecture on matchings for several families. We have obtained a recurrent formula for the power of the maximum family of n-dimensional vectors all of whose coordinates are equal to 0, 1 or -1 at a fixed number of coordinates of every type and a limitation on the scalar product. In 2022, the Laboratory continued its work on several research problems. The achieved results can be summarized as follows: (a) a study of problems of Ramsey's theorem, grid coverage and coloring and for the max-norm, (b) a study of the Tverberg-type properties for finite sets of points, (c) a study of graph-theory characteristics of unit distance graphs in high dimensionalities, (d) a study of new and classical problems of extremal combinatorics (families of sets with minor intersections, the Erdős matching conjecture etc.), (e) a study of anti-stochastic properties of graphs.

Implemented results of research:

The obtained scientific results are aimed at the development of fundamental mathematics in the domain of combinatorics and discrete geometry, they have a lot of applications in applied problems of machine learning, information search etc. We are developing methods of the regularization of solutions that will allow to build unbalanced models.

Education and career development:

Two education programs have been developed for master’s degree students: «Methods of information protection» and «Advanced methods of modern combinatorics».

Undergraduate and postgraduate students have completed internships at leading universities and research organizations in Hungary and Austria.

The Laboratory has successfully prepared one Doctor of Sciences and 6 Candidates of Sciences dissertations in our area of studies.

9 master’s degree students have been prepared for graduation and later enrolled in the postgraduate school, one bachelor’s degree student entered the master’s degree program. We have conducted a considerable number of international events (in-person conferences, online conferences, workshops) on combinations, discrete geometry and related issues involving the most prominent world-class experts.

Organizational and infrastructural transformations:

On the basis of the Laboratory, with support from the organization, we have created a computational cluster equipped with a special high-performance computer – servers and computational workstations with powerful video cards. We have renovated the Laboratory premises, purchased modern office equipment that ensures efficient in-person and remote work of the employees of the Laboratory in the context of the existing limitations for traveling abroad.

Collaborations:

  • Alfréd Rényi Institute of Mathematics (Budapest, Hungary): joint research, publications and internships of students.
  • Eötvös Loránd University (Budapest, Hungary): internships of students.
  • Technion — Israel Institute of Technology (Haifa, Israel): joint research and publications.
  • University of Neuchâtel (Neuchâtel, Switzerland): joint research and publications.

Hide Show full
g ivanov, m naszódi, a polyanskii
Approximation of the average of some random matrices. Journal of Functional Analysis. 2020, октябрь, Том: ‏ 279, Выпуск: 7, Номер статьи: 108684 (Q1)
kupavskii, a., zakharov, d.
The right acute angles problem? European Journal of Combinatorics. 2020, октябрь, Том: 89, Номер статьи: 103144 (Q2)
andreas f. holmsen, hossein nassajian mojarrad, jános pach, gábor tardos:
When are epsilon-nets small? Journal of Computer and System Sciences. 2020, июнь, Том: ‏ 110, Стр. ‏ 22-36(Q2)
a b kupavskii, a a sagdeev
Two extensions of the Erdos-Szekeres problem. Journal of the European Mathematical Society. 2020, Том: 22, Выпуск: ‏ 12, Стр. ‏ 3981-3995(Q1)
r zhang, m e zhukovskii, m i isaev, i v rodionov
Ramsey theory in a space with Chebyshev metric. Russian Mathematical Surveys. 2020, Том: 75, Выпуск: 5, стр. 965 (Q1)
a. kupavskii
Extreme value theory for triangular arrays of dependent random variables. Russian Mathematical Surveys. 2020, Том: 75, выпуск 5 (455), стр. 193–194 (Q1)
michael th. rassias, bicheng yang and andrei raigorodskii:
The VC-dimension of k-vertex d-polytopes. Combinatorica. 2020, Том: 40, стр. 869-874 (Q2)
frankl, p
On a More Accurate Reverse Hilbert-Type Inequality in the Whole Plane. Journal of Mathematical Inequalities. 2020, Том: 14, стр. 1359–1374 (Q1)
kupavskii a., polyanskii a., tomon i., zakharov d.
On the size of shadow-added intersecting families. European Journal of Combinatorics. 2021, February, Volume 92, Номер статьи 103243 (Q2)
Other laboratories and scientists
Hosting organization
Field of studies
City
Invited researcher
Time span of the project
Laboratory «Probability techniques in analysis» (10)

Saint Petersburg State University - (SPbU)

Maths

St. Petersburg

Hedenmalm Haakan Per

Sweden

2024-2028

Laboratory «Nonlinear and nonlocal equations and their applications»

Peoples' Friendship University of Russia - (RUDN University)

Maths

Moscow

Kuksin Sergei Borisovich

Russia, France

2022-2024

Probabilistic Methods in Analysis

Saint Petersburg State University - (SPbU)

Maths

St. Petersburg

Hedenmalm Haakan Per

Sweden

2021-2023