Probabilistic Combinatorics Online 2020 at MIPT

Random structures play a crucial role in combinatorics, with links to theoretical computer science, statistical physics, study of social networks, the spread of epidemics. The workshop will bring together experts in the area, providing a venue for sharing ideas and, in particular, exposing postgraduate students to cutting edge international research.

The workshop is organised by the Laboratory of Combinatorial and Geometric Structures, the Laboratory of Advanced Combinatorics and Network Applications at MIPT (Russia) and Monash University (Australia).

Important Dates

PCO’20 will be held on September 23-25, 2020 balancing time slots that are easier to attend from European time zones on the one hand and from North and South American time zones on the other hand.

For more details visit workshop webpage:


All of the talks will be held on the zoom meeting:

Meeting ID: 303-932-461
Password: first 6 decimal places of $\pi$

Also there will be 2 zoom chat-rooms for different discussions. You are welcome to register in conference slack account to be able to see the discussions in groups and join them when you like.

Alternatively, you can watch the live stream on our Twitch channel. No registration necessary.


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 Skoltech, Moscow Nikita Kalinin HSE and Saint Petersburg State University, Spb Vassily Manturov BMSTU, Moscow 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
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 Vorobyev Skoltech, Moscow Konstantin Vorob'ev Sobolev Institute of Mathematics, Novosibirsk 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 Rom Pinchasi (tentatively) Technion, Israel and MIPT, Moscow


Here is the preliminary schedule for the conference.
April 13
Section 1 chaired by Alexandr Polyanskii
15.10 - 15.30 MSK (UTC +3)
Ilya Vorobyev Skoltech, Moscow
Multistage group testing algorithms
Room: 424 Arctica
Video Slides

Group testing is a well-known search problem that consists in detecting of $s$ defective members in a set of $t$ elements by carrying out tests on properly chosen subsets. A test result is positive if there is at least one defective element in a tested subset; otherwise, the result is negative. Our goal is to find all defective elements by using the minimal possible number of tests in the worst case.

Two types of algorithms are usually considered in group testing. Adaptive algorithms can use results of previous tests to determine which subset of samples to test at the next step. In non-adaptive algorithms all tests are predetermined and can be carried out in parallel.

We consider multistage algorithms, which can be seen as a compromise solution to the group testing problem. The advantage of this approach is that we can greatly reduce the total number of tests, but still perform a lot of them in parallel. Our general goal is to construct a multistage search procedure, having asymptotically the same number of tests as an adaptive one. We propose such algorithms for $s=2, 3$.

15.40 - 16.10 MSK (UTC +3)
Danila Cherkashin Saint Petersburg State University, Spb
Maximal distance minimizers for rectangle
joint work with A. Gordeev, G. Strukov and Y. Teplitskaya
Room: 424 Arctica
Video Slides

Fix a compact $M \subset \mathbb{R}^2$ and $r>0$. Maximal distance minimizer is a connected set $\Sigma$ of the minimal length such that $$ \max_{y \in M} dist(y,\Sigma) \leq r,$$ i.e. $M \subset B_r(\Sigma)$.

We determine the set of maximal distance minimizers for rectangle and small enough $r$.

Theorem. Let $M$ be a rectangle, $0 < r < r_0(M)$. Then maximal distance minimizer is unique (up to symmetries of $M$). It is depicted on the picture below (the right part of the picture contains enlarged fragment of the minimizer; the marked angle tends to $\frac{11\pi}{12}$ with $r\to 0$).

16.20 - 16.40 MSK (UTC +3)
Maksim Zhukovskii MIPT, Moscow
Weak saturation in sparse random graphs
joint work with Mohamad Reza Bidgoli
Room: 424 Arctica
Video Slides

The notion of weak saturation was introduced in 1968 by Bollobas. Let $H$ be a spanning subgraph of a graph $G$, and $F$ be a pattern graph. $H$ is called weakly $F$-satured in $G$, if the edges of $G\setminus H$ may be added back one by one in a way such that every edge creates a new copy of $F$. The smallest number of edges in a weakly $F$-satured graph in $G$ is called a weak saturation number and is denoted by w-sat$(G,F)$.

Bollobas conjectured that w-sat$(K_n,K_s)=(s-2)n-{s-1\choose 2}$. This conjecture was proved by P. Frankl in 1982. Unexpectedly, w-sat is stable: if we remove edges from $K_n$ independently with constant probability, the weak saturation number does not change. This result was proven by Korandi and Sudakov in~2016. More formally, for every constant $p\in(0,1)$, a.a.s. w-sat$(G(n,p),K_s)=$w-sat$(K_n,K_s)=(s-2)n-{s-1\choose 2}$. They also noticed that the same is true for $n^{-\varepsilon(s)}\leq p\leq 1$ for certain small enough $\varepsilon(s)>0$ and ask about smaller $p$ and about possible threshold for the property w-sat$(G(n,p),K_s)=(s-2)n-{s-1\choose 2}$.

We prove that the threshold exists. Moreover,

  • if $p\geq n^{-\frac{1}{2s-3}}[\ln n]^{8/5}$, then
    a.a.s. w-sat$(G(n,p),K_s)=(s-2)n-{s-1\choose 2}$;
  • if $p\leq n^{-\frac{2}{s+1}}[\ln n]^{\frac{2}{(s-2)(s+1)}}$, then
    a.a.s. w-sat$(G(n,p),K_s)\neq (s-2)n-{s-1\choose 2}$.

16.40 - 17.10 MSK (UTC +3)
Section 2 chaired by Maksim Zhukovskii
17.10 - 17.40 MSK (UTC +3)
István Tomon ETH Zurich and MIPT, Moscow
String graphs have the Erdös-Hajnal property
Room: 424 Arctica
Video Slides

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.

17.50 - 18.20 MSK (UTC +3)
Gábor Tardos Alfréd Rényi Institute of Mathematics, Hungary and MIPT, Moscow
Color-critical edges in Schrijver graphs
joint work with Gábor Simonyi (Rényi Institute / Budapest Institute of Technology and Economics)
Room: 424 Arctica
Video Slides

The vertices of the Kneser graph $KG(n,k)$ are the $k$-subsets of an $n$-element base set and two vertices are connected if they are disjoint subsets. (Here $n$ and $k$ are integers and we assume $n>2k-1$.) Proving Kneser's conjecture Lovász established in 1978 that the chromatic number of $KG(n,k)$ is $n-2k+2$. The proof jumpstarted combinatorial applications of topology. In the same year Schrijver defined the graph $SG(n,k)$ as the subgraph of $KG(n,k)$ induced by independent sets if the base set is considered as the vertex set of a cycle. He proved that $SG(n,k)$ has the same chromatic number as $KG(n,k)$ but it is vertex-critical: removing any one vertex from $SG(n,k)$ decreases its chromatic number. But $SG(n,k)$ is not edge-critical: the removal of some edges does not decrease its chromatic number. This started a quest in two directions: to find out which edges of $SG(n,k)$ are color-critical and to find edge-critical subgraphs of $SG(n,k)$ with the same chromatic number. Both problems are solved in the case of 4-chromatic Schrijver graphs that are closely related to quadrangulations of surfaces, for the latter problem Kaiser and Stehlik gave nice examples. The talk also contains partial results and conjectures for the general case.

April 14
Section 1 chaired by István Tomon
15.00 - 15.30 MSK (UTC +3)
Anna Taranenko Sobolev Institute of Mathematics, Novosibirsk
Hypergraph matching problems and multidimensional matrices
Room: 424 Arctica
Video Slides

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.

15.40 - 16.10 MSK (UTC +3)
Konstantin Vorob'ev Sobolev Institute of Mathematics, Novosibirsk
On equitable 2-partitions of Johnson graphs with the second eigenvalue
Room: 424 Arctica
Video Slides

The vertices of a Johnson graph $J(n,w)$, $n\geq 2w$, are all $w$-subsets of a fixed $n$-set. Two vertices are adjacent if and only if they have $w-1$ joint elements. This graph is distance-regular with $w+1$ distinct eigenvalues $\lambda_i(n,w)=(w-i)(n-w-i)-i$, $i=0,1, \dots w$.

Given a graph $G$, a partition $(C_1,\ldots, C_{r})$ of its vertex set into $r$ cells is called an equitable partition with a quotient matrix $A=(a_{ij})$ if for any $i,j \in \{1,\ldots,r\}$ every vertex from $C_i$ has exactly $a_{ij}$ neighbors in $C_j$. An eigenvalue of the quotient matrix $A$ is called an eigenvalue of the partition.

We consider equitable $2$-partitions of a Johnson graph $J(n,w)$ with a quotient matrix having eigenvalue $\lambda_2(n,w)$. The problem of existence of equitable $2$-partitions of Johnson graphs with given quotient matrix is far from solving. In particular, it includes a famous Delsarte's conjecture about non-existence of $1$-perfect codes in the Johnson scheme.

One of possible ways is to characterise partitions with certain eigenvalues. Equitable $2$-partitions of the graph $J(n,w)$ with the eigenvalue $\lambda_1(n,w)$ were characterized by Meyerowitz [1]. Later, Gavrilyuk and Goryainov [2] found all realizable quotient matrices (i.e. quotient matrices of some existing partitions) of equitable $2$-partitions of $J(n,3)$ for odd $n$.

In these work we consider equitable $2$-partitions of $J(n,w)$ with the second eigenvalue $\lambda_2(n,w)$ for $w\geq 4$. As the main result, we find all such realizable quotient matrices. Moreover, we characterize all equitable $2$-partitions with these matrices up to equivalence in cases $n>2w$ and $n=2w$, $w \geq 7$. Particularly, we find new infinite series of partitions of $J(2w,w)$ for $w\geq 4$.

[1] A. Meyerowitz, Cycle-balanced Conditions for Distance-regular Graphs, Discrete Mathematics 264 (2003), N3, 149—166.

[2] A. L. Gavrilyuk, S. V. Goryainov, On perfect 2-colorings of Johnson graphs J(v,3), Journal of Combinatorial Designs 21, (2013), N6, 232—252.

16.20 - 16.40 MSK (UTC +3)
Alexander Guterman MSU, Moscow
Matrix Centralizers and their Applications
Room: 424 Arctica
Video Slides

The talk is based on the works [1, 2, 3].

For a matrix $A\in M_n({\mathbb F} )$ its centralizer $${\mathop{\mathcal{C}}\nolimits}(A)=\{X\in M_n({\mathbb F} )\vert\; AX=XA\}$$ is the set of all matrices commuting with $A$.

For a set $S\subseteq M_n({\mathbb F} )$ its centralizer $${\mathop{\mathcal{C}}\nolimits}(S)=\{X\in M_n({\mathbb F} )\vert\; AX=XA \mbox{ for every } A\in S\}=\bigcap_{A\in S} {\mathop{\mathcal{C}}}(A) $$ is the intersection of centralizers of all its elements. Centralizers are important and useful both in fundamental and applied sciences.

A non-scalar matrix $A\in M_n({\mathbb F} )$ is {\em minimal\/} if for every $X\in M_n({\mathbb F} )$ with ${\mathop{\mathcal{C}}\nolimits}(A) \supseteq {\mathop{\mathcal{C}}\nolimits}(X)$ it follows that ${\mathop{\mathcal{C}}\nolimits}(A)={\mathop{\mathcal{C}}\nolimits}(X)$. A non-scalar matrix $A\in M_n({\mathbb F} )$ is {\em maximal\/} if for every non-scalar $X\in M_n({\mathbb F} )$ with ${\mathop{\mathcal{C}}\nolimits}(A) \subseteq {\mathop{\mathcal{C}}\nolimits}(X)$ it follows that ${\mathop{\mathcal{C}}\nolimits}(A)={\mathop{\mathcal{C}}\nolimits}(X)$.

We investigate and characterize minimal and maximal matrices over arbitrary fields.

Our results are then applied to the theory of commuting graphs of matrix rings and to characterize commutativity preserving maps on matrices.

[1] G. Dolinar, A.E. Guterman, B. Kuzma, P. Oblak, Commuting graphs and extremal centralizers, Ars Mathematica Contemporanea, 7(2), 2014, 453-459.

[2] G. Dolinar, A.E. Guterman, B. Kuzma, P. Oblak, Commutativity preservers via matrix centralizers, Publicationes Mathematicae Debrecen, 84(3-4), 2014, 439–450.

[3] G. Dolinar, A.E. Guterman, B. Kuzma, P. Oblak, Extremal matrix centralizers, Linear Algebra and its Applications, 438(7), 2013, 2904-2910.

16.40 - 17.10 MSK (UTC +3)
Section 2 chaired by Andrey Kupavskii
17.10 - 17.40 MSK (UTC +3)
Nora Frankl London School of Economics, UK and MIPT, Moscow
On the number of discrete chains
joint work with Andrey Kupvaskii
Room: 424 Arctica
Video Slides

Determining the maximum number of unit distances that can be spanned by $n$ points in the plane is a difficult problem, which is wide open. The following more general question was recently considered by Eyvindur Ari Palsson, Steven Senger, and Adam Sheffer. For given distances $t_1,...,t_k$ a $(k+1)$-tuple $(p_1,...,p_{k+1})$ is called a $k$-chain if $||x_i-x_{i+1}||=t_i$ for $i=1,...,k$. What is the maximum possible number of $k$-chains that can be spanned by a set of $n$ points in the plane? Improving the result of Palsson, Senger and Sheffer, we determine this maximum up to a small error term (which, for $k=1 \bmod 3$ involves the maximum number of unit distances). We also consider some generalisations, and the analogous question in $R^3$.

17.50 - 18.15 MSK (UTC +3)
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
Video Slides

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.

April 15
Section 1 chaired by Nora Frankl
15.00 - 15.30 MSK (UTC +3)
Grigory Ivanov TU Wien, Austria and MIPT, Moscow
On the volume of sections of the cube
joint work with Igor Tsiutsiurupa
Room: 424 Arctica
Video Slides

The problem of volume extrema of the intersection of the standard $n$-dimensional cube $\Box^n = [-1,1]^n$ with a $k$-dimensional linear subspace $H$ has been studied intensively. The celebrated Vaaler theorem says that only the coordinate subspaces are the volume minimizers. Using the Brascamb-Lieb inequality, K. Ball proved two upper bounds which are tight for some $k$ and $n.$ Typically, methods of functional analysis or some tricky inequalities for measures are used in such problems. In this talk, we will discuss a 'naive' variational principle for the problem of volume extrema of $\Box^n \cap H$ and some geometrical consequences of this principle. Particularly, we will sketch how to find all planar maximizers ($k = 2$). Planar maximizers were unknown for all odd $k$ starting with 5.

15.40 - 16.10 MSK (UTC +3)
Márton Naszódi Alfréd Rényi Institute of Mathematics and Eötvös University, Hungary
Covering convex bodies and the closest vector problem
joint work with Moritz Venzin (EPFL, Lausanne)
Room: 424 Arctica
Video Slides

In the closest vector problem, we are given a point in real $n$-space, and need to find the closest integer point to it according to some norm. The current fastest algorithm (Dadush and Kun, 2016) for general norms is of running time $2^{O(n)} (1/\epsilon)^n$. We improve this substantially for certain norms, eg. for $\ell_p$ spaces. The result is based on a geometric covering problem that is interesting on its own. How many convex bodies are needed to cover the ball of the norm such that, if scaled by factor 2 around their centroids, each one is contained in the $(1+\epsilon)$-scaled homothet of the ball?

16.20 - 16.50 MSK (UTC +3)
Vassily Manturov BMSTU, Moscow
An Introduction to Framed 4-Graph Minor Theory
Room: 424 Arctica
Video Slides

The well-known Pontrjagin-Kuratowski Theorem says that a graph is non-planar if it does not contain $K_{5}$ and $K_{3,3}$ (in the modern formulation we can say does not contain as a minor). In the talk we deal with regular 4-graphs with an additional structure of opposite edges at each vertex (we call them framed 4-graphs) . A theorem due to the speaker (conjectured by V.A.Vassiliev) says that such a graph is non-planar if it does not contain two cycles with no common edges having exactly one transverse intersection. The equivalence of the Pontrjagin-Kuratowski Theorem and Vassiliev's conjecture was proved by I.M.Nikonov.

In the talk we prove that for framed 4-graphs (with source-sink structure) there is a unique graph which plays the role of planarity abstraction as well as intrinsic linkedness obstruction as well as obstruction of crossing number no more than two.

16.50 - 17.10 MSK (UTC +3)
Section 2 chaired by Dmitry Zakharov
17.10 - 17.40 MSK (UTC +3)
Nikita Kalinin HSE and Saint Petersburg State University, Spb
Trends in sandpile model
Room: 424 Arctica

I will define the sandpile model and briefly describe the current trends and open questions around it.

17.50 - 18.20 MSK (UTC +3)
Oleg German MSU, Moscow
Parametric approach to Khintchine's transference theorem and its generalizations
Room: 424 Arctica
Video Slides

In 1926 A.Ya.Khintchine proved the famous transference inequalities connecting two dual problems. The first one concerns simultaneous approximation of given real numbers $\theta_1,\ldots,\theta_n$ by rationals, the second one concerns approximating zero with the values of the linear form $\theta_1x_1+\ldots+\theta_nx_n+x_{n+1}$ at integer points.

In 2009 W.M.Schmidt and L.Summerer presented a new approach to Diophantine approximation, which they called parametric geometry of numbers. The formulation of Khintchine's transference theorem in terms of parametric geometry of numbers appeared to be most elegant and simple. Moreover, this approach allowed a very natural splitting of Khintchine's inequalities into a chain of inequalities between the so called intermediate Diophantine exponents.

We shall talk about application of parametric geometry of numbers to some generalizations of Khintchine's theorem. Particularly, we shall discuss transference theorems for Diophantine exponents of lattices and in Diophantine approximation with weights.

19.00 MSK (UTC +3)
Conference dinner
April 16
Section 1 chaired by Grigory Ivanov
15.20 - 15.40 MSK (UTC +3)
Grigory Kabatiansky Skoltech, Moscow
How to find counterfeit coins on a precision scale if the weights of coins a priori unknown
joint work with Elena Egorova
Room: 424 Arctica
Video Slides

Let us have a set of $n$ coins with the main part of them, namely at least $n-t$, are genuine. Genuine coins have the same weight, other coins can have different weights but no one of these weights are known. There is a precision scale that allows to know the exact weight of any subset of coins. What is the minimal number $Q(n,t)$ of non-adaptive weighings which allows to find weights for all coins?

We give the optimal solutions for $t=1$ and asymptotically optimal for $t-const$ with the number of weighings $Q(n,t)=t\log_2 n (1+o(1))$. It was previously known [1] that $Q(n,t)=O(t\ln n )$.

There are at least two open questions:

  • to develop 'decoding' algorithm which finds weights for all coins with polynomial complexity;
  • what is $Q(n,t)$ for $t=\lambda n$ and $n\rightarrow\infty$?

[1] Nader H. Bshouty, Hanna Mazzawi, On parity check (0, 1)-matrix over Zp, SODA '11: Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms, pp. 1383–1394, 2011.

15.50 - 16.10 MSK (UTC +3)
Konstantin Olmezov MIPT, Moscow
An elementary approach to the operator method in additive combinatorics
Room: 424 Arctica
Video Slides

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$.

16.20 - 16.50 MSK (UTC +3)
Ilya Shkredov Steklov Mathematical Institute, MSU and MIPT, Moscow
Growth in Chevalley groups and Zaremba's conjecture
Room: 424 Arctica
Video Slides

Given a Chevalley group ${\mathbf G}(q)$ and a parabolic subgroup $P\subset {\mathbf G}(q)$, we prove that for any set $A$ there is a certain growth of $A$ relatively to $P$, namely, either $AP$ or $PA$ is much larger than $A$. Also, we study a question about intersection of $A^n$ with parabolic subgroups $P$ for large $n$. We apply our method to obtain some results on a modular form of Zaremba's conjecture from the theory of continued fractions and make the first step towards Hensley's conjecture about some Cantor sets with Hausdorff dimension greater than $1/2$.

16.50 - 17.10 MSK (UTC +3)
Section 2 chaired by Andrey Kupavskii
17.10 - 17.40 MSK (UTC +3)
Balázs Patkós Alfréd Rényi Institute of Mathematics, Hungary and MIPT, Moscow
Induced and non-induced poset saturation problems
joint work with Keszegh, Lemons, Martin, and Pálvölgyi
Room: 424 Arctica
Video Slides

A subfamily $\mathcal{G}\subseteq \mathcal{F}\subseteq 2^{[n]}$ of sets is a non-induced (weak) copy of a poset $P$ in $\mathcal{F}$ if there exists a bijection $i:P\rightarrow \mathcal{G}$ such that $p\le_P q$ implies $i(p)\subseteq i(q)$. In the case where in addition $p\le_P q$ holds if and only if $i(p)\subseteq i(q)$, then $\mathcal{G}$ is an induced (strong) copy of $P$ in $\mathcal{F}$. We consider the minimum number $sat(n,P)$ [resp.\ $sat^*(n,P)$] of sets that a family $\mathcal{F}\subseteq 2^{[n]}$ can have without containing a non-induced [induced] copy of $P$ and being maximal with respect to this property, i.e., the addition of any $G\in 2^{[n]}\setminus \mathcal{F}$ creates a non-induced [induced] copy of $P$.

We prove for any finite poset $P$ that $sat(n,P)\le 2^{|P|-2}$, a bound independent of the size $n$ of the ground set. For induced copies of $P$, there is a dichotomy: for any poset $P$ either $sat^*(n,P)\le K_P$ for some constant depending only on $P$ or $sat^*(n,P)\ge \log_2 n$. We classify several posets according to this dichotomy, and also show better upper and lower bounds on $sat(n,P)$ and $sat^*(n,P)$ for specific classes of posets.

Our main new tool is a special ordering of the sets based on the colexicographic order. It turns out that if $P$ is given, processing the sets in this order and adding the sets greedily into our family whenever this does not ruin non-induced [induced] $P$-freeness, we tend to get a small size non-induced [induced] $P$-saturating family.

17.50 - 18.20 MSK (UTC +3)
Dmitry Zakharov HSE and MIPT, Moscow
Erdös-Ginzburg-Ziv problem and Convex Geometry
Room: 424 Arctica
Video Slides

Let $f(p, d)$ be the minimal number $s$ such that among any $s$ vectors in $\mathbb F_p^d$ one can find $p$ vectors with zero sum.

In [2], we show that for any fixed $d$ and sufficiently large $p$ we have an inequality $f(p, d) \le 4^d p$. This improves the previous bound $f(p, d) < (c d \log d)^d p$ due to [1].

Note that we have a lower bound $f(p, d) \ge 2^d (p-1)+1$ as the example of the hypercube shows. So we have that $f(p, d)$ is an exponential function in $d$ provided that $p > p_0(d)$.

The proof combines various ideas from convex geometry, additive combinatorics and algebraic combinatorics.

[1] Alon Noga and Moshe Dubiner, A lattice point problem and additive number theory, Combinatorica 15.3 (1995): 301-309.

[2] Zakharov Dmitriy, Convex geometry and Erdös-Ginzburg-Ziv problem, arXiv preprint arXiv:2002.09892 (2020).

Tune in

The conference will be held online.

To attend the conference, please enter the meeting (ID: 303-932-461, pass: first 6 decimal places of pi). Alternatively, you can watch the live stream on Twitch, no registration nesessary.


Mikhail Isaev Monash University
Dmitry Shabanov MIPT
Maksim Zhukovskii MIPT