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(t, r), 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 t^r, 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.

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.

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 K_3,3 and subdivisions of K₅. 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 K₅?

Abstract: Wir betrachten die endliche projektive bzw. affine Geometrie der Dimension n über dem endlichen Körper GF(q) mit q Elementen, also PG(n, q) bzw. AG(n, q). 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 ≤ d ≤ n - 1); sie werden üblicherweise als PG_d(n, q) bzw. AG_d(n, q) 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 < d ≤ n - 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.

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.

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.

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.

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 K_R(k) with two colors, there will always be a monochromatic copy of K_k.

Here we consider the following problem recently suggested by Allen, Böttcher, Hladky and Piguet. Let R(n, q) be a random subset of all copies of F on a vertex set V_n 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 V_n with r colors such that no monochromatic copy of F is contained in R(n, q)?

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

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.

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 K_n are claimed then Breaker wins the game.

In the strong version of this game, two players Red and Blue, alternately claim free edges of K_n (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 + Θ(k²) moves and that Red has a winning strategy in the analogues strong game.

Abstract: A Maker-Breaker game is defined as follows: Given a board X and a set of winning sets F ⊂ 2^X, 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 ~ G_n,p. We will consider the the perfect matching game, the Hamiltonicity game and the k-connectivity game. For p = log^d(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.

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.

Abstract: It is well known that by a theorem of Turán every graph on n vertices possessing more than (r - 2)n²/(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 γ·n² edges, where γ > (r - 2)/(2r - 2) denotes some real parameter.

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.

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 K_n 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 k_c = (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 = k_c - 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.

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.

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.

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.

Abstract: Most of you probably know the game of Mastermind: one player (the "codemaker") makes up a secret code word z = (z₁, z₂, ..., z_n) 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 = (x₁, x₂, ..., x_n) over the same alphabet. The codemaker answers a question with a distance measure to the secret code by revealing (i) the number a(m, x) of positions i for which z_i = x_i, in the original board game depicted by black pegs, and (ii) the maximum a(m, q) 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).

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.

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.

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)²? 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.

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.