Combinatorics Seminar 2012/2013

Talks take place at Arnimallee 3, 14195 Berlin, Room 210 at 16:15, unless stated otherwise.

Date Speaker Title
01.11.2012 Dennis Clemens
FU Berlin
On balanced coloring games in random graphs
09.11.2012 - 10.11.2012 Berlin-Poznan Seminar
16.11.2012 - 17.11.2012 KolKom 2012
22.11.2012 Codruţ Grosu
FU Berlin
Fp is locally like C
29.11.2012 Roman Glebov
FU Berlin
Biased Hamiltonicity game on random boards
06.12.2012 Lothar Narins
FU Berlin
Cooperative Colorings and Independent Systems of Representatives
13.12.2012 Tuan Tran
FU Berlin
Subspace evasive sets
20.12.2012
10:00-18:00
Frederik Garbe
TuanTran
FU Berlin
Ramanujan Graphs: Algebraic Graph Theory
10.01.2013
10:00-18:00
Dennis Clemens
Lothar Narins
FU Berlin
Ramanujan Graphs: Number Theory
17.01.2013 Yoshiharu Kohayakawa
University of São Paulo
On the Density of Universal Random Graphs
31.01.2013
10:00-18:00
Codruţ Grosu
Anita Liebenau
FU Berlin
Ramanujan Graphs: PSL2(q)
14.02.2013
10:00-18:00
Tibor Szabó
Tuan Tran
FU Berlin
Ramanujan Graphs: The Construction
21.02.2013 Anita Liebenau
FU Berlin
Orientation Games
04.04.2013 Andrew McDowell
Royal Holloway, University of London
Non-vertex-balanced factors in random graphs
12.06.2013
14:00
Andrey Kupavskii
Moscow State University
Two notions of unit distance graphs
13.06.2013
16:00
Dmitry Shabanov
Moscow State University
Equitable two-colorings for simple hypergraphs
20.06.2013 Julia Böttcher
London School of Economics
A Blow-up Lemma for arrangeable graphs

Abstracts:

01.11.2012
Dennis Clemens (FU Berlin)
On balanced coloring games in random graphs

Abstract: Let F be some graph. Consider first the following one player game, known as balanced Ramsey game: The Player has r colors and in each round r random edges (that were never seen before) on n vertices are presented to her. Immediately, the Player has to color all these edges differently. The game ends as soon as a monochromatic copy of F appears.

Secondly consider the Achlioptas game: Here the Player only loses when she creates a copy of F in one distinguished color.

The main question is how long these games last typically. In the talk, we will get an overview of the recent results proven by Luca Gugelmann and Reto Spöhel: They compare the typical time (threshold) for both games, settling an open problem by M. Krivelevich, R. Spöhel and A. Steger. Furthermore, they consider vertex analogues of both games and show that here the thresholds coincide for all graphs F.
22.11.2012
Codruţ Grosu (FU Berlin)
Fp is locally like C

Abstract: Vu, Wood and Wood showed that any finite set S in a characteristic zero integral domain can be mapped to Fp, for infinitely many primes p, while preserving all algebraic incidences of S. In this talk we will show that the converse essentially holds, namely any small subset of Fp can be mapped to some finite algebraic extension of Q, while preserving bounded algebraic relations. This answers a question of Vu, Wood and Wood.

Most of the talk will be devoted to the presentation of applications of the main result. For small subsets of Fp, we: show that the Szemerédi-Trotter theorem holds with optimal exponent 4/3, improve the previously best-known sum-product estimate, transfer results from C to Fp concerning sets with small doubling constant, and so on.

We shall briefly give some insight into the proof of the main result, which is a simple application of elimination theory and is similar in spirit with the proof of the quantitative Hilbert Nullstellensatz.
29.11.2012
Roman Glebov (FU Berlin)
Biased Hamiltonicity game on random boards

Abstract: One of the first Maker-Breaker games that was analyzed when the concept was introduced is the Hamiltonicity game. Already Erdős and Chvátal found out that Maker can build a Hamilton cycle playing on the edge set of Kn for sufficiently large n. It took decades and several partial results of different authors before Krivelevich proved their conjecture and showed that the game in fact obeys the random graph intuition, showing that the critical bias is asymptotically log(n)/n.

In this talk, we consider the Hamiltonicity game played on the edge set of the random graph G(n, p) for some appropriate p. Confirming (and even strengthening) a conjecture of Stojaković and Szabó, we show that this game also follows the random graph intuition, that is, the critical bias is asymptotically np/log(n) a.a.s.. As far time permits, I present the main steps of the proof.

Joint work with A. Ferber, A. Naor, and M. Krivelevich.
06.12.2012
Lothar Narins (FU Berlin)
Cooperative Colorings and Independent Systems of Representatives
Abstract: Introduced by Aharoni, Holzman, Howard, and Sprüssel, a cooperative coloring of a system of graphs G1, ..., Gn on the same vertex set is a choice of one independent set from each graph such that they together cover the vertex set. This is closely related to the notion of independent systems of representatives (also called independent transversals), and in fact these two concepts can be translated into one another. Aharoni, Holzman, Howard, and Sprüssel investigate conditions under which a system has a cooperative coloring, in part utilizing a topological result of Meshulam.
13.12.2012
Tuan Tran (FU Berlin)
Subspace evasive sets

Abstract: Let F be a finite field. A subset SFn is called (kc)-evasive if it has intersection of size at most c with every k-dimensional affine subspace of Fn. A simple probabilistic argument shows that a random set SFn of size |F|(1 - ε)n will have intersection of size at most O(k/ε) with any k-dimensional affine subspace. Recently, Zeev Dvir and Schachar Lovett gave an explicit construction of a (k, (k/ε)k)-evasive set SFn of size |F|(1 - ε)n.

In this talk we will present the construction and its application in extremal combinatorics.
17.01.2013
Yoshiharu Kohayakawa (University of São Paulo)
On the Density of Universal Random Graphs

Abstract: We shall discuss a polynomial time randomized algorithm that, on receiving as input a pair (HG) of n-vertex graphs, searches for an embedding of H into G. If H has bounded maximum degree and G is suitably dense and pseudorandom, then the algorithm succeeds with high probability. Our algorithm proves that, for every integer d ≥ 3 and suitable constant C = Cd, as n → ∞, asymptotically almost all graphs with n vertices and ⌊Cn2 - 1/d log1/dn⌋ edges contain as subgraphs all graphs with n vertices and maximum degree at most d.

This is joint work with Domingos Dellamonica Jr., Vojtěch Rödl and Andrzej Ruciński.
21.02.2013
Anita Liebenau (FU Berlin)
Orientation Games

Abstract: In an orientation game, two players called OMaker and OBreaker take turns in directing previously undirected edges of the complete graph on n vertices. The final graph is a tournament. OMaker wins if this tournament has some predefined property P, otherwise OBreaker wins. We analyse the Oriented-cycle game, in which OMaker's goal is to close a directed cycle. Since this game is drastically in favour of OMaker, we allow OBreaker to direct (up to) b > 1 edges in each of his moves and ask for the largest b* such that OMaker has a winning strategy (the so called threshold bias). It is known that n/2 - 3 < b* < n - 2, where the upper bound was conjectured to be tight.

In this talk I will discuss recent developments in the field of orientation games, including a sketch of an OBreaker strategy which improves the upper bound on b* to roughly 5n/6.

Joint work with Dennis Clemens.
04.04.2013
Andrew McDowell (Royal Holloway, University of London)
Non-vertex-balanced factors in random graphs
Abstract: For a fixed graph H, and a (larger) graph G, an H-factor of G is a vertex disjoint collection of copies of H, that cover all the vertices of G. The simplest example is when H is a single edge, where an H-factor is just a perfect matching. We are interested in the threshold functions for the existence of an H-factor in the Erdős-Rényi random graph The case where H is a single edge has been known since 1964 but the case where H is a triangle is far more difficult and remained unsolved until the 2008 paper by Johansson, Kahn, and Vu, which found thresholds for all strictly balanced graphs. In this talk we outline difficulties of the problem and the various known cases, before showing how a generalisation of the strictly balanced case allows for proving the threshold for non-balanced graphs.
12.06.2013
Andrey Kupavskii (Moscow State University)
Two notions of unit distance graphs
Abstract: A complete (unit) distance graph in Rd is a graph whose set of vertices is a finite subset of the d-dimensional Euclidean space, where two vertices are adjacent if and only if the Euclidean distance between them is exactly 1. A (unit) distance graph in Rd is any subgraph of such a graph. We show that for any fixed d the number of complete distance graphs in Rd on n labelled vertices is 2(1 + o(1))dn log2n while the number of distance graphs in Rd on n labelled vertices is 2(1 - 1/⌊d/2⌋ + o(1))n2/2.
13.06.2013
Dmitry Shabanov (Moscow State University)
Equitable two-colorings for simple hypergraphs
Abstract: Equitable two-coloring for a hypergraph is a proper vertex coloring such that the cardinalities of color classes differ by at most one. The famous Hajnal-Szemerédi theorem states that for any graph G with maximum vertex degree d there is an equitable coloring with d + 1 colors. In our talk we shall discuss similar question for uniform hypergraphs and present a new bound in the Hajnal-Szemerédi-type theorem for the class of simple hypergraphs. The proof is based on the random recoloring method and the results of Lu and Székely concerning negative correlations in the space of random bijections.
20.06.2013
Julia Böttcher (London Schoool of Economics)
A Blow-up Lemma for arrangeable graphs

Abstract: The Blow-up Lemma is an important tool for embedding spanning graphs H into dense graphs G. One of its limitations is, however, that it can only be used if the maximum degree of H is bounded by a constant. We recently established a generalisation of this lemma which can handle even H which are only c-arrangeable (and observe a very weak maximum degree bound). Here a graph is called c-arrangeable if its vertices can be ordered in such a way that the neighbours to the right of any vertex v have at most c neighbours to the left of v in total.

In the talk I will explain this lemma, discuss several applications, and outline parts of the proof.

Joint work with Yoshiharu Kohayakawa, Anusch Taraz and Andreas Würfl.