Combinatorics and Geometry Days II at MIPT

Combinatorics and Geometry Days II

at MIPT
April 13 - 14, 2020
Online

The conference aims to be a meeting point for combinatorialists and geometers, where they will be able to present and discuss their current research, as well as give broader scope lectures accessible to interested PhD and master students.

Speakers

Danila Cherkashin Saint Petersburg State University, Spb Oleg German MSU, Moscow Alexander Guterman MSU, Moscow Nora Frankl London School of Economics, UK and MIPT, Moscow Grigory Ivanov TU Wien, Austria and MIPT, Moscow Grigory Kabatiansky (tentatively) Skoltech, Moscow Nikita Kalinin HSE and Saint Petersburg State University, Spb Márton Naszódi Alfréd Rényi Institute of Mathematics and Eötvös University, Hungary Konstantin Olmezov MIPT, Moscow Balázs Patkós Alfréd Rényi Institute of Mathematics, Hungary and MIPT, Moscow
Rom Pinchasi (tentatively) Technion, Israel and MIPT, Moscow Ilya Shkredov Steklov Mathematical Institute, MSU and MIPT, Moscow Anna Taranenko Sobolev Institute of Mathematics, Novosibirsk Gábor Tardos Alfréd Rényi Institute of Mathematics, Hungary and MIPT, Moscow István Tomon ETH Zurich and MIPT, Moscow Ilya Vorobev Skoltech, Moscow Dmitry Zakharov HSE and MIPT, Moscow Maksim Zhukovskii MIPT, Moscow Yelena Yuditsky Ben-Gurion University of the Negev, Israel
Alexandr Polyanskii MIPT Andrei Raigorodskii MIPT Idzhad Sabitov Moscow State University Andrey Sergunin MIPT Dmitriy Shabanov MIPT and Moscow State University

Abstracts

Here are the topics and abstracts of some talks.
Konstantin Olmezov MIPT, Moscow
An elementary approach to the operator method in additive combinatorics
Room: 424 Arctica

The additive energy $E(A)$ of a finite set $A$ from an abelian group is the number of solvings $$a+b=c+d,\ a,b,c,d \in A.$$ Finding the upper bounds for the additive energy of sets from some given classes is very popular subject of additive combinatorics. In 2012 Shkredov provided operator method that allows to estimate $E(A)$ via bounding of so-called higher energy $$E_3(A) := \# \{ a_1 - b_1 = a_2 - b_2 = a_3 - b_3 \ :\ a_i, b_i \in A,\ i=1,2,3 \}$$ and the common energy $$E(A, D) = \# \{ a_1 - d_1 = a_2 - d_2 \ :\ a_i \in A,\ d_i \in D,\ i=1,2 \}$$ for an arbitrary $D \subset A-A$. He uses the properties of the operator $$T_A(x,y) = (A \circ A)(x-y) = \# \{ a-b=x-y\ :\ a,b \in A \}$$ for obtain a certain very general inequality to the number of the solutions of two linear equation systems.

We suggest an elementary approach to prove this inequality which gives an elementary proof of the corresponding bounds of $E(A)$ (in particular, for the family of convex sets and the collection of sets having few products).

Also we discuss a generalization of this inequality (which is elementary as well) connecting with the Sidorenko's conjecture from graph theory. Sidorenko's conjecture states that for any bipartite graph $H$ and any graph $G$ we have $$t_H(G) \le t_{K_2}(G)\ ,$$ where $t_H(G) = \frac{h_H(G)}{|G|^{|V(H)|}}$ and $h_H(G)$ is the number of homomorphisms from $H$ to $G$.

We consider a special case of the graph $G$ which is defined in the terms of convolutions of $A$ and prove the required bound for many non-bipartite graphs $H$.

Anna Taranenko Sobolev Institute of Mathematics, Novosibirsk
Hypergraph matching problems and multidimensional matrices
Room: 424 Arctica

The talk aims to draw attention to the interplay between the hypergraph matching theory and the theory of diagonals in multidimensional matrices. We overview some classical or just nice results on existence and counting matchings in hypergraphs and see how the matrix approach works for them. In particular, we discuss matchings in d-partite d-graphs, the Ryser's conjecture and other generalizations of the Hall's theorem, upper bounds on the numbers of perfect matchings, and extremal cases for the existence of perfect matchings in hypergraphs known as space and divisibility barriers.

István Tomon ETH Zurich and MIPT, Moscow
String graphs have the Erdős-Hajnal property
Room: 424 Arctica

A string graph is the intersection graph of curves in the plane. Building on previous works of Fox and Pach [1, 2], we prove that there exists an absolute constant $c>0$ such that if $G$ is a string graph on $n$ vertices, then $G$ contains either a clique or an independent set of size at least $n^c$.

[1] J. Fox and J. Pach, Erdős-Hajnal-type results on intersection patterns of geo-metric objects, in Horizons of combinatorics, G. O. H. Katona et al., eds., Bolyai Soc. Stud. Math. 17, Springer, Berlin, Heidelberg, (2008), 79—103.

[2] J. Fox and J. Pach, String graphs and incomparability graphs, Advances in Mathematics 230 (2012), 1381—1401.

Yelena Yuditsky Ben-Gurion University of the Negev, Israel
The $\varepsilon$-$t$-Net Problem
Joint work with Noga Alon, Bruno Jartoux, Chaya Keller and Shakhar Smorodinsky
Room: 424 Arctica

We study a natural generalization of the classical $\varepsilon$-net problem (Haussler--Welzl 1987), which we call the $\varepsilon$-$t$-net problem: Given a hypergraph on $n$ vertices and parameters $t$ and $\varepsilon\geq \frac t n$, find a minimum-sized family $S$ of $t$-element subsets of vertices such that each hyperedge of size at least $\epsilon n$ contains a set in $S$. When $t=1$, this corresponds to the $\varepsilon$-net problem.

We prove that any sufficiently large hypergraph with VC-dimension $d$ admits an $\varepsilon$-$t$-net of size $O(\frac{ (1+\log t)d}{\varepsilon} \log \frac{1}{\varepsilon})$. For some families of geometrically-defined hypergraphs (such as the dual hypergraph of regions with linear union complexity), we prove the existence of $O(\frac{1}{\varepsilon})$-sized $\varepsilon$-$t$-nets.

We also present an explicit construction of $\varepsilon$-$t$-nets (including $\varepsilon$-nets) for hypergraphs with bounded VC-dimension. In comparison to previous constructions for the special case of $\varepsilon$-nets (i.e., for $t=1$), it does not rely on advanced derandomization techniques. To this end we introduce a variant of the notion of VC-dimension which is of independent interest.

Schedule

Here is the preliminary schedule for the conference.
April 13
9.40 - 10.20
Alexander Guterman MSU, Moscow
TBA
Room: 424 Arctica

10.30 - 11.10
István Tomon ETH Zurich and MIPT, Moscow
String graphs have the Erdős-Hajnal property
Room: 424 Arctica

A string graph is the intersection graph of curves in the plane. Building on previous works of Fox and Pach [1, 2], we prove that there exists an absolute constant $c>0$ such that if $G$ is a string graph on $n$ vertices, then $G$ contains either a clique or an independent set of size at least $n^c$.

[1] J. Fox and J. Pach, Erdős-Hajnal-type results on intersection patterns of geo-metric objects, in Horizons of combinatorics, G. O. H. Katona et al., eds., Bolyai Soc. Stud. Math. 17, Springer, Berlin, Heidelberg, (2008), 79—103.

[2] J. Fox and J. Pach, String graphs and incomparability graphs, Advances in Mathematics 230 (2012), 1381—1401.

11.20 - 12.00
Dmitry Zakharov HSE and MIPT, Moscow
TBA
Room: 424 Arctica

12.00 - 13.00
Break
13.00 - 13.30
Nora Frankl London School of Economics, UK and MIPT, Moscow
TBA
Room: 424 Arctica

13.40 - 14.10
Oleg German MSU, Moscow
TBA
Room: 424 Arctica

14.20 - 14.50
Márton Naszódi Alfréd Rényi Institute of Mathematics and Eötvös University, Hungary
TBA
Room: 424 Arctica

14.50 - 15.20
Break
15.20 - 15.50
Grigory Ivanov TU Wien, Austria and MIPT, Moscow
TBA
Room: 424 Arctica

16.00 - 16.30
Nikita Kalinin HSE and Saint Petersburg State University, Spb
TBA
Room: 424 Arctica

April 14
9.40 - 10.20
Gábor Tardos Alfréd Rényi Institute of Mathematics, Hungary and MIPT, Moscow
TBA
Room: 424 Arctica

10.30 - 11.10
Maksim Zhukovskii MIPT, Moscow
TBA
Room: 424 Arctica

11.20 - 12.00
Balázs Patkós Alfréd Rényi Institute of Mathematics, Hungary and MIPT, Moscow
TBA
Room: 424 Arctica

12.00 - 13.00
Break
13.00 - 13.30
Danila Cherkashin Saint Petersburg State University, Spb
TBA
Room: 424 Arctica

13.40 - 14.10
Yelena Yuditsky Ben-Gurion University of the Negev, Israel
The $\varepsilon$-$t$-Net Problem
Joint work with Noga Alon, Bruno Jartoux, Chaya Keller and Shakhar Smorodinsky
Room: 424 Arctica

We study a natural generalization of the classical $\varepsilon$-net problem (Haussler--Welzl 1987), which we call the $\varepsilon$-$t$-net problem: Given a hypergraph on $n$ vertices and parameters $t$ and $\varepsilon\geq \frac t n$, find a minimum-sized family $S$ of $t$-element subsets of vertices such that each hyperedge of size at least $\epsilon n$ contains a set in $S$. When $t=1$, this corresponds to the $\varepsilon$-net problem.

We prove that any sufficiently large hypergraph with VC-dimension $d$ admits an $\varepsilon$-$t$-net of size $O(\frac{ (1+\log t)d}{\varepsilon} \log \frac{1}{\varepsilon})$. For some families of geometrically-defined hypergraphs (such as the dual hypergraph of regions with linear union complexity), we prove the existence of $O(\frac{1}{\varepsilon})$-sized $\varepsilon$-$t$-nets.

We also present an explicit construction of $\varepsilon$-$t$-nets (including $\varepsilon$-nets) for hypergraphs with bounded VC-dimension. In comparison to previous constructions for the special case of $\varepsilon$-nets (i.e., for $t=1$), it does not rely on advanced derandomization techniques. To this end we introduce a variant of the notion of VC-dimension which is of independent interest.

14.20 - 14.50
Ilya Vorobev Skoltech, Moscow
TBA
Room: 424 Arctica

14.50 - 15.20
Break
15.20 - 15.50
Anna Taranenko Sobolev Institute of Mathematics, Novosibirsk
Hypergraph matching problems and multidimensional matrices
Room: 424 Arctica

The talk aims to draw attention to the interplay between the hypergraph matching theory and the theory of diagonals in multidimensional matrices. We overview some classical or just nice results on existence and counting matchings in hypergraphs and see how the matrix approach works for them. In particular, we discuss matchings in d-partite d-graphs, the Ryser's conjecture and other generalizations of the Hall's theorem, upper bounds on the numbers of perfect matchings, and extremal cases for the existence of perfect matchings in hypergraphs known as space and divisibility barriers.

16.00 - 16.30
Kostiantyn Olmezov MIPT, Moscow
TBA
Room: 424 Arctica

Location

The conference will be held online.

To attend the conference, please email Irina (kupavskaia.io@mipt.ru) so that we keep you informed and send invitations for online events of the conference.

Organisers

Andrey Kupavskii MIPT Alexandr Polyanskii MIPT Andrei Raigorodskii MIPT