Geodesic Spanners for Points on a Polyhedral Terrain
Abstract: ‎Let $S$ be a set of $n$ points on a polyhedral terrain $T$ in $R^3$‎, ‎and let $\epsilon>0$ be a‎ ‎fixed constant‎. ‎We prove that $S$ admits a $(2+\epsilon)$-spanner with $O(n\log n)$ edges‎ with respect to the geodesic distance‎. ‎This is the first spanner with constant spanning‎ ratio and a near-linear number of edges for points on a terrain‎. ‎On our way to this result‎, we prove that any set of $n$ weighted points in $R^d$ admits an additively weighted‎ $(2+\epsilon)$-spanner with $O(n)$ edges; this improves the previously best known bound‎ on the spanning ratio (which was $5+\epsilon$)‎, ‎and almost matches the lower bound‎.

Applications of the Combinatorial Nullstellensatz
Abstract: The Combinatorial Nullstellensatz is a theorem of Alon from the late '90. (But it appeared before in several articles of Alon and co-authors.) It generalizes to multivariate polynomials the fact that a (univariate) polynomial of degree $d$ cannot have $d+1$ roots. This result has been called "combinatorial" because it has been used in a large range of combinatorial fields to produce new (short) proofs of known results and many generalizations.
In this presentation, I would like to introduce this marvelous theorem and give an overview of the applications, not restraining myself to additive combinatorics, where I am more involved.

Which Graph Properties are Characterized by the Spectrum?
Abstract: Spectral graph theory deals with the relation between the structure of a graph and the eigenvalues (spectrum) of an associated matrix, such as the adjacency matrix $A$ and the Laplacian matrix $L$. Many results in spectral graph theory give necessary condition for certain graph properties in terms of the spectrum of $A$ or $L$. Typical examples are spectral bounds for characteristic numbers of a graph, such as the independence number, the chromatic number, and the isoperimetric number. Another type of relations are characterization. These are conditions in terms of the spectrum of $A$ or $L$, which are necessary and sufficient for certain graph properties. Two famous examples are: (i) a graph is bipartite if and only if the spectrum of $A$ is invariant under multiplication by $-1$, and (ii) the number of connected components of a graph is equal to the multiplicity of the eigenvalue $0$ of $L$. In this talk we will survey graph properties that admit such a spectral characterization.

Weak Reconstruction of Edge-Deleted Cartesian Products
Abstract: In 1960 Ulam asked whether a graph $G$ is uniquely determined up to isomorphisms by its deck, that is, by the set of all graphs $G\setminus x$ obtained from $G$ by deleting a vertex $x$ and all edges incident to it. This led to the Reconstruction Conjecture, also known as Ulam's Conjecture, that any two graphs on at least three vertices with the same deck are isomorphic. This still is open for finite graphs. When reconstructing a class of graphs, the problem partitions into the subproblems recognition and weak reconstruction. The first consists of showing that membership in the class is determined by the deck, and the latter that nonisomorphic members of the class have different decks.
Imrich and Žerovnik, who showed that both the recognition and the weak reconstruction problem can be solved from a single vertex-deleted subgraph for nontrivial, connected finite or infinite Cartesian products.
In 1964 Harary introduced the Edge Reconstruction Conjecture, that any two graphs with at least four edges that have the same deck of edge-deleted subgraphs are isomorphic. For products this was taken up by Dörfler, who showed that all nontrivial strong products and certain lexicographic products can be reconstructed from the deck of all edge-deleted subgraphs. He did not treat the edge-reconstruction of Cartesian products.
Here we show that both the recognition problem and the weak edge reconstruction problem can be solved from a single edge-deleted subgraph for nontrivial, connected finite or infinite Cartesian products.
For finite graphs $G$ the reconstruction is possible in $O(mn^2)$ time, where $n$ is the order and $m$ the size of $G$.

Fair Partition of a Convex Planar Pie
Abstract: Nandakumar and Ramana Rao asked in 2008 the following question: Is it possible to cut a convex body in the plane in $m$ convex parts of equal area and equal perimeter? Although this problem also has some algorithmic aspects, we will only discuss the existence question.
Nandakumar and Ramana Rao themselves noticed that the case $m=2$ is solved with a simple continuity argument, and suggested an argument for $m=4$. In fact, fair partition in the case $m$ is a power of two is a simple modification of Gromov's argument from 2003, used in his proof of the waist of the Gaussian measure and the waist of the sphere theorems.
The case $m=3$ was done by B'ar'any, Blagojevi'c, and Szücs in 2010. The case when $m$ is a power of a prime was eventually done by a joint effort of several people: Aronov, Hubard, Blagojevi'c, Ziegler, and the speaker. Curiously, the essential topological fact used in this proof (in the planar problem that we discuss) was established already in 1988 by Vassiliev in his paper about topological complexity of finding non-multiple roots of a complex polynomial.
The last publication on this equipartition problem was in 2014 and since then there were no advances, in particular, nothing was known about the case $m=6$. But in 2018 we have managed to invent new approaches that solve the problem completely, for any $m$.

Two New Classes of Hadamard Matrices
Abstract: A Hadamard matrix $H$ of order $4n^2$ is said to be skew-regular if it is of skew-type and the absolute values of the row sums are all $2n$. There is no skew-regular Hadamard matrix of order $4n^2$, $n$ even.
A Hadamard matrix $H$ of order $m$ is said to be balancedly splittable if there is an $\ell\times m$ submatrix $H_1$ of $H$ such that all the off-diagonal entries of $H_1^tH_1$ belongs to the set $D$, where $|D|\le 2$. No Hadamard matrix of order $4n^2$, $n$ odd, is balancedly splittable, if the off-diagonal entries of the submatrix $H_1^tH_1$ is constant in absolute values.
The existence and applications of these two classes of matrices to Hadamard diagonalizable strongly regular graphs, maximal equiangular lines set, unbiased Bases, doubly regular tournaments, and issues related to the equivalence of Hadamard matrices will be discussed.

MDS Codes, Arcs and Tensors
Abstract: A Maximum Distance Separable code (or MDS code) is a code meeting the Singleton bound. This means that an MDS code corrects the maximum number of errors given its size and length. Examples of MDS codes include the (extended) Reed-Solomon codes which have many applications. MDS codes have been studied since the 1950's and, according to MacWilliams and Sloane [3], already in 1977, they formed ``one of the most fascinating chapters in all of coding theory''. It is believed that a linear MDS code cannot have length larger than the extended Reed-Solomon code (except in some very special cases which are well-understood). This is known as the MDS conjecture (sometimes referred to as the main conjecture). Many mathematicians have contributed to a possible solution and several instances of the MDS conjecture have been solved in the last 50 years. However the conjecture in its full generality is still open. In 2012, Simeon Ball proved the conjecture for MDS codes which are linear over prime fields.
We will report on recent progress, in particular on recent results from [1] and [2].
Linear MDS codes are equivalent to arcs in projective spaces over finite fields, and as such, they have been a motivating application for many contributions in Galois geometry. In terms of arcs, the MDS conjecture states that an arc in a projective space over a finite field cannot have more points than a normal rational curve (ignoring a couple of well-understood special cases). Most previous contributions towards the MDS conjecture, obtained by Segre [1967], Hirschfeld and Korchm'aros [1996, 1998], and Voloch [1990, 1991], rely on results on the number of points on algebraic curves over finite fields, in particular the Hasse-Weil theorem and the St"ohr-Voloch theorem, and are based on Segre's idea to associate an algebraic curve in the dual plane containing the tangents to an arc. In our work [1], we do not rely on such theorems, but use a new approach starting from a scaled coordinate-free version of Segre's lemma of tangents. We prove that in odd characteristic an arc in a projective plane over a finite field, which is not contained in a conic, is contained in the intersection of two curves, which do not share a common component, and have relatively small degree. This result then allows us to prove the MDS conjecture for a wider range of dimensions.

[1] S. Ball and M. Lavrauw: Planar arcs. J. Combin. Theory Ser. A 160 (2018), 261--287.
[2] S. Ball and M. Lavrauw: Arcs and Tensors, preprint.
[3] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, 1977.

Ultra-Fast Asynchronous Randomized Rumor Spreading
Abstract: Standard randomized rumor spreading algorithms propagate a piece of information, so-called the rumor, in a given network that proceed in synchronized rounds. Starting with a single informed node, in each subsequent round, every node calls a random neighbor in order to exchange the rumor (by sending the rumor to the neighbor (push algorithm) or asking it from the neighbor (pull algorithm)). Panagiotou et al. [ISAAC'13] considered a multiple-call version of the algorithms where each node is enabled to make more than one call in each round. The number of calls of a node is independently chosen from a probability distribution $R$.
Seeking for a more realistic model, we propose an asynchronous version of the multiple-call algorithms on a fully connected network with $n$ nodes. In our model, each node has an independent Poisson clock whose rate may differ from others. Basically, the clock rate of each node is independently drawn from a probability distribution $R$ at the beginning of the process. The push algorithm starts with a single informed node, when the clock of an informed node rings, the node contacts a random neighbor and sends (pushes) the rumor to the neighbor. Similarly, in the push-pull, if the clock of a node rings, then the node contacts a random neighbor in order to exchange the rumor. We study the effect of $R$ on the spreading time of the algorithms, which is the time that the algorithm needs to inform all nodes with high probability. In this work, we show that if $R$ is a power law distribution with exponent $\beta \in(2,3)$ and $\epsilon\in[1/n, 1-1/n]$ be an arbitrary number. Then, in expectation, after $O(\log(1/\epsilon))$ time the push-pull algorithm informs at least $(1-\epsilon)n$ nodes. Notice that the multiple-call push-pull algorithm with distribution $R$ requires $\Omega(\log\log n)$ expected rounds to inform a constant fraction of nodes. Moreover, if $R$ is an arbitrary distribution with bounded mean and variance, then we show that the push algorithm spreads the rumor in a complete network with $n$ nodes in $\frac{\log n}{R}\pm\omega(\sqrt{\log n})$ time, with high probability.

Thresholds in Random Graphs with Focus on Thresholds for $k$-regular Subgraphs
Abstract: The most intriguing discovery made by Erdös and Rényi in random graphs is the phenomenon of thresholds. For many graph properties the limiting probability that a random graph possesses them jumps from 0 to 1 (or vice versa) very rapidly, that is, with a rather small increase in the (expected) number of edges. We present a few classical and well understood examples but then move to new results. We prove that the binomial random graph $G_{n,p=c/n}$ with high probability has a $k$-regular subgraph if $c$ is at least $e^{-\Theta(k)}$ above the threshold for the appearance of a subgraph with minimum degree at least $k$; i.e. a non-empty $k$-core. In particular, this pins down the threshold for the appearance of a $k$-regular subgraph to a window of size $e^{-\Theta(k)}$.

The Independence Numbers and the Chromatic Numbers of Random Subgraphs of Kneser’s Graphs and their Generalizations
Abstract: The classical Kneser graph is the graph whose set of vertices consists of all the $ r $-subsets of the set $ [n] = ${$1, \dots, n$} and whose edges are formed by all the vertex pairs with empty intersection. The chromatic number of this graph was found by Lovász, and the independence number $ {n-1 \choose r-1} $ of this graph is given by the Erdös-Ko-Rado theorem.
In 2014 the study of the independence numbers and the chromatic numbers of random subgraphs of Kneser's graphs and their generalizations was initiated. More precisely, the independence numbers and the chromatic numbers are investigated in random subgraphs of the graphs $ G(n,r,s) $, where the vertices are the same as in Kneser's graph and the edges are formed by the pairs of vertices whose intersection is of size $ s $. Obviously, for $ s = 0 $, we come back to Kneser's graph.
In our talk, we will give an overview of many existing results and open problems concerning the subject.

Logical Laws for Random Structures
Abstract: Let $\Sigma$ be a finite set of relational symbols. A $(\Sigma,n)$-structure is the set {$1,\ldots,n$} with a fixed relation $f:${$1,\ldots,n$}$^m\to${0,1} for every relational symbol $f\in\Sigma$ of arity $m$. We consider random structures that have certain natural distributions on the set of all $(\Sigma,n)$-structures.
$\Sigma$-logic is a set of sentences with relational symbols from $\Sigma$. First order (FO) logic is the set of all sentences with variables denoting elements of structures. Second order (SO) logic is the set of all sentences with variables denoting both elements of structures and predicates. In monadic second order (MSO) logic, we restrict ourselves with variables denoting elements and unary predicates. We say that a random $(\Sigma,n)$-structure obeys FO zero-one (convergence) law, if every first order sentence is either true on the structure with high probability (w.h.p.) or false w.h.p. (is true with a converging probability resp.). Similar definitions are introduced for SO and MSO logics.
It was independently proven by Glebskii, Kogan, Liogon'kii and Talanov in 1969 and Fagin in 1976 that an undirected random graph having uniform distribution on the set of all graphs on {$1,\ldots,n$} obeys FO zero-one law. It is obvious that the convergence SO law fails on this graph (i.e., the property of having even number of vertices is expressed in SO). The MSO convergence for this random graph was disproved by Kaufmann and Shelah in 1985.
Many other random structures were considered in the context of logical laws: binomial random graphs, binomial random hypergraphs, random trees, random regular graphs, and others.
Our contribution to the field is the following. We consider the uniform attachment model: at every step, we add a vertex with $m$ edges chosen uniformly at random. An interest in studying attachment models is motivated by results of Bollobás et al. that demonstrate similarities between certain attachment models and real networks. We have proved that, for $m=1$, the random graph obeys FO zero one law, while, for $m\geq 2$, it fails. Nevertheless, for $m\geq 2$, the FO convergence law holds.