Schedule

Abstract.  Consider the random graph process $\{G_t\}_{t\geq 0}$. For $k\geq 3$ let $G_{t}^{(k)}$ denote the $k$-core of $G_t$ and let $\tau_k$ be the minimum $t$ such that $G_{t}^{(k)}$ is nonempty. It is well known that w.h.p. $G_{\tau_k}^{(k)}$ has linear size while it is believed to be Hamiltonian. Bollobás, Cooper, Fenner and Frieze further conjectured that w.h.p. $G_{\tau_k}^{(k)}$ spans $\lfloor \frac{k-1}{2} \rfloor$ edge-disjoint Hamilton cycles plus, when $k$ is even, a perfect matching. We prove that w.h.p., for $t\geq \tau_k$, if $k$ is odd then $G_{\tau_k}^{(k)}$ spans $\frac{k-3}{2}$ edge disjoint Hamilton cycles plus an additional 2-factor whereas if $k$ is even then it spans $\frac{k-2}{2}$ edge disjoint Hamilton cycles plus an additional matching of size $n-o(n)$. In particular w.h.p. $G_{t}^{(k)}$ is Hamiltonian for $k\geq 4$ and $t\geq \tau_k$. This improves upon results of Krivelevich, Lubetzky and Sudakov.

Abstract.  The random greedy algorithm for finding a maximal independent set in a graph has been studied extensively in various settings in combinatorics, probability, computer science — and even in chemistry. The algorithm builds a maximal independent set by inspecting the vertices of the graph one at a time according to a random order, adding the current vertex to the independent set if it is not connected to any previously added vertex by an edge.

In this talk I will present a natural and general framework for calculating the asymptotics of the proportion of the yielded independent set for sequences of (possibly random) graphs, involving a useful notion of local convergence. We use this framework both to give short and simple proofs for results on previously studied families of graphs, such as paths and binomial random graphs, and to give new results for other models such as random trees.

If time allows, I will discuss a more delicate result, according to which in expectation, the cardinality of a random greedy independent set in the path is no larger than that in any other tree of the same order.

The talk is based on joint work with Michael Krivelevich, Tamás Mészáros and Clara Shikhelman.

Abstract.  For a constant $\alpha>0$ a graph $G$ on $n$ vertices is called an $\alpha$-expander if every vertex subset $U$ of size up to $n/2$ has an external neighborhood whose size is at least $\alpha\left|U\right|$. It is known that every $\alpha$-expander on $n$ vertices contains cycles of lengths logarithmic and linear in $n$. We prove that cycle lengths in $\alpha$-expanders are well distributed: for every $0<\alpha\leq1$ there exist positive constants $a_{1},a_{2}$ and $A=O\left(\frac{1}{\alpha}\right)$ such that for every $\alpha$-expander $G$ on $n$ vertices and every integer $\ell\in\left[a_{1}\log n,a_{2}n\right]$, $G$ contains a cycle whose length is between $\ell$ and $\ell+A$. Moreover, we show that $G$ has $\Omega\left(\frac{\alpha^{3}}{\log\left(1/\alpha\right)}\right)n$ different cycle lengths.

We also introduce a stronger expansion-type property, guaranteeing the existence of a linearly long interval in the set of cycle lengths. For a constant $\beta>0$ a graph $G$ on $n$ vertices is called a $\beta$-graph if every pair of disjoint sets of size at least $\beta n$ are connected by at least one edge. We prove that for every $0<\beta<1/16$ there exist positive constants $b_{1},b_{2}$ such that every $\beta$-graph $G$ on $n$ vertices contains a cycle of length $\ell$ for every $\ell\in\left[b_{1}\log n,b_{2}n\right]$.

Joint work with Michael Krivelevich.

Abstract.  A Latin square of order $n$ is an $n\times n$ array with entries in $[n]$ such that each integer appears exactly once in every row and every column. Two Latin squares $L$ and $L'$ are said to be orthogonal if, for all $x,y\in [n]$, there is a unique pair $(i,j)$ such that $L(i,j) = x$ and $L'(i,j) = y$; a set of Latin squares is mutually orthogonal if any two of them are orthogonal. The motivation to study orthogonal Latin squares comes both from their connections to other combinatorial structures and from their importance in practical applications.

After the question of existence, a natural and important problem is to determine how many structures satisfying given properties there are. In this talk, we will present an upper bound on the number of ways to extend a system of $k$ mutually orthogonal Latin squares to a system of $k+1$ mutually orthogonal Latin squares and discuss some applications, comparing the resulting bounds to previously known lower and upper bounds.

This is joint work with Shagnik Das and Tibor Szabó.

Abstract.  A Sidon set in the integers is a subset $S\subset\mathbb{N}$ for which all pairwise sums are distinct, i.e. for $w,x,y,z\in S$, $w+x=y+z$ implies $\{w,x\}=\{y,z\}$. Given $0\le\alpha<1$, an $\alpha$\textit{-strong Sidon set} is defined by the condition $|(w+x)-(y+z)|\ge w^{\alpha}$ for $w,x,y,z\in S$ with $w>y\ge z \ge x$. These sets can be used to study Sidon sets contained in certain random subsets of the integers. Modifying a construction of Cilleruelo we prove the existence of an $\alpha$-strong Sidon set $S$ with counting function $|S\cap [n]| = n^{\sqrt{(1+\alpha)^2+1}-(1+\alpha)+o(1)}$.

This is joint work with Juanjo Rué and Christoph Spiegel.

Abstract.  Consider a random graph process, in which edges are added to an empty graph consecutively in a uniformly chosen random order. A classical result by Bollobás and Frieze state that at the first moment the graph no longer contains vertices of degree less than $2k$, it also typically contains $k$ edge disjoint Hamilton cycles.

We extend this result to random subgraph processes, in which only edges of a given base graph are added, for certain families of dense base graphs.

Based on a joint work with Michael Krivelevich.

Abstract.  Let $f(n,v,e)$ denote the maximum number of edges in a $3$-uniform hypergraph not containing $e$ edges spanned by at most $v$ vertices. One of the most influential open problems in extremal combinatorics then asks, for a given number of edges $e \geq 3$, what is the smallest integer $d=d(e)$ so that $f(n,e+d,e) = o(n^2)$? This question has its origins in work of Brown, Erdős and Sós from the early 70's and the standard conjecture is that $d(e)=3$ for every $e \geq 3$. The state of the art result regarding this problem was obtained in 2004 by Sárközy and Selkow, who showed that $f(n,e + 2 + \lfloor \log_2 e \rfloor,e) = o(n^2)$. The only improvement over this result was a recent breakthrough of Solymosi and Solymosi, who improved the bound for $d(10)$ from 5 to 4. We obtain the first asymptotic improvement over the Sárközy--Selkow bound, showing that $$ f(n, e + O(\log e/ \log\log e), e) = o(n^2). $$

Joint work with David Conlon, Yevgeny Levanzov and Asaf Shapira.

Abstract.  The classical Erdős-Szekeres theorem dating back almost a hundred years states that any sequence of $(n-1)^2+1$ distinct real numbers contains a monotone subsequence of length $n$. This theorem has been generalised to higher dimensions in a variety of ways but perhaps the most natural one was proposed by Fishburn and Graham more than 25 years ago. They defined the concept of a monotone and a lex-monotone array and asked how large an array one needs in order to be able to find a monotone or a lex-monotone subarray of size $n \times \ldots \times n$. Fishburn and Graham obtained Ackerman-type bounds in both cases. We significantly improve these results. Regardless of the dimension we obtain at most a triple exponential bound in $n$ in the monotone case and a quadruple exponential one in the lex-monotone case. This is joint work with Benny Sudakov and Tuan Tran.

Abstract.  A well-known conjecture, often attributed to Ryser, states that every $r$-partite $r$-uniform hypergraph has cover number at most $(r - 1)$ times its matching number. Despite considerable effort, this conjecture remains wide open, motivating the pursuit of variants of the original conjecture. Recently, Király and Tóthmérész, and independently Bustamante and Stein, considered the problem under the assumption that the hypergraph is $t$-intersecting, conjecturing that the cover number $\tau(\mathcal{H})$ of such a hypergraph $\mathcal{H}$ is at most $r - t$. This conjecture was proven for all $r \leq 4t-1$.

In this talk, we discuss extensions of this result. For $r \leq 3t-1$, we prove a tight upper bound on the cover number of these hypergraphs, showing that they in fact satisfy $\tau(\mathcal{H}) \leq \lfloor(r - t)/2\rfloor + 1$ and there is a matching construction. We also discuss upper bounds and constructions for other values of $(r,t)$. In particular, we extend the range of $t$ for which the conjectured upper bound of $r-t$ is known to be true, showing that it holds for all $r < \frac{36}{7}t-5$.

This represents joint work with Anurag Bishnoi, Shagnik Das and Tibor Szabó.

Abstract.  In this talk, we will calculate \pi.

Abstract.  We determine the asymptotic behavior of maximum cut in supercritical random graphs G(n,(1+\epsilon)/n) as a function of \epsilon. The argument is based on a theorem of Ding, Lubetzky and Peres, describing the typical structure of the giant component of random graphs in this regime.

We use upper bounds on the Maxcut of supercritical random graphs to solve two unrelated problems. Firstly, we analyze typical coloring properties of p-random tournaments, obtained from the transitive tournament of n vertices by reversing each edge independently with probability p. Secondly, we prove the following conjecture of Frieze and Pegden. For every \epsilon>0 there exists l(\epsilon) such that with high probability a random graph G\sim G(n,(1+\epsilon)/n) is not homomorphic to the cycle on 2l+1 vertices.

A joint work with Michael Krivelevich and Gal Kronenberg, Tel Aviv University.

Abstract.  A set system \mathcal{F} \subseteq 2^{[n]} shatters a given set S \subseteq [n] if \{F\cap S : F \in \mathcal{F} \}=2^S , and \mathrm{Sh}(\mathcal{F}) denotes the collection of all sets shattered by \mathcal{F}. A system is said to be (n,k)-universal if it shatters all k-subsets of [n], that is, \binom{[n]}{k} \subseteq \mathrm{Sh}(\mathcal{F}) . Much research has been devoted to determining the minimum possible size of an (n,k)-universal system, as well as to finding explicit constructions of small universal systems.

We introduce a refined version of this problem, studying the quantity \mathrm{sh}_{\text{max}}(n,k,m), the maximum number of k-subsets of [n] that can be shattered by a set system of size m. We obtain precise results when m = 2^k, in particular showing that as soon as a system can shatter a single k-subset, it can shatter a positive fraction of all k-subsets.

Joint work with Shagnik Das.

Abstract.  In 1975 Pippenger and Golumbic proved that any graph on n vertices admits at most 2e(n/k)^k induced k-cycles. This bound is larger by a multiplicative factor of 2e than the simple lower bound obtained by a blow-up construction. Pippenger and Golumbic conjectured that the latter lower bound is essentially tight. In this talk I will discuss the notion of inducibility of graphs and digraphs, some of the few related known results and some of the many related open problems. I will also briefly indicate how M. Tyomkyn and I were able to improve the aforementioned upper bound of Pippenger and Golumbic.