Combinatorics Seminar 2011/2012

Archive of old talks. The current schedule can be found here.

Date Speaker Title
23.08.2011 Benjamin Matschke
FU Berlin
Equivariant topology methods and the colored Tverberg problem
07.09.2011 Roman Glebov
FU Berlin
Rainbow matchings in hypergraphs
30.09.2011 Jan Hladky
Warwick Mathematics Institute
Loebl-Komlós-Sós Conjecture and embedding trees in sparse graphs
19.10.2011 Tibor Szabó
FU Berlin
Sharp threshold for bounded degree spanning trees with many leaves or a long bare path
28.10.2011 Christoph Koch
TU München
On Kuratowski's Theorem and the Kelmans-Seymour conjecture
04.11.2011 Dieter Jungnickel
Universität Augsburg
Klassische Designs und ihre Codes
11.11.2011 Guillem Perarnau
UPC Barcelona
Identifying codes for regular graphs
16.11.2011 Julia Wolf
École Polytechnique, Paris
Large sets with little structure
23.11.2011 David Conlon
University of Oxford
On two strengthenings of Ramsey's theorem
02.12.2011 Andrew Treglown
Charles University in Prague
Perfect packings in dense graphs
09.12.2011 Mihyun Kang
FU Berlin
The Bohman-Frieze process near criticality
16.12.2011 Yury Person
FU Berlin
A randomized Version of Ramsey's theorem
11.01.2012 Jacob Fox
MIT
Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz
18.01.2012 Dmitry Shabanov
Moscow State University
Colorings of uniform hypergraphs with large girth and their applications in Ramsey theory
25.01.2012 Penny Haxell
University of Waterloo
On Ryser’s Conjecture
08.02.2012 Heidi Gebauer
ETH Zürich
Constructing a Non-Two-Colorable Hypergraph with Few Edges
15.02.2012 Asaf Ferber
Tel Aviv University
The weak and strong k-connectivity games
22.02.2012 Dennis Clemens
FU Berlin
Fast strategies in Maker-Breaker games played on random boards
27.02.2012 - 23.03.2012 Tibor Szabó
FU Berlin
Mathias Schacht
University of Hamburg
David Conlon
University of Oxford
MDS Block Course: Extemal Combinatorics in Random Discrete Structures
18.04.2012 Daniel Reichman
The Weizmann Institute
Random permutations and random subgraphs
25.04.2012 Christian Reiher
Universität Rostock
The clique density problem
02.05.2012 Yury Person
FU Berlin
Twins in Words
09.05.2012 Anita Liebenau
FU Berlin
A new bound on the largest tournament Maker can build
16.05.2012 Tuan Tran
TU Berlin
On the edge polytopes of finite graphs
23.05.2012 Boris Bukh
University of Cambridge, CMU
Generalized Erdős-Szekeres theorems
30.05.2012 Lothar Narins
FU Berlin
Home Base Hypergraphs and Ryser's Conjecture
06.06.2012 Henning Thomas
ETH Zürich
Mastermind
08.06.2012 Luca Gugelmann
ETH Zürich
Random Hyperbolic Graphs
13.06.2012 Peter Allen & Julia Böttcher
London School of Economics
Tight cycles in dense uniform hypergraphs
20.06.2012 Alexandru Tomescu
TU Berlin
Extensional acyclic digraphs and set graphs
27.06.2012 Codruţ Grosu
FU Berlin
Following a question of Boris Bukh
04.07.2012 Roman Glebov
FU Berlin
On a conjecture of Erdős and Sós

Abstracts:

23.08.2011
Benjamin Matschke (FU Berlin)
Equivariant topology methods and the colored Tverberg problem
Abstract: The first part of this talk will be a quick survey on equivariant topology methods and how to use them in discrete geometry. The second part is about a particular application, the colored Tverberg problem, which is joint work with Pavle Blagojević and Günter Ziegler.
07.09.2011
Roman Glebov (FU Berlin)
Rainbow matchings in hypergraphs

Abstract: We investigate the following problem: given a (large) integer r and a (sufficiently large) integer t, we are presented an r-uniform r-partite multihypergraph that consists of f matchings of size t. What is the extremal number f = f(tr), such that we know that there exists a t-matching with every hyperedge coming from a different matching? We present an upper bound of order tr, improving a previous bound of Alon. We also present an observation leading to the intuition that the "extremal" examples live on a small number of vertices.

The aim of the talk is to equate our knowledge in the problem and to motivate further joint research in this and closely related problems.

Joint work in progres with Benny Sudakov, Tibor Szabó, Yury Person and Anita Liebenau.
30.09.2011
Jan Hladky (Warwick Mathematics Institute)
Loebl-Komlós-Sós Conjecture and embedding trees in sparse graphs

Abstract: We prove an approximate version of the Loebl-Komlós-Sós Conjecture which asserts that if half of the vertices of a graph G have degrees at least k then G contains each tree T of order k + 1 as a subgraph.

The proof of our result follows a strategy common to approaches which employ the Szemerédi Regularity Lemma: the graph G is decomposed, a suitable combinatorial structure inside the decomposition is found, and then the tree T is embedded into G using this structure. However the decomposition given by the Regularity Lemma is not of help when G sparse. To surmount this shortcoming we use a general decomposition technique (a variant of which was introduced by Ajtai, Komlós, Simonovits and Szemerédi to resolve to Erdős-Sós conjecture) which applies also to sparse graphs: each graph can be decomposed into vertices of huge degree, regular pairs (in the sense of the Regularity Lemma), and an expander-like part.

Joint work with János Komlós, Diana Piguet, Miki Simonovits, and Endre Szemerédi.
19.10.2011
Tibor Szabó (FU Berlin)
Sharp threshold for bounded degree spanning trees with many leaves or a long bare path
Abstract: We show that any given n-vertex tree with bounded maximum degree and linearly many leaves is contained in the binomial random graph G(np) asymptotically almost surely for some p = (1 + o(1))log n/n. Furthermore we also show that G(np) contains asymptotically almost surely every bounded degree spanning tree T that has a path of linear length whose vertices have degree two in T. This represents joint work with Dan Hefetz and Michael Krivelevich.
28.10.2011
Christoph Koch (TU München)
On Kuratowski's Theorem and the Kelmans-Seymour conjecture

Abstract: Kuratowski's well-known theorem gives a precise characterization of planar graphs - there are exactly two types of forbidden subgraphs in planar graphs: subdivisions of K3,3 and subdivisions of K5. Thus, a natural question to arise is the following: Are there classes of graphs such that we need only check for one type of these subdivisions in order to determine planarity? In the past decades there have been many results of that kind, but still some problems remain unsolved. One of them is the Kelmans-Seymour conjecture: Does every 5-connected non-planar graph contain a subdivided K5?

This talk will illustrate two main approaches towards this conjecture. In particular, there have been some partial results by various people within the last year.
04.11.2011
Dieter Jungnickel (Universität Augsburg)
Klassische Designs und ihre Codes

Abstract: Wir betrachten die endliche projektive bzw. affine Geometrie der Dimension n über dem endlichen Körper GF(q) mit q Elementen, also PG(nq) bzw. AG(nq). Die klassischen Designs zu einer derartigen Geometrie sind die Inzidenzstrukturen, die aus allen Punkten sowie allen d-dimensionalen Unterräumen der Geometrie gebildet werden (für ein d mit 1 ≤ dn - 1); sie werden üblicherweise als PGd(nq) bzw. AGd(nq) bezeichnet. Da es (exponentiell) viele Designs mit denselben Parametern wie die klassischen Designs gibt, möchte man diese schönen Beispiele unter allen Designs mit diesen Parametern charakterisieren.

Vor nahezu 50 Jahren hat Hamada eine codierungstheoretische Charakterisierung der klassischen Designs vorgeschlagen; jedoch ist die nach ihm benannte Vermutung trotz einiger Fortschritte in den letzten Jahren weiterhin weitgehend offen. Der Vortrag beschäftigt sich mit einer alternativen (von Hamada inspirierten, aber deutlich komplexeren) Möglichkeit, die klassischen Designs codierungstheoretisch zu charakterisieren. In einer gerade zur Publikation angenommenen gemeinsamen Arbeit mit V.D.Tonchev ist dies für alle projektiven und für viele affine Fälle (nämlich für d = 1 sowie (n - 2)/2 < dn - 1) gelungen; dabei konnten die affinen Fälle auf eine geometrische Vermutung reduziert werden, die sicherlich für alle d gilt, aber bisher nur im genannten Bereich verifiziert werden konnte.

Unsere Beweismethoden bestehen aus einem Zusammenspiel von kombinatorischen, geometrischen und codierungstheoretischen (also algebraischen) Argumenten. Dabei spielen einige sehr interessante (aber leider verhältnismäßig wenig bekannte) Ideen aus der Codierungstheorie (Spur-Codes, Galois-abgeschlossene Codes, Erweiterungscodes) eine entscheidende Rolle; diese Begriffe sind nicht vorausgesetzt, sondern werden im Vortrag erklärt.
11.11.2011
Guillem Perarnau (UPC Barcelona)
Identifying codes for regular graphs

Abstract: Given a graph G, an identifying code can be defined as a dominating set that identifies each vertex of G with a unique code. They have direct applications on detecting and locating a "failure" of a vertex in networks. We are mainly interested in bounding the size of a minimal code in terms of the maximum or minimum degree of G. The first part of the talk is devoted to give a new result that provides an asymptotically tight approximation to a conjecture stated by Foucaud, Klasing, Kosowski and Raspaud (2009) for a large class of graphs. In the second part we will talk about graphs with girth five, where better upper bounds can be given. Moreover, we use them to compute the minimal size of a code for random regular graphs with high probability.

This is a joint work with Florent Foucaud.
16.11.2011
Julia Wolf (École Polytechnique, Paris)
Large sets with little structure
Abstract: There has been much activity in the past twelve months regarding upper bounds on the density of sets containing no 3-term arithmetic progressions. We shall give an overview of some of these developments and subsequently examine the corresponding lower bounds for this problem. This includes joint work with Ben Green and Yuncheng Lin.
23.11.2011
David Conlon (University of Oxford)
On two strengthenings of Ramsey's theorem
Abstract: Ramsey's theorem states that every 2-colouring of the edges of the complete graph on {1, 2, ..., n} contains a monochromatic clique of order roughly log n. We prove new bounds for two extensions of Ramsey's theorem, each demanding extra structure within the monochromatic clique. In so doing, we answer a question of Erdős and improve upon results of Rödl and Shelah. This is joint work with Jacob Fox and Benny Sudakov.
02.12.2011
Andrew Treglown (Charles University in Prague)
Perfect packings in dense graphs

Abstract: We say that a graph G contains a perfect H-packing if there exists a set of vertex-disjoint copies of H which cover all the vertices in G. For all 'non-trivial' graphs H, the decision problem whether a graph G has a perfect H-packing is NP-complete. Thus, there has been significant attention on obtaining sufficient conditions which ensure a graph G contains a perfect H-packing.

The Hajnal-Szemerédi theorem states that a graph G whose order n is divisible by r has a perfect Kr-packing provided that the minimum degree of G is at least (1 - 1/r)n. In this talk our focus is on strengthening the Hajnal-Szemerédi theorem: Given integers n, r and d, we haracterise the edge density threshold that ensures a perfect Kr-packing in a graph G on n vertices and of minimum degree at least d. We also give two conjectures concerning degree sequence conditions which force a graph to contain a perfect H-packing. This is joint work with Jozsef Balogh and Alexandr Kostochka.
09.12.2011
Mihyun Kang (FU Berlin)
The Bohman-Frieze process near criticality

Abstract: The Erdős-Rényi random graph process begins with an empty graph on n vertices and edges are added randomly one at a time to a graph. A classical result of Erdős and Rényi states that the Erdős-Rényi process undergoes a phase transition, which takes place when the number of edges reaches n/2 and a giant component emerges.

In this talk we discuss the so-called Bohman-Frieze process, a simple modification of the Erdős-Rényi process. The Bohman-Frieze process begins with an empty graph on n vertices. At each step two random edges are present and if the first edge would join two isolated vertices, it is added to a graph; otherwise the second edge is added. We show that the Bohman-Frieze process has a qualitatively similar phase transition to the Erdős-Rényi process in terms of the size and structure of the components near the critical point.

(Joint work with Perkins and Spencer)
16.12.2011
Yury Person (FU Berlin)
A randomized Version of Ramsey's theorem

Abstract: The classical theorem of Ramsey states that for all integers k ≥ 2 there exists an integer R(k) such that no matter how one colors the edges of the complete graph KR(k) with two colors, there will always be a monochromatic copy of Kk.

Here we consider the following problem recently suggested by Allen, Böttcher, Hladky and Piguet. Let R(nq) be a random subset of all copies of F on a vertex set Vn of size n, in which every copy is present independently with probability q. For which functions q = q(n) can we color the edges of the complete graph on Vn with r colors such that no monochromatic copy of F is contained in R(nq)?

We also discuss the usual randomization of Ramsey's theorem for random (hyper-)graphs and its connection to the problem above.

This is joint work with Luca Gugelmann, Angelika Steger and Henning Thomas.
11.01.2012
Jacob Fox (MIT)
Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz.

Abstract: A famous conjecture of Hajos from 1961 states that every graph with chromatic number k contains a subdivision of the complete graph on k vertices.

This conjecture was disproved by Catlin in 1979. Erdős and Fajtlowicz further showed in 1981 that a random graph on n vertices almost surely is a strong counterexample to the Hajós conjecture. They further conjectured that in a certain sense a random graph is essentially the strongest possible counterexample among graphs on n vertices. We prove the Erdős-Fajtlowicz conjecture. Joint work with Choongbum Lee and Benny Sudakov.
18.01.2012
Dmitry Shabanov (Moscow State University)
Colorings of uniform hypergraphs with large girth and their applications in Ramsey theory
Abstract: Extremal problems concerning colorings of uniform hypergraphs arose in connection with classical theorems of Ramsey Theory. Our talk is devoted to the problem of estimating the maximum vertex degree of a uniform hypergraph with large girth and large chromatic number. This problem is not completely solved even in the case of graphs. We shall present some new results and show their applications for finding quantitative bounds in Ramsey's theorem and Van der Waerden's theorem. The proofs use a continuous-time random recoloring process based on Poisson stochastic processes.
25.01.2012
Penny Haxell (University of Waterloo)
On Ryser's Conjecture
Abstract: We discuss some old and new results and ideas on the following long-standing conjecture. Let H be an r-partite r-uniform hypergraph. A matching in H is a set of disjoint edges, and we denote by ν the maximum size of a matching. A cover of H is a set of vertices that intersects every edge. It is clear that there exists a cover of H of size , but it is conjectured that there is always a cover of size at most (r - 1)ν.
08.02.2012
Heidi Gebauer (ETH Zürich)
Constructing a Non-Two-Colorable Hypergraph with Few Edges
Abstract: We say that a given k-uniform hypergraph is non-two-colorable if every red/blue-coloring of its vertices yields an edge where all vertices have the same color. It is a long-standing open problem to determine the minimum number m(k) such that there exists a non-2-colorable k-uniform hypergraph with m(k) hyperedges. Erdős showed, using the probabilistic method, that m(k) ≤ O(k2·2k), and by a result of Radhakrishnan and Srinivasan, m(k) ≥ Ω(√(k/ln k) 2k). These are the best known bounds. This talk will be about an explicit construction of a non-two-colorable hypergraph with 2k(1 + o(1)) edges.
15.02.2012
Asaf Ferber (Tel Aviv University)
The weak and strong k-connectivity games

Abstract: In this talk we consider the weak and strong k-connectivity game played on the edge set of the complete graph. In the weak k-connectivity game, two players, Maker and Breaker, alternately claim free edges of the complete graph. Maker wins as soon as the graph consists of his edges is a (spanning) k-connected graph. If Maker doesn't win by the time all the edges of Kn are claimed then Breaker wins the game.

In the strong version of this game, two players Red and Blue, alternately claim free edges of Kn (Red is the first player to move). The winner is the first player to build a spanning k-connected graph.

We prove that in the weak k-connectivity game Maker has a winning strategy within nk/2 + Θ(k2) moves and that Red has a winning strategy in the analogues strong game.

Joint work with Dan Hefetz.
22.02.2012
Dennis Clemens (FU Berlin)
Fast strategies in Maker-Breaker games played on random boards

Abstract: A Maker-Breaker game is defined as follows: Given a board X and a set of winning sets F ⊂ 2X, two players, called Maker and Breaker, alternately take elements of X. If Maker occupies an element of F completely until the end of the game, he wins. Otherwise Breaker is the winner.

In the seminar I will present results about Maker-Breaker games played on the edge set of a sparse random graph G ~ Gn,p. We will consider the the perfect matching game, the Hamiltonicity game and the k-connectivity game. For p = logd(n)/n (with d large enough) we will see that Maker a.a.s. can win these games as fast as possible, i.e. in n/2 + o(n), n + o(n) and kn/2 + o(n) moves, respectively.

Joint work with Asaf Ferber, Anita Liebenau and Michael Krivelevich.
18.04.2012
Daniel Reichman (The Weizmann Institute)
Random permutations and random subgraphs

Abstract: We describe how random permutations give rise to random subgraphs of undirected graphs with interesting properties. We present applications to bootstrap percolation, proving existence of large k-degenerate graphs in bounded degree graphs as well as a new framework for designing algorithms for the independent set problem.

Joint work with Uri Feige
25.04.2012
Christian Reiher (Universität Rostock)
The clique density problem

Abstract: It is well known that by a theorem of Turán every graph on n vertices possessing more than (r - 2)n2/(2r - 2) edges has to contain a clique of size r, where r > 3 denotes some integer.

Given that result, it is natural to wonder what one can say about the number of r–cliques that have to be present in a graph on n vertices with at least γ·n2 edges, where γ > (r - 2)/(2r - 2) denotes some real parameter.

In awareness of the structure of the graph that is extremal for Turán’s original problem, it is quite tempting to suggest that the answer is provided by first choosing some appropriate integer s > r - 1 depending on γ alone and then constructing a complete (s + 1)–partite graph all of whose vertex classes except for one possibly smaller one are of equal size. This gives a number of r–cliques that is proportional to nr and it is an amazingly difficult problem to decide whether the factor of proportionality thus obtained is indeed (asymptotically) best possible. This question has first been asked by Lovász and Simonovits in the 1970s, and has remained widely open until very recently when Razborov introduced new analytical ideas and solved the case r = 3. Shortly afterwards, Nikiforov solved the case r = 4. In the talk, we will present the recent solution to this clique density problem, and discuss some related ideas of Lovász and Razborov concerning graph limits.
02.05.2012
Yury Person (FU Berlin)
Twins in words

Abstract: Suppose we are given a 0-1-sequence S of length n and we want to find two long identical non-overlapping (disjoint) sequences (twins) in S. Which length can one always guarantee? I will answer this question (asymptotically) and discuss some generalizations of it.

Joint work with Maria Axenovich and Svetlana Puzynina.
09.05.2012
Anita Liebenau (FU Berlin)
A new bound on the largest tournament Maker can build

Abstract: Two players, usually called Maker and Breaker, play the following positional game. Given a tournament T (a complete directed graph) on k vertices, they claim edges alternately from the complete graph Kn on n vertices. Maker also has to choose a direction for every edge she picks.

Maker wins this game as soon as her graph contains a copy of T.

In 2008, Beck showed that the largest clique Maker can build (that is, disregarding directions) is of order kc = (2 - o(1)) log n. Given n large enough, we show that Maker is able to build a tournament of order k = (2 - o(1)) log n = kc - 10. That is, building a tournament is almost as easy for Maker as building a clique of the same size.

This improves the lower bound of 0.5 log n (Beck 2008) and log n (Gebauer 2010). In particular, this result shows that the so called "random graph intuition" fails for the tournament game.

Joint work with Dennis Clemens and Heidi Gebauer.
16.05.2012
Tuan Tran (TU Berlin)
On the edge polytopes of finite graphs

Abstract: Given a finite graph G. The edge polytope P(G) of G is defined as the convex hull of the column vectors of the incidence matrix of G. In this talk we will discuss the following topics:

  1. A description of the low-dimensional faces of the polytope P(G)
  2. Non-linear relations between the components of the f-vector of P(G)
  3. Asymptotic growth rate of the maximum number of facets of a d-dimensional edge polytope.
This is the author's thesis, written under the supervision of Günter Ziegler
23.05.2012
Boris Bukh (University of Cambridge, CMU)
Generalized Erdős-Szekeres theorems

Abstract: We introduce a generalization of the Erdős-Szekeres theorem, and show how it can be applied to construct a strengthening of weak epsilon-nets.

We also discuss the decision problem for Erdős-Szekeres-type for arbitrary semialgebraic predicates.
30.05.2012
Lothar Narins (FU Berlin)
Home Base Hypergraphs and Ryser's Conjecture

Abstract: Ryser's Conjecture states that any r-partite r-uniform hypergraph has a vertex cover of size at most r - 1 times the size of the largest matching. For r = 2, the conjecture is simply König's Theorem. It has also been proven for r = 3 by Aharoni using topological methods. Our ambitious goal is to try to extend Aharoni's proof to r = 4. We are currently still far from this goal, but we start by characterizing those hypergraphs which are tight for the conjecture for r = 3. These we call home base hypergraphs. Our proof of this characterization is also based on topological machinery, particularly utilizing results on the (topological) connectedness of the independence complex of the line graph of a graph.

Joint work with Penny Haxell and Tibor Szabó.
06.06.2012
Henning Thomas (ETH Zürich)
Mastermind

Abstract: Most of you probably know the game of Mastermind: one player (the "codemaker") makes up a secret code word z = (z1z2, ..., zn) over an alphabet of size k, where in the classical board game (n = 4, k = 6) the symbols are represented by pegs of different colors. The other player (the "codebreaker") has to identify the code word by asking questions of the form x = (x1x2, ..., xn) over the same alphabet. The codemaker answers a question with a distance measure to the secret code by revealing (i) the number a(mx) of positions i for which zi = xi, in the original board game depicted by black pegs, and (ii) the maximum a(mq) over all permutations of q, originally depicted by white pegs.

In this talk we present some known upper and lower bounds as well as a new strategy which improves the currently best-known upper bounds for the case k = Θ(n) from O(n log n) questions to O(n log log n).

This is joint work with Benjamin Doerr, Reto Spöhel and Carola Winzen from MPI Saarbrücken.
08.06.2012
Luca Gugelmann (ETH Zürich)
Random Hyperbolic Graphs
Abstract: Many large real-world networks have degree sequences which follow a power-law (i.e. the number of vertices of degree k is of order k-a for some fixed a) and have large clustering coefficients (the average probability that two neighbors of a vertex are themselves adjacent). Unfortunately these properties seem difficult to reproduce in mathematically tractable random graph models. There are models for graphs with power-law degree sequences (e.g. preferential attachment) or models for graphs with large clustering coefficients (e.g. Watts-Strogatz) but to our knowledge none which reproduce both properties and yet still remain mathematically tractable. Recently Papadopoulos et al. introduced a random geometric graph model which is based on hyperbolic geometry and for which they claimed empirically and with some preliminary mathematical analysis that it satisfies both properties above. This model consists (in its simplest version) of n points sampled uniformly at random from a hyperbolic disc of radius R = R(n) which are connected if their hyperbolic distance is at most R. We (Konstantinos Panagiotou, Ueli Peter and the speaker) analyze this model rigorously and compute exact asymptotic expressions for the expected number of vertices of degree k (up to the maximum degree). We also prove concentration around these values. Further we compute asymptotic expressions for the average and maximum degree and a constant lower bound for the clustering coefficient.
13.06.2012
Peter Allen & Julia Böttcher (London School of Economics)
Tight cycles in dense uniform hypergraphs

Abstract: We prove an approximate version of the Erdős-Gallai theorem for tight cycles in uniform hypergraphs, and determine asymptotically the extremal codegree guaranteeing tight cycles of given lengths divisible by k in k-partite k-uniform hypergraphs. Our main tool is a simplification of the strong hypergraph regularity object which we expect to be of further use.

This is joint work with Julia Böttcher, Oliver Cooley and Richard Mycroft.
20.06.2012
Alexandru Tomescu (TU Berlin)
Extensional acyclic digraphs and set graphs

Abstract: A digraph is called 'extensional' if its vertices have pairwise distinct (open) out-neighborhoods. Extensional acyclic digraphs originate from set theory where they represent transitive closures of hereditarily finite sets.

We will present some results concerning the underlying graphs of extensional acyclic digraphs, which we call 'set graphs'. Even though we argue that recognizing set graphs is NP-complete, we show that set graphs contain all connected claw-free graphs and all graphs with a Hamiltonian path. In the case of claw-free graphs, we provide a polynomial-time algorithm for finding an extensional acyclic orientation.

Extensional digraphs can also be characterized in terms of a slight variation of the notion of separating code, which we call open-out-separating code. Concerning this, deciding if a digraph admits an open-out-separating code of given size is NP-complete.

Joint work with Martin Milanic and Romeo Rizzi
27.06.2012
Codruţ Grosu (FU Berlin)
Following a question of Boris Bukh

Abstract: Let f(x) be some polynomial with T non-zero real coefficients. Suppose we square this polynomial. What is a lower bound q(T) for the number of non-zero coefficients of f(x)2? It was a question of Erdős from 1949 that q(T) goes to infinity when T goes to infinity. This was solved by Schinzel in 1987, who proved q(T) > log log T. The result was recently (2009) improved by Schinzel and Zannier to log T. This is the proof I am going to present.

Bukh asked whether one can show q(T) > T1 - ε, for some ε > 0.
04.07.2012
Roman Glebov (FU Berlin)
On a conjecture of Erdős and Sós

Abstract: Erdős and Sós asked the following question: given a hypergraph on sufficiently many vertices with positive edge density on every linearly large vertex set, is it true that it contains a given subgraph? In particular, they raised this question for the case of 3-uniform hypergraphs with the subgraph of interest being the hypergraph K on 4 vertices and 3 edges. Rödl showed that, somewhat surprisingly, this lower density condition is not sufficient, giving an increasing sequence of hypergraphs not containing K and having density almost ¼ on every linearly large vertex set. In this talk, we show that the constant ¼ is optimal. The proof uses the computational flag algebra method.

Joint work in progress with Daniel Král’ and Jan Volec.