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

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

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

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.

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.

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.

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.

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

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.

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?

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.

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

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.

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

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

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.

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