Combinatorics Seminar 2011/2012

If you are interested in talks of the previous years, please go to the Archive.




July 4, 2012

Roman Glebov

FU Berlin

On a conjecture of Erdős and Sós

June 27, 2012

Codrut Grosu

FU Berlin

Following a question of Boris Bukh

June 20, 2012

Alexandru Tomescu

TU Berlin

Extensional acyclic digraphs and set graphs

June 13, 2012

Peter Allen & Julia Böttcher

London School of Economics

Tight cycles in dense uniform hypergraphs

June 8, 2012

Luca Gugelmann

ETH Zürich

Random Hyperbolic Graphs

June 6, 2012

Henning Thomas

ETH Zürich


May 30, 2012

Lothar Narins

FU Berlin

Home Base Hypergraphs and Ryser’s Conjecture

May 23, 2012

Boris Bukh

University of Cambridge, CMU

Generalized Erdős-Szekeres theorems

May 16, 2012

Tran Mahn Tuan

TU Berlin

On the edge polytopes of finite graphs

May 9, 2012

Anita Liebenau

FU Berlin

A new bound on the largest
tournament Maker can build

May 2, 2012

Yury Person

FU Berlin

Twins in Words

April 25, 2012

Christian Reiher

Universität Rostock

The clique density problem

April 18, 2012

Daniel Reichman

The Weizmann Institute

Random permutations and random subgraphs

February 27 – March 23, 2012

Tibor Szabó

FU Berlin

Mathias Schacht

University of Hamburg

David Conlon

University of Oxford

MDS Block Course:
Extemal Combinatorics in Random Discrete Structures

February 22nd, 2012

Dennis Clemens

FU Berlin

Fast strategies in Maker-Breaker games 
played on random boards

February 15th, 2012

Asaf Ferber

Tel Aviv University

The weak and strong k-connectivity games

February 8th, 2012

Heidi Gebauer

ETH Zurich

Constructing a Non-Two-Colorable

Hypergraph with Few Edges

January 25th, 2012

Penny Haxell

University of Waterloo

On Ryser’s Conjecture

January 18th, 2012

Dmitry Shabanov

Moscow State University

Colorings of uniform hypergraphs with large girth and their applications in Ramsey theory

January 11th, 2012

Jacob Fox


Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz

December 16th, 2011

Yury Person

FU Berlin

A randomized Version of Ramsey's theorem

December 9th, 2011

Mihyun Kang

FU Berlin

The Bohman-Frieze process near criticality

December 2nd, 2011

Andrew Treglown

Charles University in Prague

Perfect packings in dense graphs

November 23rd, 2011

David Conlon

University of Oxford

On two strengthenings of Ramsey's theorem

November 16th, 2011

Julia Wolf

École Polytechnique, Paris

Large sets with little structure

November 11th, 2011

Guillem Perarnau

UPC Barcelona

Identifying codes for regular graphs

November 4th, 2011

Dieter Jungnickel

Universität Augsburg

Klassische Designs und ihre Codes

October 28th, 2011

Christoph Koch

TU München

On Kuratowski's Theorem

and the Kelmans-Seymour conjecture

October 19th, 2011

Tibor Szabó 
Freie Universität Berlin

Sharp threshold for bounded degree

spanning trees with many leaves or a long

bare path

September 30th, 2011

Jan Hladky

Warwick Mathematics Institute

Loebl-Komlos-Sos Conjecture and

embedding trees in sparse graphs

September 7th, 2011

Roman Glebov
FU Berlin

Rainbow matchings in hypergraphs

August 23rd, 2011

Benjamin Matschke
FU Berlin

Equivariant topology methods

and the colored Tverberg problem




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



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



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



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
The classical theorem of Ramsey states that for all integers $k \ge 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\"ottcher, Hladky and Piguet. Let $\mathcal{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

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.


Jacob Fox, Chromatic number, clique subdivisions, and the conjectures of
Hajós and Erdös-Fajtlowicz.
A famous conjecture of Hajos from 1961 states that every graph
with chromatic number k contains a subdivision of the complete graph on k
This conjecture was disproved by Catlin in 1979. Erdos and Fajtlowicz
further showed in 1981 that a random graph on n vertices almost surely is a
strong counterexample to the Hajos 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
Erdos-Fajtlowicz conjecture. Joint work with Choongbum Lee and Benny


Dmitry Shabanov, Colorings of uniform hypergraphs with large girth and their
applications in Ramsey theory

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.


Penny Haxell, On Ryser's Conjecture
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 $\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
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. Erdos showed, using the probabilistic
method, that m(k) <= O(k^2 * 2^k), and by a result of Radhakrishnan and
Srinivasan, m(k) >= \Omega(\sqrt(k/ln k) 2^k). These are the best known
bounds. This talk will be about an explicit construction of a
non-two-colorable hypergraph with 2^(k(1+o(1)) 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
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


Christian Reiher, The clique density problem

It is well known that by a theorem of Turán every graph on n vertices
possessing more than (r-2)n^2/(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 \gamma·n^2 edges, where \gamma > (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 \gamma 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.


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.
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.


Anita Liebenau, A new bound on the largest tournament Maker can build

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.
Joint work with Dennis Clemens and Heidi Gebauer.


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,
and show how it can be applied to construct a strengthening of weak
We also discuss the decision problem for Erdős-Szekeres-type for
arbitrary semialgebraic predicates.


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
Most of you probably know the game of Mastermind: one player (the "codemaker") makes up a secret code word z=(z_1, z_2, ..., 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_1, x_2, ..., 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 = \Theta(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.


Luca Gugelmann, Random Hyperbolic Graphs

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.


Peter Allen & Julia Böttcher, Tight cycles in dense uniform hypergraphs
We prove an approximate version of the Erdos-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 Boettcher, Oliver Cooley and Richard Mycroft.


Alexandru Tomescu, Extensional acyclic digraphs and set graphs
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
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


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

·         Combinatorics Seminar 2009/2010

·         Combinatorics Seminar 2010/2011