Schedule

Abstract.  In this talk, we will consider the following two-player game, parametrised by positive integers n and k . The game is played between Painter and Builder, alternately taking turns, with Painter moving first. The game starts with the empty graph on n vertices. In each round Painter colours a vertex of her choice by one of the k colours and Builder claims an edge between two previously unconnected vertices. Both players should maintain that during the game the graph admits a proper k-colouring. The game ends if either all n vertices have been coloured, or Painter has no legal move. In the former case, Painter wins the game, in the latter one Builder is the winner. We prove that the minimal number of colours k = k(n) allowing Painter's win is of logarithmic order in the number of vertices n. Biased versions of the game will also be considered. This is joint work with Małgorzata Bednarska-Bzdęga, Michael Krivelevich and Viola Mészároz.

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.