# Combinatorics and Geometry Days II

## Speakers

## Abstracts

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

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.

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.

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.

## Location

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.