Combinatorics Seminar 2011/2012
If
you are interested in talks of the previous years, please go to the Archive.
Abstracts
Benjamin Matschke, Equivariant topology
methods and the colored Tverberg problem 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. Roman Glebov, Rainbow matchings in hypergraphs 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. Joint work in progres with Benny Sudakov, Tibor Szabó, Yury Person and Anita Liebenau. Jan Hladky, Loebl-Komlos-Sos Conjecture and embedding trees in sparse graphs We prove an approximate version of the Loebl-Komlos-Sos 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 Szemeredi
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, Komlos, Simonovits and Szemeredi to resolve to Erdos-Sos
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 Janos Komlos,
Diana Piguet, Miki Simonovits,
and Endre Szemeredi. Tibor Szabó, Sharp threshold for bounded degree spanning trees
with many leaves or a long bare path
We show
that any given n-vertex tree with bounded maximum degree and linearly
many leaves is contained in the binomial random graph G(n,p) asymptotically almost surely for some p=(1+o(1))log
n/n. Furthermore we also show that G(n,p) 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.
Christoph Koch, On Kuratowski's Theorem
and the Kelmans-Seymour conjecture 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_5$. 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_5$? 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. Dieter Jungnickel, Klassische
Designs und ihre Codes
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 PGd(n,q) bzw. AGd(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. 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.
Guillem Perarnau, Identifying codes for regular graphs 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. Julia Wolf, Large sets
with little structure 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. David Conlon, On two strengthenings of
Ramsey's theorem 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 Erdos and improve upon results of Rodl
and Shelah. This is joint work with Jacob Fox and
Benny Sudakov. Andrew Treglown, Perfect packings in dense graphs 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 K_r-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 K_r-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. Mihyun Kang, The Bohman-Frieze process near criticality The Erd\H{o}s-R\'{e}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\H{o}s
and R\'{e}nyi states that the Erd\H{o}s-R\'{e}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\H{o}s-R\'{e}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\H{o}s-R\'{e}nyi process in terms of the size and structure of the components
near the critical point. (joint work with Perkins and Spencer) Yury Person, A randomized Version of Ramsey's theorem Jacob Fox, Chromatic
number, clique subdivisions, and the conjectures of Dmitry Shabanov, Colorings of uniform hypergraphs
with large girth and their Penny Haxell, On Ryser's Conjecture 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 $\nu$ 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 $r\nu$, but it is conjectured that there is
always a cover of size at most $(r-1)\nu$. Heidi Gebauer, Constructing a Non-Two-Colorable Hypergraph with Few Edges Asaf Ferber, The weak and strong k-connectivity games 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+Theta(k^2)
moves and that Red has a winning strategy in the analogues
strong game. Joint work with Dan Hefetz. Dennis Clemens, Fast strategies in Maker-Breaker games played on random boards A Maker-Breaker game is defined as follows: Given a
board $X$ and a set of winning
sets $F\subset 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\sim 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. Joint work with Asaf
Ferber, Anita Liebenau and Michael Krivelevich. Daniel Reichman, Random permutations and random subgraphs We describe how random permutations give rise to
random subgraphs of Christian Reiher, The clique density problem It is well known that by a theorem of Turán every graph on n vertices Yury Person, Twins in words 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. Anita Liebenau, A new bound on the largest tournament Maker can build Two players, usually called Maker and Breaker, play
the following Tran Manh Tuan, On the edge polytopes of finite graphs 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 Guenter Ziegler Boris Bukh, Generalized Erdős-Szekeres theorems We introduce a generalization of the Erdős-Szekeres theorem, Lothar Narins,
Home Base Hypergraphs and Ryser’s
Conjecture 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ó. Henning Thomas, Mastermind Luca Gugelmann, Random
Hyperbolic Graphs Many large real-world networks have degree sequences
which follow a power-law Peter Allen & Julia Böttcher, Tight cycles in
dense uniform hypergraphs Alexandru Tomescu, Extensional acyclic digraphs and set graphs Codrut Grosu, Following
a question of Boris Bukh 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 Erdos
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) > T^{1-\eps},
for some \eps > 0. Roman Glebov, On a conjecture of Erdős
and Sós 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. Combinatorics Seminar - Archive |