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 |
F_{p} 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: PSL_{2}(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) |
F_{p} 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 F_{p}, 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 F_{p} 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 F_{p}, 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 F_{p} 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 K_{n} 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 G_{1}, ..., G_{n} 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 S ⊆ F^{n} is called (k, c)-evasive if it has intersection of size at most c with every k-dimensional affine subspace of F^{n}. A simple probabilistic argument shows that a random set S ⊂ F^{n} 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 S ⊂ F^{n} 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 (H, G) 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 = C_{d}, as n → ∞, asymptotically almost all graphs with n vertices and ⌊Cn^{2 - 1/d} log^{1/d}n⌋ 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 R^{d} 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 R^{d} is any subgraph of such a graph. We show that for any fixed d the number of complete distance graphs in R^{d} on n labelled vertices is 2^{(1 + o(1))dn log2n} while the number of distance graphs in R^{d} 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. |