Laboratory for Combinatorial and Geometrical Structures

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.