Research Seminar Combinatorics | Berlin Math Seminars

Combinatorics

Mon, 21.10.24 at 14:15

T9/046

Victor Falgas-Ravry Umea University

1-independent percolation on high dimensional lattices

Abstract

Combinatorics

Thu, 17.10.24 at 16:15

Arnimallee 3

Joseph Fehribach Worcester Polytechnic Institute

Families of Kirchhoff Graphs

Abstract

Combinatorics

Thu, 22.08.24 at 16:15

Arnimallee 3

Gregory Sorkin London School of Economics and Political Science

Matchings and Loose Cycles in the Semirandom Hypergraph Model

Combinatorics

Thu, 22.08.24 at 16:15

Arnimallee 3

Anita Liebenau UNSW Sydney

Ramsey with purple edges

Combinatorics

Thu, 22.08.24 at 16:15

Arnimallee 3

Shagnik Das National Taiwan University

Fractionally Intersecting Families

Combinatorics

Thu, 22.08.24 at 16:15

Arnimallee 3

Michael Anastos Institute of Science and Technology Austria

Climbing up a random subgraph of the hypercube

Combinatorics

Wed, 03.07.24 at 16:15

Arnimallee 3

Jie Han Beijing Institute of Technology

Graph Theory theorems in random graphs

Combinatorics

Wed, 26.06.24 at 16:15

Arnimallee 3

Tibor Szabó Freie Universität Berlin

Global rigidity of random graphs in R

Combinatorics

Wed, 05.06.24 at 16:15

Arnimallee 3

Dhruv Mubayi University of Illinois

New bounds for the Erdős-Rogers problem

Combinatorics

Tue, 28.05.24 at 10:00

A7/031

Richard Lang University Hamburg

A hypergraph bandwidth theorem

Combinatorics

Wed, 14.02.24 at 16:15

Arnimallee 3

Yannick Mogge TUHH

Creating a tree universal graph in positional games

Combinatorics

Thu, 08.02.24 at 16:15

Arnimallee 3

Michael Krivelevich Tel Aviv University

Improving graph's parameters through random perturbation

Combinatorics

Thu, 01.02.24 at 16:15

Arnimallee 3

Peter Martin FU Berlin

Lower bounds on Ramsey multiplicity of cliques.

Combinatorics

Thu, 25.01.24 at 16:15

Arnimallee 3

Alexandra Wesolek TU Berlin

Cops and Robber Game on Surfaces

Combinatorics

Wed, 17.01.24 at 16:15

Arnimallee 3

Michael Krivelevich Tel Aviv University

Percolation through isoperimetry

Combinatorics

Thu, 11.01.24 at 16:15

Arnimallee 3

Raphael Steiner ETH Zürich

Hadwiger's conjecture and topological bounds.

Combinatorics

Fri, 17.11.23 at 16:15

Arnimallee 3

Jan Volec Czech Technical University in Prague

On the minimum eigenvalue of regular triangle-free graphs

Combinatorics

Thu, 02.11.23 at 16:15

Arnimallee 3

Yamaan Attwa FU Berlin

Erdős-Hajnal is true for an infinite family of prime graphs. Part II

Combinatorics

Thu, 26.10.23 at 16:15

Arnimallee 3

Yamaan Attwa FU Berlin

Erdős-Hajnal is true for an infinite family of prime graphs. Part I

Combinatorics

Wed, 23.08.23

Chaoliang Tang Fudan University

Turán number of the linear 3-graph Crown

Abstract.

Let the crown C13 be the linear 3-graph on 9 vertices {a,b,c,d,e,f,g,h,i} with edges E = {{a,b,c}, {a, d,e}, {b, f, g}, {c, h,i}}. Proving a conjecture of Gyárfás et. al., we show that for any crown-free linear 3-graph G on n vertices, its number of edges satisfy |E(G)| ≤ 3(n - s)/2, where s is the number of vertices in G with degree at least 6. This result, combined with previous work, essentially completes the determination of linear Turán number for linear 3-graphs with at most 4 edges.The result is the joint work with my tutor Hehui Wu and my fellow Zeyu Zheng. It is also simutaneously proved by Shengtong Zhang.

Combinatorics

Wed, 19.07.23

Silas Rathke FU Berlin

The asymptotics of R(4,t)

Abstract.

The Ramsey number R(4,t) is the minimum number n of vertices such that each 2-colouring of K_n either contains a red K_4 or a blue K_t. Erdős conjectured that this should essentially grow with the order t^3. For forty years, there has not been any progress on that problem. Until last month, when Mattheus and Verstraete proved this conjecture.In the talk, I will present their proof. It combines a concrete algebraic construction with some probabilistic arguments.

Combinatorics

Tue, 11.07.23

Anand Srivastav Christian-Albrechts-Universität zu Kiel

A new Bound for the Maker-Breaker Triangle Game

Combinatorics

Thu, 06.07.23

Patrick Morris Universitat Politècnica de Catalunya

The canonical Ramsey theorem in random graphs: even cycles and list constraints

Abstract.

The celebrated canonical Ramsey theorem of Erdős and Rado implies that for a given graph H, if n is sufficiently large then any colouring of the edges of Kn gives rise to copies of H that exhibit certain colour patterns, namely monochromatic, rainbow or lexicographic. We are interested in sparse random versions of this result and the threshold at which the random graph G(n,p) inherits the canonical Ramsey properties of Kn. We will discuss a theorem that pins down this threshold when we focus on colourings that are constrained by some prefixed lists and also a related result on the threshold for the canonical Ramsey property (with no list constraints) in the case that H is an even cycle.This represents joint work with José D. Alvarado, Yoshiharu Kohayakawa and Guilherme O. Mota.

Combinatorics

Wed, 21.06.23

Olaf Parczyk FU Berlin

Graphs with large minimum degree and no small odd cycles are 3-colourable

Abstract.

Let Ƒ be a fixed family of graphs. The homomorphism threshold of Ƒ is the infimum of those α for which there exists an Ƒ-free graph H=H(Ƒ, α), such that every Ƒ-free graph on n vertices of minimum degree αn is homomorphic to H. Letzter and Snyder showed that the homomorphism threshold of {C3,C5} is 1/5. They also found explicit graphs H({C3,C5}, α), for α > 1/5, which were in addition 3-colourable. Thus, their result also implies that {C3,C5}-free graphs of minimum degree at least (1/5+ ε)n are 3-colourable. For longer cycles, Ebsen and Schacht showed that the homomorphism threshold of {C3,C5,…,C2l-1} is 1/(2l-1). However, their proof does not imply a good bound on the chromatic number of{C3,C5,…,C2l-1}-free graphs of minimum degree n/(2l-1). Answering a question of Letzter and Snyder, we prove that such graphs are 3-colourable. In fact, we prove a stronger result that works with a slightly smaller minimum degree.This is joint work with Julia Böttcher, Nóra Frankl, Domenico Mergoni Cecchelli, and Jozef Skokan.

Combinatorics

Wed, 17.05.23

Dingyuan Liu FU Berlin

On the number of sets with bounded sumset

Abstract.

We will study the counting problem of sets with bounded sumset. More precisely, let m,n be natural numbers, for an n-element subset Y of an arbitrary abelian group, we give upper bounds on the number of sets A ⊆Y with |A+A| ≤ m according to the range of m. Furthermore, we also give an upper bound for the refined version of this problem, improving the previous result of Campos and confirming an earlier conjecture of Alon, Balogh, Morris, and Samotij in a certain range.This is joint work with Leticia Mattos and Tibor Szabó.

Combinatorics

Wed, 10.05.23

Ákos Magyar University of Georgia

On a conjecture of Graham in geometric Ramsey theory

Abstract.

Let's call a finite point configuration F in a Euclidean space "Ramsey" if any finite coloring of a sufficiently high dimensional Euclidean space contains a monochromatic isometric copy of F. After some initial investigations of Erdos, Graham at al., Graham conjectured that a set F is Ramsey if and only if it is spherical, i.e. if it can be inscribed into a sphere.We outline a new approach and some new results based on some modern tools of additive combinatorics, such as the use of (geometric) uniformity norms and arithmetic regularity lemmas both in the context of Euclidean spaces as well as in the model case of vector spaces over finite fields.

Combinatorics

Thu, 04.05.23

Avi Wigderson IAS, Princeton

Approximate Sylvester-Gallai, and applications

Abstract.

Assume you have a finite set of points in real space, with the property that every line through any pair of these points meets a third point. This property is satisfied when all points are colinear, and the (so called) Sylvester-Gallai theorem states that this is the only way!In this talk we explore approximate versions of the assumption, in which the hypothesis holds "on average". I'll motivate this question from applications in coding theory and algebraic complexity. I'll then prove bounds on the dimension of the point set under such relaxed hypothesis. The proof in interesting in that in combines combinatorial, algebraic and analytic arguments, each of them simple to explain.Based on (old) joint works with Barak, Dvir, Saraf and Yehudayoff.The talk is self contained - no special background is assumed.

Combinatorics

Wed, 03.05.23

Adam Schweitzer TU Berlin

The Chow ring of matroids and the Rota-Welsh conjecture - Part II

Abstract.

Recently methods in combinatorial Hodge theory have been used successfully to settle long standing conjectures about certain characteristic sequences of matroids.This talk will introduce some of the central concepts and theorems of this theory for the case of matroids, without delving into the underlying algebraic geometry, and use it to give parts of June Huh's proof of the Rota-Welsh conjecture.

Combinatorics

Thu, 27.04.23

Adam Schweitzer TU Berlin

The Chow ring of matroids and the Rota-Welsh conjecture - Part I

Abstract.

Recently methods in combinatorial Hodge theory have been used successfully to settle long standing conjectures about certain characteristic sequences of matroids.This talk will introduce some of the central concepts and theorems of this theory for the case of matroids, without delving into the underlying algebraic geometry, and use it to give parts of June Huh's proof of the Rota-Welsh conjecture.

Combinatorics

Wed, 15.03.23

Gregory Sorkin London School of Economics and Political Science

Extremal Cuts and Isoperimetry in Random Cubic Graphs

Abstract.

The minimum bisection width of random cubic (3-regular) graphs is of interest because it is one of the simplest questions imaginable in extremal combinatorics. An additional reason is that the minimum bisection of (general) cubic graphs plays a role in the construction of efficient exponential-time algorithms, and it seems likely that random cubic graphs are extremal.It is known that a random cubic graph has a minimum bisection of size at most 1/6 times its order (indeed this is known for all cubic graphs), and we reduce this upper bound to below 1/7 (to 0.13993) by analyzing an algorithm with a couple of surprising features. We increase the corresponding lower bound on minimum bisection using the Hamilton cycle model of a random cubic graph. (The Hamilton cycle approach had also decreased the upper bound on maximum cut, but this has since been improved upon by making rigorous a 2010 conjecture from statistical physics.)

Combinatorics

Wed, 01.03.23

Stefanie Gerke Royal Holloway, University of London

The k-th shortest s-t path in a weighted complete graph

Abstract.

Suppose we weight the edges of the complete graph Kn with independent exponential Exp(1) random weights, pick two distinct vertices s and t,and then successively construct and then remove the edges of minimal weight s-t paths. We describe asymptotically the distributions of the weights of the first k paths obtained in this process. In particular we show that the mean weight of the k-th path is (log n + γ + 2ζ(3) + 2ζ(5) + ... + 2ζ(2k − 1) + o(1))/n as n → when k is a constant, and where γ is the Euler--Mascheroni constant and ζ is the Riemann zeta function. This is joint work with P. Balister.

Combinatorics

Wed, 08.02.23

Silas Rathke FU Berlin

Pseudorandom Ramsey graphs

Abstract.

In recent years, the theory of pseudorandom graphs have received considerable attention in combinatorial research. One question raised was, how pseudorandom Ks-free graphs can be. A note by Mubayi and Verstraëte published in 2019 describes a link between pseudorandom graphs and Ramsey numbers: They show that if pseudorandom Ks-free graphs exist, then the Ramsey number r(s,t) can be bounded from below. In this talk, we will look at this note. We will try to understand the link in detail. Could pseudorandom graphs really be the "the central tool required to determine classical graph Ramsey numbers" as the authors suggest?

Combinatorics

Wed, 25.01.23

Yamaan Attwa FU Berlin

Towards the Erdős-Hajnal conjecture for P5

Abstract.

The Erdős-Hajnal Conjecture is one of the most well-known problems in extremal combinatorics. It states that in contrast to the general n-vertex graph, if one forbids any fixed graph H as an induced subgraph, instead of a tight guarantee of a logarithmic-size homogeneous set, one can guarantee a homogeneous set of polynomial size. While the conjecture is far from being fully resolved, it is known to be true for some forbidden subgraphs of small order. The smallest forbidden subgraph for which the conjecture remains open is the path on five vertices. In this talk I intend to review a recent paper by Blanco and Bucić guaranteeing a homogeneous set of size 2Ω(log(n)^2/3) in P5-free graphs. This result is an improvement to the 2Ω(log(n)^1/2) size of a homogeneous set guaranteed by a result of Erdős and Hajnal for any forbidden subgraph.

Combinatorics

Thu, 19.01.23

Alberto Espuny Díaz TU Ilmenau

Threshold for (some) spanning trees in random geometric graphs

Abstract.

Consider the following model of random graphs: a total of n vertices are assigned to uniformly random positions on the unit square, independently of each other, and any two vertices are then joined by an edge if the distance between their positions is less than a given parameter r. This is called the random geometric graph G(n,r) and, similarly to the binomial random graph G(n,p), increasing properties exhibit thresholds (with respect to the parameter r) which we wish to understand. The behaviour of random geometric graphs, however, is very different from the behaviour of G(n,p). In this talk, I will highlight some of these differences and eventually focus on the case of balanced s-ary trees, for which we have established the threshold. This is based on joint work with Lyuben Lichev, Dieter Mitsche and Alexandra Wesolek.

Combinatorics

Wed, 11.01.23

Tibor Szabó FU Berlin

Results, problems, and a couple of proofs from Oberwolfach

Combinatorics

Thu, 08.12.22

Leticia Mattos FU Berlin

Bounds For Essential Covers Of The Cube

Abstract.

An essential cover of the vertices of the n-cube {-1,1}n by hyperplanes is a minimal covering where no hyperplane is redundant and every variable appears in the equation of at least one hyperplane. Linial and Radhakrishnan gave a construction of an essential cover with n/2+1 hyperplanes and showed that √n hyperplanes are required. Recently, Yehuda and Yehudayoff improved the lower bound by showing that any essential cover of the n-cube contains at least n0.52 hyperplanes. In this talk, we show that n5/9 hyperplanes are needed. This is based on a joint work with Araujo and Balogh.

Combinatorics

Thu, 24.11.22

Aldo Kiem ZIB

Flag Algebras for Edge-Colored Graphs

Abstract.

Flag Algebras is a highly successive formalism to study problems in extremal combinatorics. It has achieved the best known bounds for Turán’s (3,4)-problem as well as tight bounds for the three color Ramsey multiplicity of the triangle, Erdös’s Pentagon conjecture and a conjecture of Erdös and Sós on the asymptotic frequency of Rainbow triangles. What is special about Flag Algebras is that a significant amount of work in finding a Flag Algebra proof certificate can be automated by relaxing the given problem to a semidefinite program (SDP). In this talk, we will formally define Flag Algebras with many examples from the theory of c-edge-colored complete graphs. We will then see how to set up a Flag Algebra SDP and will discuss methods, old and new, to reduce the size of the SDP as well as splitting it up into smaller blocks. Finally, we will present our newest calculation for the four color Ramsey multiplicity of the triangle. This is joint work with Prof. Pokutta (TU Berlin and ZIB) and Dr. Christoph Spiegel (ZIB).

Combinatorics

Wed, 16.11.22

Olaf Parczyk FU Berlin

A general approach to transversal versions of Dirac-type theorems

Abstract.

Given a collection of m hypergraphs on the same vertex set, an m-edge graph F is a transversal if there is each edge comes from a different graph of the collection. How large does the minimum degree of each graph in the collection need to be so that it necessarily contains a copy of F that is a transversal? Each graph in the collection could be the same hypergraph, hence the minimum degree of each of them needs to be large enough to ensure that it individually contains F. In this talk, we discuss a unified approach to this problem by providing a widely applicable sufficient condition for this lower bound to be asymptotically tight. This is general enough to recover many previous results in the area and obtain novel transversal variants of several classical Dirac-type results for (powers of) Hamilton cycles. This is joint work with Pranshu Gupta, Fabian Hamann, Alp Müyesser, and Amedeo Sgueglia.

Combinatorics

Wed, 09.11.22

Giulia Codenotti FU Berlin

Flatness constants and lattice-reduced convex bodies

Abstract.

The lattice width of a convex body measures how "thin" the body is in lattice directions. The so-called flatness theorem states that in each fixed dimension there is an upper bound for the lattice width of a special class of convex bodies, those which are hollow. In this talk we introduce these definitions and certain generalizations thereof and look at the few known extremal hollow convex bodies achieving maximum lattice width. This leads us to a conjecture about extremal convex bodies, namely that they are lattice-reduced. This class of convex bodies has not been previously studied, and we present (many) questions and (some) answers about such lattice-reduced convex bodies.

Combinatorics

Wed, 02.11.22

David Fabian FU Berlin

Graph bootstrap percolation of random graphs

Abstract.

Given graphs H and G the H-bootstrap process on G is the process that starts with G and in which at each step every edge that is the only missing edge in a copy of H is added. Any such process stabilises after a finite number of steps. The maximum running time MH(n) is the largest number of steps of an H-bootstrap process when H is fixed and G ranges over all graphs on n vertices. In this talk we investigate MH(n) when H is distributed as the random graph G(k,p). We will show that for p = ω(log(k)/k) the maximum running time is bounded from below by ckn² for some ck>0. This is joint work with Patrick Morris and Tibor Szabó.

Combinatorics

Wed, 19.10.22

Michaela Borzechowski FU Berlin

A Universal Construction for Unique Sink Orientations

Abstract.

A Unique Sink Orientation (USO) is an orientation of the hypercube graph, such that the induced subgraph of every non-empty subcube contains exactly one sink. USOs can be used to capture the combinatorial structure of many essential algebraic and geometric problems. Unfortunately, there is no known algorithm that verifies if a given orientation is actually USO and which runs in polynomial time in the dimension of the cube. Out of the many possible orientations for a given cube only few of them are USO. But still, for a cube of a fixed dimension, the number of USOs is exponential in the dimension. To generate bounds on the total number of USOs, construction techniques are needed. They are also useful to find counterexamples to suspected properties of USOs. Furthermore, families of ''bad'' USOs provide examples to show lower bounds for the worst-case runtime of algorithms. While there are some construction methods for USOs, until now they have not been able to generate all possible USOs. In this talk we present a new construction framework which can be applied to all USOs and with which we can generate every n-dimensional USO using only USOs of dimension n-1 or lower. Our universal construction was inspired by techniques from cube tilings of space. This is joint work with Joseph Doolittle (TU Graz) and Simon Weber (ETH Zürich)

Combinatorics

Tue, 26.07.22

Shagnik Das NTW

Tight bounds for divisible subdivisions

Abstract.

Alon and Krivelevich proved that for every n-vertex subcubic graph H and every integer q ≥ 2 there exists a (smallest) integer f = f(H,q) such that every Kf-minor contains a subdivision of H in which the length of every subdivision-path is divisible by q. Improving their superexponential bound, we show that f(H, q) ≤ 10.5qn + 8n + 14q, which is optimal up to a constant multiplicative factor. This is joint work with Nemanja Draganić and Raphael Steiner.

Combinatorics

Wed, 20.07.22

Thomas Lesgourgues UNSW

Minimum degree of minimal Ramsey graphs for cliques

Abstract.

A graph G is r-Ramsey for a graph H, if every r-colouring of the edges of G contains a monochromatic copy of H. The graph G is called r-Ramsey-minimal for H if it is r-Ramsey for H but no proper subgraph of G possesses this property. In 1976, Burr, Erdős and Lovász introduced the study of the smallest minimum degree sr(k) of a graph G such that G is r-Ramsey-minimal for a complete graph of size k. They were able to show the rather surprising exact result, that with two colours, then s2(k) = (k-1)2. The behaviour of this function is still not so well understood for more than 2 colours. In 2016, Fox, Grinshpun, Liebenau, Person, and Szabó showed that for r > 2, sr(k) is at most 8(k-1)6r3. The speaker, together with John Bamberg and Anurag Bishnoi, have recently used a group theoretic model of generalised quadrangles introduced by Kantor in 1980, coupled with a probabilistic approach, to improve this bound.

Combinatorics

Wed, 06.07.22

Bjarne Schülke Caltech

A local version of Katona's intersection theorem

Abstract.

Katona's intersection theorem states that every intersecting family ℱ ⊆ [n](k) satisfies |∂ℱ| ≥ |ℱ|, where ∂ℱ = {F\x : x∊F∊ℱ} is the shadow of ℱ. Frankl conjectured that for n>2k and every intersecting family ℱ⊆ [n](k), there is some i∊[n] such that |∂ℱ(i)| ≥ |ℱ(i)|. Here, we prove this conjecture in a very strong form for n > (k+1)k/2. In particular, our result implies that for any j∊[k], there is a sequence a1,...,aj∊[n] such that |∂ℱ(a1,...,aj)| ≥ |ℱ(a1,...,aj)|. Further, Frankl conjectured that for n > k+ℓ and cross-intersecting families G⊆ [n](ℓ) and ℋ⊆ [n](k), there is some i∊[n] such that |∂G(i)| ≥ |G(i)| or |∂ℋ(i)| ≥ |ℋ(i)|. We prove this conjecture again in a very strong form for n > kℓ. This is joint work with Marcelo Sales.

Combinatorics

Wed, 22.06.22

Jan-Hendrik de Wiljes FU Berlin

Peg Solitaire on Graphs

Abstract.

The single-player board game (Peg) Solitaire has been around for centuries and eventually attracted researchers from mathematics and computer science. Recently, but certainly very naturally, peg solitaire was extended to graphs. The game rules are as follows: Place pegs on all vertices but one of a (connected) finite simple graph G. If u,v and w are vertices of G such that uv and vw are edges of G and there are pegs on u and v but not on w, then it is possible to jump with the peg from u onto w removing the peg from v in the process. Usually one tries to eliminate all but one peg from the graphs vertices by using such jumps, calling a graph solvable if that is possible. This talk serves as an introduction to the game and provides an overview of major developments and open problems. Moreover, typical methods used in the proofs of known results will be presented. Several variations of the game, for example a misère version, were also considered recently, some of which will be discussed in this talk as well.

Combinatorics

Wed, 15.06.22

Adam Schweitzer Berlin Mathematical School

Clique number of Xor products of Kneser graphs

Abstract.

Given two graphs, G and H, let us denote by V(G), V(H) and E(G), E(H) their vertex and edge sets respectively. Define the Xor product, s the graph with the vertex set V=V(G) × V(H), and two vertices (g,h) and (g',h') are connected if and only if among the statements gg' ∊ E(G) and hh' ∊ E(H) exactly one occurs. In this talk we examine the clique number of the Xor product of two isomorphic KG(N,k) Kneser graphs, denote this number with f(k,N). We discuss the background of the problem and we give lower and upper bounds on f(k,N). Furthermore we determine f(k,N) up to a constant deviation depending only on k, and find the exact value for f(2,N) if N is large enough. We also compute that f(k,k2) is asymptotically equivalent to k2.

Combinatorics

Wed, 08.06.22

Walner Mendonça ISTA

Tiling edge-coloured graphs with few monochromatic bounded-degree graphs

Abstract.

Gerencsér and Gyárfás proved in 1967 that for any 2-colouring of the edges of the complete graph with n vertices, Kn, it is possible to partition V(Kn) into two monocromatic paths. This result, which has a straightforward proof, motivated many other challenging problems that have been extensively studied in the last years. For instance, an open conjecture of Erdős, Gyárfás and Pyber from 1991 states that for any r-colouring of the edges of Kn there are r monochromatic paths partitioning V(Kn). We can also find in the literature other versions of the problem where instead of partitioning into paths, we are interested in partitioning into trees, cycles, or even power of cycles. Grinshpun and Sárközy studied a more general version of the problem where they were interested in partitioning V(Kn) into few monochromatic subgraphs which are copies of a given family of bounded degree graphs. They proved that for any family of graphs S = {F1, F2, F3, ...} such that Fi has exactly i vertices and maximum degree at most D, the following holds: for any 2-colouring of edges of Kn, there is a partition of V(Kn) into at most exp(O(D log D)) monochromatic subgraphs that are copies of graphs from S. They conjectured that for any r-colouring of the edges of Kn, it is possible to partition V(Kn) into exp(DC) monochromatic subgraphs that are copies of graphs from S, where C=C(r) is a constant that only depends on r. In this talk, we present the first progress towards Grinshpun-Sárközy conjecture by establishing a super-exponential bound.

Combinatorics

Wed, 01.06.22

Nina Kamčev University of Zagreb

The Turán density of 3-uniform tight cycles

Abstract.

Turán-type problems for hypergraphs are famously interesting and difficult. For example, for 3-uniform hypergraphs, the Turán density of F is known for very few hypergraphs F. The topic of this talk are Turán-type problems for 3-uniform tight cycles Ck, where the number of vertices k is not divisible by 3. The Turán density of a family of 3-graphs F, denoted π(F) , is the limit of the maximum density of an n-vertex 3-graph not containing a member of F. There is an iterated construction of a C5-free 3-graph Hn with edge density asymptotic to 2√3−3 ≈ 0.464 due to Mubayi and Rödl. Razborov showed that π(C5) ≤ 0.468, indicating that Hn might be optimal for C5. We show that Hn is asymptotically optimal for an enlarged family of graphs - namely, π(FK) = 2√3−3, where FK is the family of tight cycles whose length k is not divisible by 3 and is bounded by an absolute constant K. One of our main tools, which may be of independent interest, is a 3-uniform analogue of the statement `a graph is bipartite if and only if it does not contain an odd cycle'. Joint work with Shoham Letzter and Alexey Pokrovskiy.

Combinatorics

Wed, 25.05.22

Peter Allen LSE

Packing degenerate graphs

Abstract.

A simple random greedy algorithm can almost perfectly pack graphs with bounded degeneracy and almost linear maximum degree into the complete graph. I will explain how the algorithm works and sketch the analysis. In some situations, one can add further ideas to get from almost perfect packings to perfect packings. I will describe two ways, which together prove the Gýarfás Tree Packing Conjecture (which says that T1,...,Tn pack into Kn, where each Ti has i vertices) with a restriction cn/log n on the maximum degree of the trees. This is joint work with Julia Böttcher, Dennis Clemens, Jan Hladký, Diana Piguet and Anusch Taraz.

Combinatorics

Thu, 05.05.22

Anita Liebenau UNSW

Uncommon and Sidorenko systems of equations

Abstract.

A system of linear equations L over the finite field Fq is common if the number of solutions to L in any two-colouring of Fqn is asymptotically (as n→∞) at least the expected number of monochromatic solutions in a random colouring of Fqn. For example, a Schur triple x+y=z was shown to be common by Cameron, Cilleruelo and Serra in 2007. Another heavily studied specific example is that of an arithmetic progression of length four (4-AP), which can be described by two equations of the form x - 2y + z = 0 and y - 2z + w = 0. Wolf showed that these are uncommon (over ZN and over F5). Motivated by these existing results on specific systems, as well as extensive research on common and Sidorenko graphs, the systematic study of common systems of linear equations was recently initiated by Saad and Wolf. Building on earlier work of Cameron, Cilleruelo and Serra, common linear equations have been fully characterised by Fox, Pham and Zhao. In this talk, we discuss recent progress towards characterising common systems of two or more equations. In particular, we prove that any system containing a 4-AP is uncommon, confirming a conjecture of Saad and Wolf. We also discuss the related concept of Sidorenko systems of equations. Joint work with Nina Kamčev and Natasha Morrison.

Combinatorics

Wed, 04.05.22

Patrick Morris UPC

Schur properties of randomly perturbed sets

Abstract.

A set A of integers is said to be Schur if any two-colouring of A results in monochromatic x,y and z with x+y=z. We discuss the following problem: how many random integers from [n] need to be added to some A ⊆ [n] to ensure with high probability that the resulting set is Schur? Hu showed in 1980 that when |A| > ⌈4n/5⌉, no random integers are needed, as A is already guaranteed to be Schur. Recently, Aigner-Horev and Person showed that for any dense set of integers A ⊆ [n], adding ω(n1/3) random integers suffices, noting that this is optimal for sets A with |A| ≤ ⌈n/2⌉. We close the gap between these two results by showing that if A ⊆ [n] with |A| = ⌈n/2⌉+t <⌈4n/5⌉, then adding ω(min{n1/3,nt-1}) random integers will with high probability result in a set that is Schur. Our result is optimal for all t, and we further initiate the study of perturbing sparse sets of integers A by providing nontrivial upper and lower bounds for the number of random integers that need to be added in this case. Joint work with Shagnik Das and Charlotte Knierim.

Combinatorics

Thu, 21.04.22

Guilherme Oliveira Mota USP

Constrained colourings of random graphs

Abstract.

Given graphs G, H1 and H2, let G --> (H1,H2) denote the property that in every edge-colouring of G there is a monochromatic copy of H1 or a rainbow copy of H2. The constrained Ramsey number, defined as the minimum n such that Kn --> (H1,H2), exists if and only if H1 is a star or H2 is a forest. We determine the threshold for the property G(n,p) --> (H1,H2) when H2 is a forest. This is a joint work with Maurício Collares, Yoshiharu Kohayakawa and Carlos Gustavo Moreira.

Combinatorics

Wed, 13.04.22

Dávid Matolcsi Eötvös Loránd University

Avoiding right angles and certain Hamming distances

Abstract.

In this paper we show that the largest possible size of a subset of Fqn avoiding right angles, that is, distinct vectors x,y,z such that x−z and y−z are perpendicular to each other is at most O(nq−2). This improves on the previously best known bound due to Naslund and refutes a conjecture of Ge and Shangguan. A lower bound of nq/3 is also presented. It is also shown that a subset of Fqn avoiding triangles with all right angles can have size at most O(n2q−2). Furthermore, asymptotically tight bounds are given for the largest possible size of a subset A ⊂ Fqn for which x−y is not self-orthogonal for any distinct x,y ∊ A. The exact answer is determined for q=3 and n ≡ 2 (mod 3).Our methods can also be used to bound the maximum possible size of a binary code where no two codewords have Hamming distance divisible by a fixed prime q. Our lower- and upper bounds are asymptotically tight and both are sharp in infinitely many cases.

Combinatorics

Wed, 13.04.22

András Imolay Eötvös Loránd University

Multicolor Turán Numbers

Abstract.

We consider a natural generalisation of Turán's forbidden subgraph problem and the Ruzsa-Szemerédi problem by studying the maximum number exF(n,G) of edge-disjoint copies of a fixed graph F can be placed on an n-vertex ground set without forming a subgraph G whose edges are from different F-copies. We determine the pairs {F,G} for which the order of magnitude of exF(n,G) is quadratic and prove several asymptotic results using various tools from the regularity lemma and supersaturation to graph packing results.

Combinatorics

Thu, 17.02.22

Simona Boyadzhiyska FU Berlin

Fixed-point cycles and envy-free division

Abstract.

Given an edge-labeling of the complete bidirected graph K⃡n with functions from [d] to itself, we call a cycle in K⃡n a fixed-point cycle if composing the labels of its edges results in a map that has a fixed point; the labeling is fixed-point-free if no fixed-point cycle exists. In this talk we will consider the following question: for a given d, what is the largest value of n for which there exists a fixed-point-free edge-labeling of K⃡n with functions from [d] to itself? This problem was recently introduced by Chaudhury, Garg, Mehlhorn, Mehta, and Misra and has close connections to fair allocation in social choice theory. We will also discuss the special case where the edges are labeled with permutations of [d], which is related to a problem recently studied by Alon and Krivelevich and by Mészáros and Steiner. This is joint work with Benjamin Aram Berendsohn and László Kozma.

Combinatorics

Wed, 09.02.22

Benjamin Aram Berendsohn FU Berlin

The Diameter of Graph Associahedra

Abstract.

Graph Associahedra are a family of polytopes that generalize several well-known polytopes such as Associahedra, Permutohedra, and Cyclohedra. The skeleton of a Graph Associahedron corresponds to the rotation graph of the elimination trees on a fixed graph. In this talk, we study the diameter of Graph Associahedra, or, in other words, the maximum rotation distance between two elimination trees on a fixed graph G. We survey several known results and then focus on the case where G is a caterpillar tree, calculating the diameter of each Caterpillar Associahedron up to a constant factor.

Combinatorics

Wed, 02.02.22

Samuel Mohr Masaryk University

Uniform Turán density

Abstract.

In the early 1980s, Erdős and Sós initiated the study of the classical Turán problem with a uniformity condition: the uniform Turán density of a hypergraph H is the infimum over all d for which any sufficiently large hypergraph with the property that all its linear-size subhyperghraphs have density at least d contains H. In particular, they raise the questions of determining the uniform Turán densities of K4(3)- and K4(3). The former question was solved only recently in [Israel J. Math. 211 (2016), 349--366] and [J. Eur. Math. Soc. 97 (2018), 77--97], while the latter still remains open for almost 40 years. In addition to K4(3)- , the only 3-uniform hypergraphs whose uniform Turán density is known are those with zero uniform Turán density classified by Reiher, Rödl and Schacht~[J. London Math. Soc. 97 (2018), 77--97] and a specific family with uniform Turán density equal to 1/27. In this talk, we give an introduction to the concept of uniform Turán densities, present a way to obtain lower bounds using color schemes, and give a glimpse of the proof for determining the uniform Turán density of the tight 3-uniform cycle Cℓ(3), ℓ ≥ 5.

Combinatorics

Wed, 26.01.22

Kalina Petrova ETHZ

Resilience of Loose Hamilton Cycles in Random 3-Uniform Hypergraphs

Abstract.

Consider a random 3-uniform hypergraph H ~ H3(np) on n vertices, where each triple of vertices form a hyperedge with probability p. In this work, we prove a resilience result for H with respect to the property of containing a loose Hamilton cycle, that is, a cycle in which consecutive edges overlap in one vertex. More specifically, we show that there is a C s.t. if p >= C n-3/2 log(n), H is with high probability such that any spanning subgraph of H with minimum degree at least (7/16 + o(1)) p (n-1) (n-2) / 2 has a loose Hamilton cycle. This is optimal with respect to the resilience constant, but presumably not with respect to p. We also show a corresponding result about minimum co-degree, which is optimal with respect to both the resilience constant and p. Namely, there is a C s.t. if p >= C n-1 log(n), H is with high probability such that any spanning subgraph of H in which each pair of vertices is in at least (1/4 + o(1)) p (n-2) edges has a loose Hamilton cycle. This is joint work with Miloš Trujić.

Combinatorics

Thu, 20.01.22

Tibor Szabó FU Berlin

Improved Integrality Gap in Restricted Max-Min Allocation

Abstract.

In the max-min allocation problem a set P of players are to be allocated disjoint subsets of a set R of indivisible resources, such that the minimum utility among all players is maximized. We study the restricted variant, also known as the Santa Claus problem, where each resource has an intrinsic positive value, and each player covets a subset of the resources. Bezakova and Dani showed that this problem is NP-hard to approximate within a factor less than 2, consequently a great deal of work has focused on approximate solutions. The principal approach for obtaining approximation algorithms has been via the Configuration LP (CLP) of Bansal and Sviridenko. Accordingly, there has been much interest in bounding the integrality gap of this CLP. The existing algorithms and integrality gap estimations are all based one way or another on the combinatorial augmenting tree argument of Haxell for finding perfect matchings in certain hypergraphs. Our main innovation is to introduce the use of topological methods for the restricted max-min allocation problem, to replace the combinatorial ones. This approach yields substantial improvements in the integrality gap of the CLP. In particular we improve the previously best known bound of 3.808 to 3.534. The talk represents joint work with Penny Haxell.

Combinatorics

Wed, 12.01.22

Amedeo Sgueglia LSE

Multi-round Maker-Breaker Games

Abstract.

We consider a new procedure, which we call Multi-round Maker-Breaker Game. Maker and Breaker start from G0:=Kn and play several rounds of a usual Maker-Breaker game, where, for i ≥ 1, the i-th round is played as follows. They claim edges of Gi-1 until all edges are distributed, and then they set Gi to be the graph consisting only of Maker's edges. They will then play the next round on Gi. This creates a sequence of graphs G0 ⊃ G1 ⊃ G2 ⊃ ... and, given a monotone graph property, the question is how long Maker can maintain it, i.e. what is the largest k such that Maker has a strategy to guarantee that Gk satisfies such property. We will answer this question for several graph properties. This is joint work with Juri Barkey, Dennis Clemens, Fabian Hamann, and Mirjana Mikalački.

Combinatorics

Wed, 05.01.22

Felix Clemen UIUC

Max cuts in triangle-free graphs

Abstract.

A well-known conjecture by Erdős states that every triangle-free graph on n vertices can be made bipartite by removing at most n2/25 edges. This conjecture is known to be true for graphs with edge density at least 0.4 and also for graphs with edge density at most 0.172. We present progress on this conjecture; we prove the conjecture for graphs with edge density at most 0.2486 and for graphs with edge density at least 0.3197. Further, we prove that every triangle-free graph can be made bipartite by removing at most n2/23.5 edges improving the previously best bound of n2/18. Time permitting, we will discuss related questions. This is joint work with József Balogh and Bernard Lidický.

Combinatorics

Thu, 16.12.21

Olaf Parczyk FU Berlin

Density of triangles and independent sets of size three

Abstract.

The triangle-density of a graph G is the number of triangles in G divided by the number of possible triangles. In this talk we will characterise all pairs (x,y), where x is the triangle-density in G and y the triangle-density in the complement of G. This is based on two papers of Huang, Linial, Naves, Peled, and Sudakov.

Combinatorics

Wed, 08.12.21

Alberto Espuny Díaz TU Ilmenau

Path decompositions of random directed graphs

Abstract.

In this talk we consider the problem of decomposing the edges of a directed graph into as few paths as possible. The minimum number of paths needed in such an edge decomposition is called the path number of the digraph. The problem of determining the path number is generally NP-hard. However, there is a simple lower bound for the path number of a digraph in terms of its degree sequence, and a conjecture of Alspach, Mason, and Pullman from 1976 states that this lower bound gives the correct value of the path number for any even tournament. The conjecture was recently resolved, and in this talk I will discuss to what extent the conjecture holds for other digraphs. In particular, I will discuss some of the ingredients of a recent result showing that the conjecture holds with high probability for the random directed graph Dn,p for a large range of p. This is joint work with Viresh Patel and Fabian Stroh.

Combinatorics

Wed, 01.12.21

Simón Piga Universität Hamburg

Codegree threshold for cycle decompositions in 3-uniform hypergraphs

Abstract.

We show that 3-graphs on n vertices whose codegree is at least (2/3+o(1))n can be decomposed into tight cycles of fixed length, subject to the trivial necessary divisibility conditions. We also provide a construction showing this result is best possible up to the o(1) term. All together, our results solve a recent conjecture by Glock, Kühn, and Osthus.

Combinatorics

Wed, 24.11.21

Pedro Araújo Czech Academy of Sciences

Tight Hamilton cycles in uniformly dense hypergraphs

Abstract.

We study Hamiltonicity in quasirandom hypergraphs. We show that if an n-vertex 3-uniform hypergraph H=(V,E) has the property that for any set of vertices X and for any collection P of pairs of vertices, the number of hyperedges composed by a pair belonging to P and one vertex from X is at least (1/4+o(1))|X||P| - o(|V|³) and H has minimum vertex degree at least Ω(|V|²), then H contains a tight Hamilton cycle. A probabilistic construction shows that the constant 1/4 is optimal in this context. We will also discuss possible extensions to higher uniformities.

Combinatorics

Thu, 18.11.21

Leticia Mattos FU Berlin

Hitting all maximum independent sets

Abstract.

For a graph G on n vertices and independence number a(G) = an, let a'(G)=a'n denote the average value of the independence number of the induced subgraph of G on a uniform random set of vertices. Very recently, Friedgut, Kalai and Kindler (FKK) raised the following conjecture: for any a < 1/2 there is an c(a)>0 so that for every graph G with n vertices and independence number an, we have a'(G) < a - c(a). In this literature seminar, we will show a result of Alon which proves the FKK conjecture in the range where a > 1/4. We will also show his other result which states that the FKK conjecture holds for regular graphs when a > 1/8. If time allows, we will also show Alon's counterexamples for another related conjecture raised by FKK.

Combinatorics

Wed, 10.11.21

Michael Anastos FU Berlin

Determining the Hamiltonicity of sparse graphs in polynomial expected time

Abstract.

The Hamilton cycle problem asks to determines whether a given graph G has a Hamilton cycle. It belongs to the list of Karp’s 21 NP-complete problems and if P ≠ NP then there does not exist an algorithm that determines the Hamiltonicity of G in poly(n) time for every graph G on n vertices. On the other hand Gurevich and Shelah gave an algorithm that determines the Hamiltonicity of an n-vertex graph in poly(n) time on average. Equivalently the expected running time of their algorithm over the input distribution G ∼ G(n, p) is polynomial in n when p = 1/2. The last statement raises the question for which values of p there exist an algorithm that solves the Hamilton cycle problem in polynomial expected running time over the input distribution G ∼ G(n, p). Gurevich and Shelah, Thomason and Alon and Krivelevich gave such an algorithm for p ∈ [0, 1] being constant, p ≥ 12n−1/3 and p ≥ 70n-1/2 respectively. In this talk we present an algorithm which solves the Hamilton cycle problem in polynomial expected running time over the input distribution G ∼ G(n, p) for p ≥ 500/n.

Combinatorics

Thu, 21.10.21

Leticia Mattos FU Berlin

Clique packings in random graphs

Abstract.

Let u(n,p,k) be the k-clique packing number of the random graph G(n,p), that is, the maximum number of edge-disjoint k-cliques in G(n,p). In 1992, Alon and Spencer conjectured that for p = 1/2 we have u(n,p,k) = Ω(n²/k²) when k = k(n,p) - 4, where k(n,p) is minimum t such that the expected number of t-cliques in G(n,p) is less than 1. This conjecture was disproved a few years ago by Acan and Kahn, who showed that in fact u(n,p,k) = O(n²/k³) with high probability, for any fixed p ∈ (0,1) and k = k(n,p) - O(1). In this talk, we show a lower bound which matches Acan and Kahn's upper bound on u(n,p,k) for all p ∈ (0,1) and k = k(n,p) - O(1). To prove this result, we follow a random greedy process and use the differential equation method. This is a joint work with Simon Griffiths and Rob Morris.

Combinatorics

Thu, 15.07.21

Tássio Naia Universidade de São Paulo

Tree-like structures in dense digraphs

Abstract.

What large structures appear in every dense digraph? A celebrated result of Komlós, Sárközy and Szemerédi, answering a conjecture of Bollobás, states that for all ε > 0, every sufficiently large graph of order n and minimum degree n(1/2 + ε) contains every spanning tree of bounded maximum degree. This was later strengthened by the same authors to allow trees of degree c_ε n/log n (where c_ε is a constant depending on ε). The result has also been extended in a large number of directions. In this talk, we discuss a generalization of this result for digraphs: for all ε > 0, every sufficiently large digraph G of order n and minimum semidegree n(1/2 + ε) contains every spanning tree of bounded degree (the minimum semidegree of G is the minimum of in- and out-degrees over all vertices of G). In fact, our method establish the presence of a much more general family of arbitrarily oriented spanning subdigraphs, such as large subdivisions of a small graph, or collections of o(n^1/4) vertex-disjoint cycles. Ths is joint work with Richard Mycroft.

Combinatorics

Thu, 08.07.21

Alp Müyesser FU Berlin

Transversals in multiplication tables of abelian groups

Abstract.

Given an n x n matrix M filled in with arbitrary symbols, a transversal is a selection of n entries of M which do not share a row, a column, or a symbol. When M is the multiplication table of a finite group G, Hall and Paige conjectured in 1955 that M has a transversal if and only if the Sylow 2-subgroups of G are trivial or non-cyclic. In 2009, Wilcox, Evans, and Bray gave a proof of this conjecture using the classification of finite simple groups. Giving a characterisation of sub-matrices of M with transversals is currently open, and even the abelian case is not fully understood. In this talk, we will characterise sub-matrices of multiplication tables of abelian groups which admit transversals. In particular, we will address a conjecture of Snevily from 1999. This is joint work with Alexey Pokrovskiy.

Combinatorics

Wed, 30.06.21

Igor Balla Tel Aviv University

Equiangular lines and graph spectra

Abstract.

A set of lines passing through the origin in Rr is called equiangular if every pair of lines makes the same angle. In 1973, Lemmens and Seidel asked to determine the maximum number Nα(r) of equiangular lines in Rr with common angle arccos(α). Recently, B., Dräxler, Keevash, and Sudakov showed that Nα(r) ≤ 2r-2 for any fixed α ∈ (0,1) when r is exponentially large in 1/α, with equality if and only if α = 1/3. Building on their work, Jiang, Tidor, Yao, Zhang, and Zhao were able to determine Nα(r) completely for all α such that there exists a graph whose spectral radius is (1/α-1)/2 and when r is at least doubly exponentially large in 1/α. In both cases, the approach crucially relies on using Ramsey's theorem in order to bound the maximum degree of a corresponding graph. In this talk we will discuss how we can use orthogonal projections of matrices with respect to the Frobenius inner product in order to overcome this limitation and thereby prove new bounds on Nα(r) which effectively bridge the gap between 2r(1+o(1)) when α = Θ(1) and (1-o(1))r2/2 when α = Θ(1/r1/2), as well as significantly improving on the only previously known universal bound Nα(r) ≤ 2/3 · r/α2 · (1+o(1)), due to Glazyrin and Yu. Using the connection to real equiangular lines, our methods can also be used to obtain bounds on eigenvalues of the adjacency matrix of a regular graph. In particular, we show that for any k-regular graph on n vertices whose adjacency matrix has second and last eigenvalue λ2 and λn such that the spectral gap satisfies k - λ2 = o(n), we have λ2 ≥ (1 - o(1)) max(k1/3, (-λn)1/2). In fact, our bounds work up to O(1) provided that the spectral gap is slightly smaller than n/2, and since we do not need an assumption on the diameter, this can be seen as the first generalization of the Alon-Boppana theorem to dense graphs. Finally, we note that our method provides new inequalities involving the corresponding Gram matrix, which become equalities whenever there exist r·(r+1)/2 equiangular lines in Rr. We also derive analogous inequalities for complex equiangular lines and time permitting, we will discuss how our results generalize to this setting.

Combinatorics

Wed, 23.06.21

Olaf Parczyk LSE

Resilience for Hamiltonicity in random hypergraphs

Abstract.

Sudakov and Vu introduced the concept of local resilience of graphs for measuring robustness with respect to satisfying a given property. A classical result of Dirac states that any subgraph G of the complete graph on n vertices of minimum degree n/2 contains a Hamilton cycle. In the binomial random graph G(n,p) the threshold for the appearance of a Hamilton cycle is log(n)/n. Lee and Sudakov generalised Dirac’s result to random graphs by showing that with p > C log(n)/n asymptotically almost surely any subgraph G of G(n,p) with minimum degree (1/2+ε)n contains a Hamilton cycle, where C depends only on ε>0. These kind of resilience problems in random graphs received a lot of attention. In this talk we discuss a generalisation of the result of Lee and Sudakov to tight Hamilton cycles in random hypergraphs. This is joint work with Peter Allen and Vincent Pfenninger.

Combinatorics

Wed, 16.06.21

Julian Sahasrabudhe University of Cambridge

The singularity probability of random symmetric matrices

Abstract.

Let Mn be drawn uniformly from all {+1,-1}-symmetric n by n matrices. We consider the following basic problem: what is the probability Mn is singular? While the analogous problem for matrices with all entries independent is now well understood, the case of symmetric matrices has remained somewhat more mysterious, despite the attention it has received. In this talk I will discuss our recent result which shows that the singularity probability is exponentially small. This talk is based on joint work with Marcelo Campos, Matthew Jenssen and Marcus Michelen.

Combinatorics

Thu, 10.06.21

Simona Boyadzhiyska FU Berlin

Ramsey simplicity of random graphs

Abstract.

We say that a graph G is q-Ramsey for another graph H if any q-coloring of the edges of G yields a monochromatic copy of H. Much of the research related to Ramsey graphs is concerned with determining the smallest possible number of vertices in a q-Ramsey graph for a given H, known as the q-color Ramsey number of H. In the 1970s, Burr, Erdős, and Lovász initiated the study of another graph parameter in the context of Ramsey graphs: the minimum degree. A straightforward argument shows that, if G is a minimal q-Ramsey graph for H, then we must have δ(G) ≥ q(δ(H) - 1) + 1, and we say that H is q-Ramsey simple if this bound can be attained. In this talk, we will ask how typical Ramsey simplicity is; more precisely, we will discuss for which pairs p and q the random graph G(n,p) is almost surely q-Ramsey simple. This is joint work with Dennis Clemens, Shagnik Das, and Pranshu Gupta.

Combinatorics

Wed, 02.06.21

Giulia Maesaka Universität Hamburg

Embedding spanning subgraphs in uniformly dense and inseparable graphs

Abstract.

In this talk we consider sufficient conditions for the existence of k-th powers of Hamiltonian cycles in n-vertex graphs G with minimum degree μn for arbitrarily small μ>0. About 20 years ago Komlós, Sarközy, and Szemerédi resolved the conjectures of Pósa and Seymour and obtained optimal minimum degree conditions for this problem by showing that μ=k/(k+1) suffices for large n. For smaller values of μ, the given graph G must satisfy additional assumptions. We show that inducing subgraphs of density d>0 on linear subsets of vertices and being inseparable, in the sense that every cut has density at least μ>0, are sufficient assumptions for this problem and, in fact, for a variant of the bandwidth theorem. This generalises recent results of Staden and Treglown. Joint work with O. Ebsen, C. Reiher, M. Schacht and B. Schülke

Combinatorics

Wed, 26.05.21

Leticia Mattos IMPA

Asymmetric Ramsey properties of random graphs for cliques and cycles

Abstract.

We say that G ⟶ (F,H) if in every red and blue colouring of the edges of G we can find a red copy of F or a blue copy of H. In 1997, Kohayakawa--Kreuter conjectured the value of the threshold for this property when G is a random graph G(n,p). In this talk, we sketch the proof of Kohayakawa--Kreuter conjecture for the case that F is a clique and H is a cycle. Our main tool is a structural characterisation of Ramsey graphs for pairs of cliques and cycles. Joint work with Anita Liebenau, Walner Mendonça and Jozef Skokan.

Combinatorics

Wed, 19.05.21

Hong Liu University of Warwick

Sublinear expander and embeddings in sparse graphs

Abstract.

A notion of sublinear expander has played a central role in the resolutions of a couple of long-standing conjectures in embedding problems in graph theory, including e.g. the odd cycle problem of Erdos and Hajnal that the harmonic sum of odd cycle length in a graph diverges with its chromatic number, Komlos's conjecture on the number of Hamilton subsets, average degree forcing dense/sparse graphs as minors etc. I will survey some of these developments.

Combinatorics

Wed, 12.05.21

Andrea Freschi University of Birmingham

On Deficiency Problems for Graphs

Abstract.

Nenadov, Sudakov and Wagner recently introduced the notion of graph deficiency: given a global spanning property P (eg Hamiltonicity) and a graph G, the deficiency def(G) of G with respect to P is the smallest non-negative integer t such that the join G*Kt has property P, where G*Kt is the graph obtained by adding t new vertices to G and adding all edges incident to at least one of the new vertices. In particular, Nenadov, Sudakov and Wagner raised the question of determining how many edges an n-vertex graph G needs to ensure G*Kt contains a Kr-factor (for any fixed r >= 3).In this talk we present a solution to this problem. We also briefly discuss about an analogous result which forces G*Kt to contain any fixed bipartite (n+t)-vertex graph of bounded degree and small bandwidth. This is joint work with Joseph Hyde and Andrew Treglown.

Combinatorics

Wed, 05.05.21

Raphael Steiner TU Berlin

Zero sum cycles in complete digraphs

Abstract.

Given a non-trivial finite Abelian group (A,+), let n(A)≥2 be the smallest integer such that for every labelling of the arcs of the bidirected complete graph of order n(A) with elements from A there exists a directed cycle for which the sum of the arc-labels is zero. The problem of determining n(Zq) for integers q≥2 was recently considered by Alon and Krivelevich, who proved that n(Zq)=O(qlogq). Here we improve their bound and show that n(Zq) grows linearly. More generally we prove that for every finite Abelian group A we have n(A)≤8|A|, while if |A| is prime then n(A)≤32|A|. As a corollary we also obtain that every K16q-minor contains a cycle of length divisible by q for every integer q≥2, which improves a result by Alon and Krivelevich. This is joint work with Tamás Mészáros.

Combinatorics

Wed, 28.04.21

Peleg Michaeli Tel Aviv University

Discrepancies of Spanning Trees

Abstract.

Discrepancy theory is concerned with colouring elements of a ground set so that each set in a given set system is as balanced as possible. In the graph setting, the ground set is the edge set of a given graph, and the set system is a family of subgraphs. In this talk, I shall discuss the discrepancy of the set of spanning trees in general graphs, a notion that has been recently studied by Balogh, Csaba, Jing and Pluhár. More concretely, for every graph G and a number of colours r, we look for the maximum D such that in any r-colouring of the edges of G one can find a spanning tree with at least (n-1+D)/r edges of the same colour. As our main result, we show that under very mild conditions (for example, if G is 3-connected), D is equal, up to a constant factor, to the minimal integer s such that G can be separated into r equal parts by removing s vertices. This strong and perhaps surprising relation between the extremal quantity D and a geometric quantity allows us to estimate the spanning-tree discrepancy for many graphs of interest. In particular, we reprove and generalize results of Balogh et al., as well as obtain new ones. For certain graph families, we also obtain tight asymptotic results. The talk is based on joint work with Lior Gishboliner and Michael Krivelevich.

Combinatorics

Thu, 22.04.21

Shagnik Das FU Berlin

Isomorphic bisections of cubic graphs

Abstract.

Graph partitioning is the division of a graph into two or more parts based on certain combinatorial conditions, and problems of this kind of have been studied extensively. In the 1990s, Ando conjectured that the vertices of every cubic graph can be partitioned into two parts that induce isomorphic subgraphs. Using probabilistic methods together with delicate recolouring arguments, we prove Ando's conjecture for large connected graphs.This is joint work with Alexey Pokrovskiy and Benny Sudakov.

Combinatorics

Wed, 17.02.21

Dömötör Pálvögyi ELTE

At most 4.47n stable matchings

Combinatorics

Wed, 10.02.21

Tuan Tran IBS

Minimum saturated families of sets

Abstract.

A family F of subsets of [n] is called s-saturated if it contains no s pairwise disjoint sets, and moreover, no set can be added to F while preserving this property. More than 40 years ago, Erdős and Kleitman conjectured that an s-saturated family of subsets of [n] has size at least (1 – 2-(s-1))2n. It is easy to show that every s-saturated family has size at least 2n-1, but, as was mentioned by Frankl and Tokushige, even obtaining a slightly better bound of (1/2 + ε)2n, for some fixed ε > 0, seems difficult. We prove such a result, showing that every s-saturated family of subsets of [n] has size at least (1 – 1/s)2n. In this talk, I will present two short proofs. This is joint work with M. Bucic, S. Letzter and B. Sudakov.

Combinatorics

Wed, 03.02.21

Michael Anastos FU Berlin

On a k-matching algorithm and finding k-factors in cores of random graphs

Abstract.

We prove that for k+1 ≥ 3 w.h.p. the (k+1)-core of Gn,p, if non empty, spans a (near) spanning k-regular subgraph. This improves upon a result of Chan and Molloy and completely resolves a conjecture of Bollobas, Kim and Verstraëte. In addition, we show that w.h.p. such a subgraph can be found in linear time. A substantial element of the proof is the analysis of a randomized algorithm for finding k-matchings in random graphs with minimum degree k+1.

Combinatorics

Wed, 27.01.21

David Fabian FU Berlin

The running time of Q3-bootstrap percolation

Abstract.

The bootstrap process of a graph H on a graph G is the sequence (Gi)i≥0, where G0 := G and Gi is obtained from Gi-1 by adding every edge which completes a copy of H. Let MH(n) be the smallest integer such that Gi+1 = Gi for all i ≥ MH(n) and every graph G on n vertices. It was shown by Bollobás, Przykucki, Riordan and Sahasrabudhe and, independently, by Matzke that MK_4(n) = n-3. In 2019 Balogh, Kronenberg, Pokrovskiy and Szabó found a construction that gives MK_r(n) = Θ(n2) for r ≥ 6. In this talk we consider the problem of determining MH(n) when H = Q3 and show that there exist constants c,C > 0 such that cn3/2 ≤ MQ_3(n) ≤ Cn8/5 for all n ∈ N. This is joint work with Patrick Morris and Tibor Szabó.

Combinatorics

Wed, 20.01.21

Raphael Steiner TU Berlin

Complete minors via dichromatic number

Abstract.

The dichromatic number of a directed graph is the smallest integer k for which the vertex-set of the graph can be partitioned into k acyclic sets (not spanning a directed cycle). Inspired by the famous Hadwiger conjecture for undirected graphs, several groups of authors have recently studied the containment of complete digraph minors in directed graphs with given dichromatic number. We present a very short argument which improves the existing exponential upper bounds to almost linear bounds by reducing the problem to a recent result of Postle on Hadwiger's conjecture. The talk represents recent joint work with Tamás Mészáros (FU Berlin).

Combinatorics

Wed, 13.01.21

Yannick Mogge TU Hamburg

r-cross t-intersecting families via necessary intersection points

Abstract.

Given integers r ≥ 2 and n,t ≥1 we call families ℱ1,...,ℱr ⊆ ℘([n]) r-cross t-intersecting if for all Fi ∈ ℱi, i ∈ [r], we have |⋂i ∈ [r] Fi| ≥ t. We obtain a strong generalisation of the classic Hilton-Milner theorem on cross intersecting families. In particular, we determine the maximum of ∑j ∈ [r] |ℱj| for r-cross t-intersecting families in the cases when these are k-uniform families or arbitrary subfamilies of ℘([n]). Only some special cases of these results had been proved before. We obtain the aforementioned theorems as instances of a more general result that considers measures of r-cross t-intersecting families. This also provides the maximum of ∑j ∈ [r] |ℱj| for families of possibly mixed uniformities k1,...,kr. This is a joint work with Pranshu Gupta, Simón Piga and Bjarne Schülke.

Combinatorics

Thu, 07.01.21

Alp Müyesser FU Berlin

A proof of Ringel's Conjecture

Abstract.

A typical decomposition question asks whether the edges of some graph G can be partitioned into disjoint copies of another graph H. One of the oldest and best known conjectures in this area, posed by Ringel in 1963, concerns the decomposition of complete graphs into edge-disjoint copies of a tree. It says that any tree with n edges packs 2n+1 times into the complete graph K2n+1. Here we present a recent breakthrough result of Montgomery, Pokrovskiy and Sudakov that proves this conjecture for large n.

Combinatorics

Thu, 17.12.20

Patrick Morris FU Berlin

A robust Corrádi-Hajnal Theorem

Abstract.

The Corrádi-Hajnal Theorem states that any graph G with n ∈ 3ℕ vertices and minimum degree δ(G) ≥ 2n/3, contains a triangle factor, i.e. a collection of n/3 pairwise vertex-disjoint triangles. We show that any such G is `robust' with respect to this property, in that almost all (sufficiently dense) subgraphs of G contain a triangle factor. In detail, we define p*(n):=n-2/3 log1/3n and for a graph G and p=p(n), we define Gp to be random sparsification of G: the graph obtained from G keeping each edge independently with probability p. Our main result then states that there exists a C>0 such that for any G satisfying the Corrádi-Hajnal condition and any p=p(n) ≥ Cp*(n), Gp contains a triangle factor with high probability. The minimum degree condition is tight due to the existence of graphs of minimum degree 2n/3 - 1 that do not contain a triangle factor. The bound on the probability is also tight up to the value of C. Indeed, as shown in seminal work of Johansson, Kahn and Vu, p* is the threshold for containing a triangle factor in G(n,p) (that is, taking G=Kn above). Our result can thus be seen as a common strengthening of the theorems of Corrádi-Hajnal and Johansson-Kahn-Vu.This represents joint work with Peter Allen, Julia Böttcher, Jan Corsten, Ewan Davies, Matthew Jenssen, Barnaby Roberts and Jozef Skokan.

Combinatorics

Thu, 10.12.20

Simona Boyadzhiyska FU Berlin

Hyperplane coverings with multiplicities

Abstract.

It is known that the minimum number of hyperplanes needed to cover all points of F2n \ {0} while leaving the origin uncovered is n. In this talk, we will consider a variant of this problem in which the points have to be covered with certain multiplicities. More specifically, we will discuss the problem of determining the smallest number of hyperplanes required to cover all points of F2n \ {0} at least k times while covering the origin at most k-1 times and give tight bounds for certain ranges of the parameters n and k. This talk is based on joint work with Anurag Bishnoi, Shagnik Das, and Tamás M\észáros.

Combinatorics

Thu, 03.12.20

Ander Lamaison Masaryk University Brno

Quasirandom Latin squares

Abstract.

In this talk we present the notion of quasirandom Latin squares, analogous to similar definitions in other discrete structures such as graphs and permutations. Proving a conjecture of Garbe et al., we will show that a sequence of Latin squares is quasirandom if and only if every $2\times 3$ pattern has density $1/720+o(1)$, and that $2\times 2$ or $1\times k$ patterns are not enough to guarantee quasirandomness. The main tool that we will use will be Latinons, a limit structure for Latin squares introduced by Garbe et al. Joint work with Jacob Cooper, Dan Král’ and Samuel Mohr.

Combinatorics

Thu, 26.11.20

Anurag Bishnoi TU Delft

Lower bounds for diagonal Ramsey numbers

Abstract.

In a recent breakthrough Conlon and Ferber gave an exponential improvement in the lower bounds on diagonal Ramsey number R(t, t, \dots, t), when the number of colours is at least 3. We discuss their construction, along with the further improvement of Wigderson, and the finite geometry behind it.

Combinatorics

Wed, 18.11.20

Raphael Steiner TU Berlin

Disjoint cycles of distinct lengths in directed graphs of large connectivity or large minimum degree

Abstract.

A classical result by Thomassen from 1983 states that for every k ≥1 there is an integer f(k) such that every digraph with minimum out-degree f(k) contains k vertex-disjoint directed cycles. The known proof methods for Thomassen's result however do not give any information concerning the lengths of the k disjoint cycles. In undirected graphs, it is true that sufficiently large minimum degree guarantess k disjoint cycles of equal lengths, as shown by Alon (1996), and also k disjoint cycles of distinct lengths, as shown by Bensmail et al (2017). Alon also gave a construction showing that there are digraphs of unbounded minimum out- and in-degree containing no k disjoint directed cycles of the same length. In 2014 Lichiardopol made the following conjecture: For every k there exists an integer g(k) such that every digraph of minimum out-degree g(k) contains k vertex-disjoint directed cycles of pairwise distinct lengths. This conjecture seems quite challenging, as already the existence of g(3) is unknown. For general k the conjecture is only proved in some special cases such as tournaments and regular digraphs by Bensmail et al. (2017). In my talk I will present some recent ideas for finding disjoint cycles of distinct lengths in digraphs based on a new tool from structural digraph theory. I have the following partial results. For every k there exists an integer s(k) such that every strongly s(k)-connected digraph contains k vertex-disjoint directed cycles of pairwise distinct lengths. There exists an integer K such that every digraph of minimum out- and in-degree at least K contains 3 vertex-disjoint directed cycles of pairwise distinct lengths.

Combinatorics

Thu, 12.11.20

Tibor Szabó FU Berlin

Mader-perfect digraphs

Abstract.

We investigate the relationship of dichromatic number and subdivision containment in digraphs. We call a digraph Mader-perfect if for every (induced) subdigraph F, any digraph of dichromatic number at least v(F) contains an F-subdivision. We show that, among others, arbitrary orientated cycles, bioriented trees, and tournaments on four vertices are Mader-perfect. The first result settles a conjecture of Aboulker, Cohen, Havet, Lochet, Moura, and Thomassé, while the last one extends Dirac's Theorem about 4-chromatic graphs containing a K4-subdivision to directed graphs. The talk represents joint work with Lior Gishboliner and Raphael Steiner.

Combinatorics

Wed, 04.11.20

Alp Müyesser FU Berlin

A rainbow version of Hajnal-Szemerédi Theorem

Abstract.

Let G1, … , Gn/k be a collection of graphs on the same vertex set, say [n], such that each graph has minimum degree (1-1/k+o(1))n. We show that [n] can then be tiled with k-cliques, each clique coming from a distinct graph. (Here, k is a constant and n is sufficiently large.) When all the graphs are identical, this result reduces to the celebrated Hajnal-Szemerédi Theorem. This extends a result of Joos and Kim, who considered the problem when k=2, and has applications to the study of cooperative colorings, a notion of graph coloring introduced by Aharoni, Holzman, Howard, and Sprüssel. This is joint work with Yani Pehova.

Combinatorics

Thu, 16.07.20

Benjamin Aram Berendsohn FU Berlin

Geometric group testing

Abstract.

Group testing is concerned with identifying t defective items in a set of m items, where each test reports whether a specific subset of items contains at least one defective. In non-adaptive group testing, the subsets to be tested are fixed in advance. By testing multiple items at once, the required number of tests can be significantly smaller than m. In fact, if t is constant, the optimal number of (non-adaptive) tests is known to be Θ(log m). We consider the problem of non-adaptive group testing in a geometric setting, where the items are points in the plane and the tests are rectangles. We present upper and lower bounds on the required number of tests under this geometric constraint. In contrast to the general, combinatorial case, the bounds in our geometric setting are polynomial in m. Joint work with László Kozma.

Combinatorics

Thu, 09.07.20

Michael Anastos FU Berlin

Sampling Colorings of Hypergraphs

Abstract.

The talk will consist of two parts, both concerning sampling colorings of (random) hypergraphs. At the first part we will study an MCMC algorithm for sampling a (near) uniform q-coloring of a simple k-uniform hypegraph with n vertices and maximum degree D. Here q > max{ C1(k) log n, C2(k) D1/(k − 1) }. For the second part we will let Wq denote the set of proper q-colorings of the random graph G(n,m), m = dn/2 and let Hq be the graph with vertex set Wq where two vertices are connected iff the corresponding proper colorings differ in a single vertex. We will show that for sufficiently large d, if q > (1+o(1)) d/log d then Hq is connected, providing an asymptotic matching upper bound to the lower bound given by Achlioptas and Coja-Oghlan. We then extend this result to random hypergraphs. This talk is based on joint work with Alan M. Frieze.

Combinatorics

Thu, 02.07.20

David Fabian FU Berlin

The running time of graph bootstrap percolation for trees

Abstract.

Graph bootstrap percolation is a model introduced by Bollobás in 1968. Given a fixed, small graph H the H-bootstrap process on a graph G is the sequence (Gi) i ≥ 0 for which G0 := G and Gi is obtained from Gi-1 by adding every edge that completes a copy of H. We investigate the maximum number of steps this process needs to stabilise when H is a tree and G has n vertices. More precisely, we show that for any tree T there exists a constant cT such that the T-bootstrap process on any graph stabilises after at most cT steps.

Combinatorics

Thu, 25.06.20

Patrick Morris FU Berlin

Triangle factors in pseudorandom graphs

Abstract.

We discuss a conjecture of Krivelevich, Sudakov and Szabó which states that there exists a constant c such that any n vertex d-regular graph with n ∈ 3ℕ and second eigenvalue in absolute value at most cd2/n, contains a triangle factor. This bound is best possible due a dense pseudorandom triangle free construction of Alon.

Combinatorics

Thu, 18.06.20

Ander Lamaison FU Berlin

Coloring graphs by translates in the circle

Abstract.

: The fractional and circular chromatic numbers are the two most studied non-integral refinements of the chromatic number of a graph. Starting from the definition of a coloring base of a graph, which originated in work related to ergodic theory, we formalize the notion of a gyrocoloring of a graph: the vertices are colored by translates of a single Borel set in the circle group, and neighbouring vertices receive disjoint translates. The corresponding gyrochromatic number of a graph always lies between the fractional chromatic number and the circular chromatic number. We investigate basic properties of gyrocolorings. In particular, we provide an example of a graph in which no optimal gyrocoloring exists, and study the separation between fractional, circular and gyrochromatic numbers. Joint work with Pablo Candela, Carlos Catalá, Robert Hancock, Adam Kabela, Dan Kraľ and Lluís Vena.

Combinatorics

Thu, 11.06.20

Tamás Mészáros FU Berlin

Boolean dimension, components and blocks

Abstract.

We investigate the behavior of Boolean dimension with respect to components and blocks. To put our results in context, we note that for Dushnik-Miller dimension, we have that if dim(C) ≤ d for every component C of a poset P, then dim(P) ≤ max{2,d}; also if dim(B) ≤ d for every block B of a poset P, then dim(P) ≤ d + 2. By way of constrast, local dimension is well behaved with respect to components, but not for blocks: if ldim(C) ≤ d for every component C of a poset P, then ldim(P) ≤ d+2; however, for every d ≥ 4, there exists a poset P with ldim(P) = d and dim(B) ≤ 3 for every block B of P. In this paper we show that Boolean dimension behaves like Dushnik-Miller dimension with respect to both components and blocks: if bdim(C) ≤ d for every component C of P, then bdim(P) ≤ 2+d+4·2d; also if bdim(B) ≤ d for every block B of P, then bdim(P) ≤ 19 + d + 18·2d. This is joint work with Piotr Micek and William T. Trotter.

Combinatorics

Wed, 12.02.20

Patrick Morris FU Berlin

Vertex Ramsey properties of randomly perturbed graphs

Abstract.

Given graphs F,H and G, we say that G is (F,H)v -Ramsey if every red/blue vertex colouring of G contains a red copy of F or a blue copy of H. Results of Łuczak, Ruciński and Voigt and, subsequently, Kreuter determine the threshold for the property that the random graph G(n,p) is (F,H)v -Ramsey. In this talk we consider the sister problem in the setting of randomly perturbed graphs. In particular, we determine how many random edges one needs to add to a dense graph to ensure that with high probability the resulting graph is (F,H)v -Ramsey for all pairs (F,H) that involve at least one clique. This represents joint work with Shagnik Das and Andrew Treglown.

Combinatorics

Wed, 05.02.20

Pranshu Gupta TU Hamburg

Pattern gadgets and highly Ramsey-simple graphs

Abstract.

We say a graph G is q-Ramsey for another graph H if in every q-colouring of the edges of G there is a monochromatic copy of H. Additionally, if no proper subgraph of G is q-Ramsey for H, we say that G is minimal q-Ramsey for H. Let Mq(H) denote the set of all minimal q-Ramsey graphs for H. In 1976, Burr, Erdős, Lovász initiated the study of properties of this set. In particular, the parameter sq(H)= min { δ(G) : G ∈ Mq(H) } has been of considerable interest. It is not difficult to show that sq(H) ≥ qδ(H) - (q-1). We call a graph H q-Ramsey simple if this lower bound is the correct value of sq(H). In 2010, Szabó et al. showed that many classes of bipartite graphs are 2-Ramsey simple. We define a graph H to be highly q-Ramsey simple if it is q-Ramsey simple and for every positive integer k there exists a minimal Ramsey graph for H with at least k vertices of degree sq(H). We develop a new tool, called a pattern gadget, which helps us show that cycles of length at least four are highly q-Ramsey simple for all q ≥ 2. We also discuss similar results for other graphs.This is a joint work with Simona Boyadzhiyska and Dennis Clemens.

Combinatorics

Thu, 30.01.20

Michał Seweryn Jagellonian University, Krakow

Erdős-Hajnal properties for powers of sparse graphs

Abstract.

The notion of nowhere dense classes of graphs attracted much attention in recent years and found many applications in structural graph theory, algorithmics and logic. The powers of nowhere dense graphs do not need to be sparse, for instance the second power of star graphs are complete graphs. However, it is believed that powers of sparse graphs inherit somewhat simple structure. In this spirit, we show that for a fixed nowhere dense class of graphs and a positive integer d, in any n-vertex graph G in the class, there are disjoint vertex subsets A and B, each of size almost linear in n, such that in the dth power of G, either there is no edge between A and B, or there are all possible edges between A and B. This is joint work with Marcin Briański, Piotr Micek and Michał Pilipczuk.

Combinatorics

Wed, 29.01.20

Charlotte Knierim ETH Zürich

Long Cycles, Heavy Cycles and Cycle Decompositions in Directed Graphs

Abstract.

In this talk I show a connection between heavy cycles and cycle decompositions. We prove that every directed Eulerian graph can be decomposed into at most O(n log Δ) disjoint cycles, thus making progress towards the conjecture by Bollobás and Scott, and matching the best known upper bound from the undirected case. This also implies the existence of long cycles differing to the Erdős-Gallai bound for undirected graphs in only a log factor Our approach is based on finding heavy cycles in certain edge-weightings of directed graphs. As a further consequence of our techniques, we prove that for every edge-weighted digraph in which every vertex has out-weight at least 1, there exists a cycle with weight at least Ω(log log n/log n), thus resolving a question by Bollobás and Scott.This is joint work with Maxime Larcher, Anders Martinsson and Andreas Noever.

Combinatorics

Wed, 22.01.20

Frederik Garbe Czech Academy of Sciences

Limits of Sequences of Latin Squares

Abstract.

We introduce a limit theory for sequences of Latin squares paralleling the ones for dense graphs and permutations. The limit objects are certain distribution valued two variable functions, which we call Latinons, and left-convergence is defined via densities of kxl subpatterns of Latin Squares. The main result is a compactness theorem stating that every sequence of Latin squares of growing orders has a Latinon as an accumulation point. Furthermore, our space of Latinons is minimal, as we show that every Latinon can be approximated by Latin squares. This relies on a result of Keevash about combinatorial designs. We also introduce an analogue of the cut-distance and prove counterparts to the counting lemma, sampling lemma and inverse counting lemma.This is joint work with R. Hancock, J. Hladky, and M. Sharifzadeh.

Combinatorics

Wed, 15.01.20

Bhargav Narayanan Rutgers University

Disproportionate Division

Abstract.

A finite number of agents, each with their own measure of utility, would like to cut up a piece of cake amongst themselves. How efficiently can they do this? Almost everything one would like to know about this problem is known in the case where the agents all want a fair share of the cake. The more general problem where the agents have different claims to the cake is less well understood; in this talk, I shall present a new, efficient division procedure for the general problem that yields nearly optimal bounds. We’ll take the scenic route to the problem, first through some algebraic topology, and then end up at some combinatorics.

Combinatorics

Thu, 09.01.20

Giulia Codenotti FU Berlin

Unimodular covers of 3-dimensional parallelepipeds and Cayley sums

Combinatorics

Wed, 18.12.19

Olaf Parczyk LSE

The size-Ramsey number of tight 3-uniform paths

Abstract.

Given a hypergraph H, the size-Ramsey number is the smallest integer m such that there exists a graph G with m edges with the property that in any colouring of the edges of G with two colours there is a monochromatic copy of H. Extending on results for graphs we prove that the size Ramsey number of the 3-uniform tight path on n vertices is linear in n. This is joint work with Jie Han, Yoshiharu Kohayakawa, and Guilherme Mota.

Combinatorics

Thu, 12.12.19

Simona Boyadzhiyska FU Berlin

On Ramsey minimal graphs for cliques

Abstract.

A graph G is Ramsey for another graph H if any two-coloring of the edges of G contains a monochromatic copy of H. We call G Ramsey minimal for H if G is Ramsey for H but no proper subgraph of G is. In this talk, we will present a result of Rödl and Siggers, showing that, for any k≥3 and n sufficiently large, there exist many graphs on at most n vertices that are Ramsey minimal for the k-clique. More precisely, we will show that, for any k≥3, there exist constants c(k)>1 and n0(k) such that, for all n≥n0(k), there are at least cn^2 Ramsey minimal graphs for Kk on at most n vertices.This talk is based on the paper "On Ramsey minimal graphs" by V. Rödl and M. Siggers.

Combinatorics

Wed, 04.12.19

David Fabian FU Berlin

On infinite α-strong Sidon sets

Abstract.

Given a real parameter 0≤α<1, an α-strong Sidon set is a subset S⊂N of the positive integers such that for any w,x,y,z∊S with {w,x}≠{y,z} one has |(w+x)-(y+z)|≥ max{wα,xα,yα,zα}. In this talk we focus on the setting when S is infinite and study the asymptotics of the counting function S(n):=|S∩[n]|. By generalizing a construction of Cilleruelo we show that there exists an α-strong Sidon set S with counting function S(n) = n\sqrt{(1+α)^2+1}-(1+α)+o(1). Finally, we take a look at how α-strong Sidon sets can be used to bound the density of the largest Sidon set contained in a random infinite subset of the positive integers. We also describe how these results can be extended to Bh-sets. This is joint work with Juanjo Rué and Christoph Spiegel.

Combinatorics

Wed, 27.11.19

Shagnik Das FU Berlin

Ramsey games near the critical threshold

Abstract.

A well-known result of Rödl and Ruciński states that for any graph H there exists a constant C such that if p ≥ C n- 1/m_2(H), then the random graph Gn,p is a.a.s. H-Ramsey, that is, any 2-colouring of its edges contains a monochromatic copy of H. Aside from a few simple exceptions, the corresponding 0-statement also holds; that is, there exists c>0 such that if p≤ cn-1/m_2(H) the random graph Gn,p is a.a.s. not H-Ramsey. We show that near this threshold, even when Gn,p is not H-Ramsey, it is often extremely close to being H-Ramsey. More precisely, we prove that for any constant c > 0 and any strictly 2-balanced graph H, if p ≥ c n-1/m_2(H), then the random graph Gn,p a.a.s. has the property that every 2-edge-colouring without monochromatic copies of H cannot be extended to an H-free colouring after Ω(1) extra random edges are added. This generalises a result by Friedgut, Kohayakawa, Rödl, Ruciński and Tetali, who in 2002 proved the same statement for triangles, and addresses a question raised by those authors. We also provide a wide variety of examples to show that these theorems need not hold when H is not strictly 2-balanced, and extend a result of theirs in the 3-coloured setting. This is joint work with David Conlon, Joonkyung Lee and our very own Tamás Mészáros.

Combinatorics

Wed, 20.11.19

Tamás Mészáros FU Berlin

Greedy maximal independent sets via local limits

Abstract.

The greedy algorithm for finding a maximal independent set in a graph G on vertices V = {v1, ..., vn} can be described as follows. Let σ be a permutation of [n] chosen uniformly at random. Starting from an empty set R, at step i add vσ(i) to the set R if and only if R∪{vσ(i)} is an independent set in G. This very natural algorithm has been studied extensively in various settings in combinatorics, probability, computer science - and even in chemistry. In this talk we present a natural and general framework for calculating the asymptotics of the proportion of the yielded independent set for sequences of (possibly random) graphs, involving a useful notion of local convergence. We use this framework both to give short and simple proofs for results on previously studied families of graphs, such as paths and binomial random graphs, and to study new ones, such as random trees. This is joint work with Michael Krivelevich, Peleg Michaeli and Clara Shikhelman.

Combinatorics

Wed, 13.11.19

Christoph Spiegel UPC Barcelona

A step beyond Freiman's theorem for set addition modulo a prime

Abstract.

Freiman's 2.4-Theorem states that any subset A of Zp satisfying |2A| ≤ 2.4 |A| - 3 and |A| < p/35 can be covered by an arithmetic progression of length at most |2A| - |A| + 1. A more general result of Green and Ruzsa implies that this covering property holds for any set satisfying |2A| ≤ 3|A| - 4 as long as the rather strong density requirement |A| < p/10215 is satisfied. In this talk I will present a version of this statement that allows for sets satisfying |2A| ≤ 2.48|A| - 7 with the more modest density requirement of |A| < p/1010. In doing so, I hope to shed some light on how the methods of rectification and modular reduction go hand-in-hand when proving these types of small doubling covering property both in the cyclic setting and in the integers. This is joint work with Pablo Candela and Oriol Serra.

Combinatorics

Thu, 07.11.19

Karola Mészáros Cornell University

Encoding polytopal properties with (reductions on) graphs

Abstract.

The flow polytope FG associated to an acyclic graph G is the set of all nonnegative flows of size 1 on the graph G. Fundamental questions about this and other flow polytopes include: (1) what is the polytope’s volume? (2) how many integer points are in it? I will explain how to use a reduction procedure on graphs to answer these question.

Combinatorics

Wed, 30.10.19

Alp Müyesser FU Berlin

Turán-type results for unavoidable subgraphs

Abstract.

We say that a two-coloring of a K2k is k-unavoidable if one color forms either a clique of order k or two disjoint cliques of order k. Bollob\'as conjectured that for any ε and k, there exists an integer R(ε,k) such that any n≥R(ε,k) vertex graph with at least ε{n choose 2} edges in each color contains a k-unavoidable graph. This was proven by Cutler and Montágh, and Fox and Sudakov showed R(ε, k)=(1/ε)θ(k). Here, we obtain several Turán-type variants of this result, such as showing that in any two-colored graph with density 1-(1/ε)O(k) and at least ε fraction of the edge set in each color, there exists a k-unavoidable subgraph. A result with a similar flavour was recently obtained by DeVos et al. who showed that any graph with density above 2/3 whose edges are colored half red and half blue must contain a non-monochromatic triangle. We solve this same problem entirely for all cycles, and up to an additive constant, for all cliques. This is joint work with Boris Bukh and Michael Tait.

Combinatorics

Thu, 24.10.19

Michael Anastos FU Berlin

The longest path in a random graph has a scaling limit

Abstract.

Let G(n,p) denote the random graph on n vertices where each edge appears independently with probability p=c/n. It is well known that p=1/n is the threshold for the existence of a giant component. Erdős conjectured that if c > 1 then w.h.p. the length of the longest path of G(n,c/n), denoted by L(c,n), satisfies L(c,n) ≥ l(c)n where l(c) > 0 is independent of n. This was proved by Ajtai, Komlós and Szemerédi and in a slightly weaker form by de la Vega. The lower bound was then improved in a series of papers. In this talk we go a step further and we show that for sufficiently large c, w.h.p. L (c,n)/n tends to some function f(c) as n tends to infinity. In addition we give a method of computing f(c) to arbitrary accuracy. This talk is based on joint work with Alan M. Frieze.

Combinatorics

Wed, 28.08.19

Alexandra Wesolek Simon Fraser University

Weak rainbow saturation

Abstract.

Rainbow saturation asks for the minimum number of edges in a t-edge-coloured graph G such that it does not contain a rainbow copy of some fixed graph H but adding any missing edge in any colour from [t] completes a rainbow copy of H. It is an extension of the uncoloured saturation problem which was first studied by Erdős, Hajnal and Moon in 1964. Surprisingly, if H=Ks, the complete graph on s vertices, and G is a graph on n vertices, the minimum number of edges that we need is Θ(n log n) while in the uncoloured saturation problem we only need a linear number of edges. In this work we investigate weak versions of rainbow saturation. In the usual rainbow saturation problem we can choose an arbitrary ordering of the missing edges and add all the missing edges back to the graph in that order and in arbitrary colours completing a rainbow copy each time we add an edge. Instead of being able to add the edges in any ordering to the graph, in a weaker setting we ask for only one specific ordering in which we need to be able to add them back. Is the behaviour for the minimum sets in this case still Θ(n log n)? In the uncoloured setting the bound for this weakened version is linear, so the answer needs to be between these bounds. Moreover, we investigate how the problem changes if we are allowed to choose a colour for every edge that we add. What if we can choose the colours and an ordering? We give answers to those questions. This represents joint work with Shagnik Das.

Combinatorics

Wed, 14.08.19

Hiệp Hàn University of Santiago de Chile

Quasi-random words and limits of word sequences

Abstract.

Words are finite sequences of letters over a finite alphabet and in this talk we address two intimately related topics for this object: quasi-randomness and limit theory.With respect to the first topic we study the notion of uniform distribution of letters over intervals, and in the spirit of the famous Chung-Graham-Wilson theorem we provide a list of word properties which are equivalent to this property. This investigation naturally gives rise to a notion of convergent word sequences, and in the second part of our work we develop a limit theory for such sequences. Via this theory we address several problems such as property testing and finite forcibility and obtain as a byproduct a new model of random word sequences.Joint work with Matias Pavez-Signe and Marcos Kiwi.

Combinatorics

Wed, 03.07.19

Nina Kamcev Monash University

Asymptotic enumeration of regular hypergraphs

Abstract.

We prove an asymptotic formula for the number of k-uniform hypergraphs with a given degree sequence, for a wide range of parameters. In particular, we can asymptotically enumerate d-regular k-graphs of density O(1/k) for 3 ≤ k< n1/10. This extends the recent results for graphs of Liebenau and Wormald.It follows that within our scope, the distribution of the degree sequence of a random k-uniform hypergraph can be approximated by a sequence of independent random variables with the appropriate binomial distribution. This is joint work with Anita Liebenau and Nick Wormald.

Combinatorics

Wed, 26.06.19

Mara Nehring FU Berlin

Online Ramsey Numbers

Abstract.

The Online Ramsey Game is a game on an unbounded number of vertices played by two players, Builder and Painter. Builder builds an edge between two vertices and Painter paints it immediately red or blue. Builder's goal is to build a monochromatic red copy of Km or a monochromatic blue copy of Kn while Painter tries to delay this for as long as possible. The online Ramsey number is the minimum number of edges Builder needs to guarantee a win regardless of Painter's strategy. We will show new lower and upper bounds for the online Ramsey number. Work by David Conlon, Jacob Fox, Andrey Ginshpun and Xiaoyu He.

Combinatorics

Wed, 19.06.19

Tamás Mészáros FU Berlin

Unlabeled compression schemes and corner peelings for ample and maximum classes

Abstract.

I will be presenting recent work by Chalopin, Chepoi, Moran and Warmuth. "We examine connections between combinatorial notions that arise in machine learning and topological notions in cubical/simplicial geometry. These connections enable to export results from geometry to machine learning. Our first main result is based on a geometric construction by Tracy Hall (2004) of a partial shelling of the cross polytope which can not be extended. We use it to derive a maximum class of VC dimension 3 that has no corners. This refutes several previous works in machine learning from the past 11 years. In particular, it implies that all previous constructions of optimal unlabeled sample compression schemes for maximum classes are erroneous.On the positive side we present a new construction of an unlabeled sample compression scheme for maximum classes. We leave as open whether our unlabaled sample compression scheme extends to ample (a.k.a. lopsided or extremal) classes, which represent a natural and far-reaching generalization of maximum classes. Towards resolving this question, we provide a geometric characterization in terms of unique sink orientations of the 1-skeletons of associated cubical complexes."

Combinatorics

Thu, 13.06.19

Tibor Szabó FU Berlin

Slow bootstrap percolation

Abstract.

Graph-bootstrap percolation, also known as weak saturation, was introduced by Bollobás in 1968. In this process, we start with initial "infected" set of edges E0, and infect new edges according to a predetermined rule. Given a graph H and a set of previously infected edges Et ⊆ E(Kn), we infect a non-infected edge e if it completes a new copy of H in G=([n], Et ∪ e). A question raised by Bollobás asks for the maximum time the process can run before it stabilizes. Bollobás, Przykucki, Riordan, and Sahasrabudhe considered this problem for the most natural case where H=Kr. They answered the question for r ≤ 4 and gave a non-trivial lower bound for every r ≤ 5. They also conjectured that the maximal running time is o(n2) for every integer r. In a joint work with József Balogh, Gal Kronenberg, and Alexey Pokrovskiy we disprove their conjecture for every r ≥ 6 and we give a better lower bound for the case that r=5 using Behrend's construction of large 3-term arithmetic progression-free sets of integers.

Combinatorics

Mon, 10.06.19

Hao Huang Emory University

A spectral proof of Kleitman's diametric theorem

Combinatorics

Wed, 05.06.19

Anurag Bishnoi FU Berlin

A construction for clique-free pseudorandom graphs

Abstract.

A construction of Alon and Krivelevich gives highly pseudorandom Kk-free graphs on n vertices with edge density equal to Θ(n-1/(k-2)). In this talk I will give a construction of an infinite family of highly pseudorandom Kk-free graphs with a higher edge density of Θ(n-1/(k-1)), for all k≥3, using the geometry of quadratic forms over finite fields. (Joint work with Ferdinand Ihringer and Valentina Pepe.)

Combinatorics

Wed, 22.05.19

William T. Trotter Georgia Institute of Technology

Dimension and Maximum Degree

Abstract.

The maximum degree of a poset is the maximum degree in the associated comparability graph. For an integer k, let f(k) denote the maximum dimension of a poset P with maximum degree k. It was shown in 1991 by Erdős, Kierstead and Trotter that f(k) = Ω(k logk). In 1986, Füredi and Kahn showed that f(k) = O(k log2k). Just in 2018, Scott and Wood made the following subtle but dramatic improvement: f(k) = O(log1+o(1)k). We outline the proof which uses an iterated application of the Lovász Local Lemma.

Combinatorics

Wed, 15.05.19

Piotr Micek Jagellonian University Krakow and TU Berlin

p-centered colorings of planar graphs

Abstract.

A p-centered coloring of a graph G is a coloring of its vertices such that for every connected subgraph H of G either H receives more than p colors or there is a color that appears exactly once in H. Very recently, we have shown that every planar graph admits a p-centered coloring with O(p3 log(p)) colors. This improves an O(p19) bound by Pilipczuk&Siebertz. We also know that some planar graphs require Omega(p2 log(p)) colors. We have tight bounds for outerplanar graphs, stacked triangulations, and graphs of bounded treewidth.Ongoing work with Stefan Felsner and Felix Schröder.

Combinatorics

Wed, 08.05.19

Tuan Tran ETH Zürich

Dense induced bipartite subgraphs in triangle-free graphs

Abstract.

The problem of finding dense induced bipartite subgraphs in H-free graphs has a long history, and was posed 30 years ago by Erdős, Faudree, Pach and Spencer. We obtain several results in this direction. First we prove that any H-free graph with minimum degree at least d contains an induced bipartite subgraph of minimum degree at least c_H log d/log log d, confirming (asymptotically) several conjectures by Esperet, Kang and Thomassé. Complementing this result, we further obtain optimal bounds for this problem in the case of dense triangle-free graphs, and we also answer a question of Erdős, Janson, Luczak and Spencer. Joint work with Kwan, Letzter and Sudakov.

Combinatorics

Thu, 02.05.19

Joonkyung Lee Universität Hamburg

On the extremal number of subdivisions

Abstract.

The extremal number ex(n, H) is the maximum number of edges in an H-free graph with n vertices. When H has chromatic number at least three, the asymptotic behaviour of the extremal number is well understood, but when H is bipartite, the function remains mysterious. We give new estimates for the extremal numbers of various bipartite graphs H, especially if H can be obtained by subdividing edges of another graph H' in certain ways. Joint work with David Conlon and Oliver Janzer.

Combinatorics

Wed, 24.04.19

Ander Lamaison FU Berlin

Ramsey upper density of infinite graphs

Abstract.

Let H be an infinite graph. In a two-coloring of the edges of the complete graph on the natural numbers, what is the densest monochromatic subgraph isomorphic to H that we are guaranteed to find? We measure the density of a subgraph by the upper density of its vertex set. This question, in the particular case of the infinite path, was introduced by Erdős and Galvin. Following a recent result for the infinite path, we present bounds on the maximum density for other choices of H, including exact values for a wide class of bipartite graphs.

Combinatorics

Wed, 17.04.19

Simona Boyadzhiyska FU Berlin

On counting problems related to (mutually) orthogonal Latin squares

Abstract.

After the question of existence of a combinatorial structure satisfying given properties, a natural and important problem is to determine how many such objects there are. In this talk, we will consider some counting questions related to (mutually) orthogonal Latin squares. We will prove an upper bound on the number of ways to extend a set of k mutually orthogonal Latin squares to a set of k+1 mutually orthogonal Latin squares and discuss some applications, comparing the resulting bounds to previously known lower and upper bounds.This talk is based on joint work with Shagnik Das and Tibor Szabó.

Combinatorics

Wed, 10.04.19

Andrew Treglown University of Birmingham

A degree sequence Komlós theorem

Abstract.

A classical topic is graph theory concerns finding minimum degree conditions that force a given spanning subgraph in a graph. There has also been interest in generalising such results via degree sequence conditions. Komlós' theorem determines the minimum degree that forces an H-tiling in a graph G covering a given proportion of the vertices in G. (An H-tiling is simply a collection of vertex-disjoint copies of H in G.) In this talk we will discuss a degree sequence generalisation of this result. This is joint work with Hong Liu and Joseph Hyde.

Combinatorics

Wed, 06.03.19

Tibor Szabó FU Berlin

List Ramsey numbers

Abstract.

We introduce the list colouring extension of classical Ramsey numbers, investigate when the two Ramsey numbers are equal, and in general, how far apart they can be from each other. We find graph sequences where the two are equal and where they are far apart. For l-uniform cliques we prove that the list Ramsey number is bounded by an exponential function, while it is well-known that the Ramsey number is super-exponential for uniformity at least 3. This is in great contrast to the graph case where we cannot even decide the question of equality for cliques. Joint work with Noga Alon, Matija Bucic, Tom Kalvari, and Eden Kuperwasser.

Combinatorics

Thu, 21.02.19

Jan van den Heuvel LSE

Partial solutions to Hadwiger's Conjecture

Abstract.

Hadwiger's Conjecture (1943) asserts that every graph without the complete graph Kt+1 as a minor has a proper vertex-colouring using at most t colours. Since the conjecture is stubbornly refusing to be proved, we might look at relaxed versions of it. In the talk we discuss some results around the following question: If we are given t colours to colour a graph without Kt+1-minor, what kind of vertex-colourings can we guarantee with those t colours?

Combinatorics

Wed, 13.02.19

Ferdinand Ihringer Ghent University

Rank Bounds on the Independence Number

Abstract.

Recently, the breakthrough results by Croot, Lev, and Pach on progression-free sets in ℤ4n and by Ellenberg and Gijswijt on cap sets brought new attention to rank arguments for bounding sets in combinatorial problems. We discuss several traditional applications of rank arguments to bound the independence number of a graph. The examples include the orthogonality graph on {-1,1}n, generalized quadrangles, Hermitian dual polar graphs, and quasisymmetric designs.

Combinatorics

Wed, 06.02.19

David Fabian FU Berlin

Rainbow arithmetic progressions and anti-van der Waerden numbers

Abstract.

Given a colouring of a set in an ambient abelian group, a rainbow arithmetic progression is an arithmetic progression whose elements receive pairwise distinct colours. We are going to consider two related problems that have been studied over the last years: First we ask whether any k-colouring of [n] with equally sized colour classes admits a rainbow arithmetic progression of length k. The second problem is to find the smallest positive integer r, for which every r-colouring of [n] contains a rainbow k-AP. We shall also have a look at the analogous problems when [n] is replaced by a finite abelian group.

Combinatorics

Wed, 30.01.19

László Kozma FU Berlin

Hamiltonicity below Dirac's condition

Abstract.

Dirac's theorem (1952) is a classical result of graph theory, stating that an n-vertex graph (n≥3) is Hamiltonian if every vertex has degree at least n/2. Both the value n/2 and the requirement for every vertex to have high degree are necessary for the theorem to hold. In this work we give efficient algorithms to determine whether a graph is Hamiltonian when either of the two conditions are relaxed. Joint work with Bart Jansen and Jesper Nederlof.

Combinatorics

Wed, 23.01.19

Anurag Bishnoi FU Berlin

Non-intersecting Ryser hypergraphs

Abstract.

A famous conjecture of Ryser states that every r-partite hypergraph has vertex cover number at most r − 1 times the matching number. In recent years, hypergraphs meeting this conjectured bound, known as r-Ryser hypergraphs, have been studied extensively. It was proved by Haxell, Narins and Szabó that all 3-Ryser hypergraphs with matching number ν > 1 are essentially obtained by taking ν disjoint copies of intersecting 3-Ryser hypergraphs. In this talk we will see new infinite families of r-Ryser hypergraphs, for any given matching number ν > 1, that do not contain two vertex disjoint intersecting r-Ryser subhypergraphs.

Combinatorics

Wed, 16.01.19

Jan Corsten LSE

Erdős-Rothschild problem for five and six colours

Abstract.

Given positive integers n,r,k, the Erdős-Rothschild problem asks to determine the largest number of r-edge-colourings without monochromatic k-cliques a graph on n vertices can have. In the case of triangles, i.e. when k=3, the solution is known for r = 2,3,4. We investigate the problem for five and six colours.

Combinatorics

Wed, 09.01.19

Péter Pál Pach BME

Polynomial Schur's theorem

Abstract.

We consider the Ramsey problem for the equation x+y=p(z), where p is a polynomial with integer coefficients. Under the assumption that p(1)p(2) is even we show that for any 2-colouring of ℕ the equation x+y=p(z) has infinitely many monochromatic solutions. Indeed, we show that the number of monochromatic solutions with x,y,z∈ {1,2,\dots,n} is at least n2/d^3-o(1), where d=deg p.On the other hand, when p(1)p(2) is odd, that is, when p attains only odd values, then there might not be any monochromatic solution, e.g., this is the case when we colour the integers according to their parity. We give a characterization of all 2-colourings avoiding monochromatic solutions to x+y=p(z).This is a joint work with Hong Liu and Csaba Sándor.

Combinatorics

Wed, 19.12.18

Christoph Spiegel UPC

Intervals in the Hales-Jewett Theorem

Abstract.

The Hales–Jewett Theorem states that any r–colouring of [m]n contains a monochromatic combinatorial line if n is large enough. Shelah’s proof of the theorem implies that for m = 3 there always exists a monochromatic combinatorial lines whose set of active coordinates is the union of at most r intervals. I will present some recent findings relating to this observation. This is joint work with Nina Kamcev.

Combinatorics

Wed, 12.12.18

Jozef Skokan LSE

The k-colour Ramsey number of odd cycles via non-linear optimisation

Abstract.

For a graph G, the k-colour Ramsey number Rk(G) is the least integer N such that every k-colouring of the edges of the complete graph KN contains a monochromatic copy of G. Let Cn denote the cycle on n vertices. We show that for fixed k > 2 and n odd and sufficiently large, Rk(Cn) = 2k-1(n-1) + 1. This generalises a result of Kohayakawa, Simonovits and Skokan and resolves a conjecture of Bondy and Erdős for large n. We also establish a surprising correspondence between extremal k-colourings for this problem and perfect matchings in the hypercube Qk. This allows us to in fact prove a stability-type generalisation of the above. The proof is analytic in nature, the first step of which is to use the Regularity Lemma to relate this problem in Ramsey theory to one in convex optimisation. This is joint work with Matthew Jenssen.

Combinatorics

Wed, 05.12.18

Alexandra Wesolek FU Berlin

Bootstrap percolation in Ore-type graphs

Abstract.

In the r-neighbour bootstrap process on a graph G we start with an initial set of infected vertices A0 ⊆ V(G) and a new vertex gets infected as soon as it has r infected neighbours. We call A0 percolating if an infection of A0 infects all of our graph. Under which conditions on G can we find a small percolating set A0? In general, the denser our graph is the easier it is to infect new vertices as the initially infected vertices share potentially more neighbours. If v(G) ≤ r then we need to infect at least r vertices initially to infect all of our graph otherwise we will not be able to infect any new vertices during the bootstrap process. Gunderson showed that if a graph G on n vertices has minimum degree δ(G) ≤ ⌊ n/2 ⌋ + r - 3 then we can always find a percolating set of size r (if r ≤ 4 and n is big enough). How much can we decrease the minimum degree conditions if we are initially allowed to infect r+k vertices for k ∈ ℕ? What if we consider more general graphs where the sum of the degrees of any two non-adjacent vertices x and y is deg(x) + deg(y) ≤ D? This is more general because if a graph G has δ(G) = D/2 then for any two vertices in G it holds that deg(x) + deg(y) ≤ D. In this talk we give conditions on D=D(r,k) that guarantee a percolating set of size r + k, answering both open questions at once for small enough k=k(r).

Combinatorics

Thu, 29.11.18

Hong Liu Warwick

Enumeration in arithmetic setting

Combinatorics

Wed, 28.11.18

Andrew Newman TU Berlin

Small simplicial complexes with large torsion in homology

Abstract.

From the work of Kalai on ℚ-acyclic complexes it is known that for d ≥ 2 a d-dimensional simplicial complex on n vertices can have enormous torsion, on the order of exp(Θd(nd)), in its (d-1)st homology group. However, explicit constructions of complexes which realize this enormous-torsion phenomenon have been somewhat rare. Therefore, in this talk we consider and affirmatively answer the following inverse question: Given a finite abelian group of order m, can one always construct a d-dimensional simplicial complex on Θd((log m)1/d) vertices which realizes the given group in its (d - 1)st homology group?

Combinatorics

Wed, 21.11.18

Sophia Elia FU Berlin

A comparison of Quotient Posets

Abstract.

Given an equivalence relation on the elements of a poset, place a new relation on the equivalence classes of elements. If this new relation is reflexive, antisymmetric, and transitive, then a quotient poset is created. We survey different types of quotient posets and see how they compare. In particular, we look at quotient posets that arise from lattice congruences, order-preserving group actions, and as images of surjective maps. We characterize quotient posets that correspond to a certain relation on equivalence classes by defining a sequence related to transitivity. Then we look at an application of quotient posets arising from order-preserving group actions. Let Hom(P,n) be the set of order-preserving maps from a poset P to a chain with elements. Stanley showed that |Hom(P,n)| is given by a polynomial in . Given an order-preserving group action on P, there is an induced group action on Hom(P,n). Katharina Jochemko showed that the number of maps in Hom(P,n)up to equivalence under the induced group action is also polynomial in using quotient posets. We touch on an alternative approach to the proof through the Ehrhart theory of order polytopes.

Combinatorics

Wed, 07.11.18

Patrick Morris FU Berlin

On the discrepancy of permutation families

Combinatorics

Wed, 31.10.18

Tamás Mészáros FU Berlin

Sample compression schemes

Abstract.

In this talk we concentrate on two fundamental concepts of classical machine learning theory: learning and compression. Motivated by the fact that if a concept class admits a small sample compression scheme then it is efficiently learnable (Littlestone and Warmuth), we propose to study the relationship between the size of sample compression schemes and the combinatorial notion of VC dimension. In particular, we propose several directions to tackle the compression scheme conjecture which states that the smallest possible size of a sample compression scheme is linear in the VC dimension of the underlying concept class.

Combinatorics

Wed, 24.10.18

Roman Glebov Ben Gurion University

Perfect Matchings in Random Subgraphs of Regular Bipartite Graphs

Abstract.

Consider the random process in which the edges of a graph G are added one by one in a random order. A classical result states that if G is the complete graph K2n or the complete bipartite graph Kn,n, then typically a perfect matching appears at the moment at which the last isolated vertex disappears. We extend this result to arbitrary k-regular bipartite graphs G on 2n vertices for all k=Ω(n). Surprisingly, this is not the case for smaller values of k. We construct sparse bipartite k-regular graphs in which the last isolated vertex disappears long before a perfect matching appears. Joint work with Zur Luria and Michael Simkin.

Combinatorics

Thu, 19.07.18

Daniele Bartoli University of Perugia

Permutation polynomials over finite fields

Abstract.

Let q = p^h be a prime power. A polynomial f(x) in Fq[x] is a permutation polynomial (PP) if it is a bijection of the finite field Fq into itself. On the one hand, each permutation of Fq can be expressed as a polynomial over Fq. On the other hand, particular, simple structures or additional extraordinary properties are usually required by applications of PPs in other areas of mathematics and engineering, such as cryptography, coding theory, or combinatorial designs. Permutation polynomials meeting these criteria are usually difficult to find. A standard approach to the problem of deciding whether a polynomial f(x) is a PP is the investigation of the plane algebraic curve Cf : (f(x) − f(y))/(x − y) = 0; in fact, f is a PP over Fq if and only if Cf has no Fq-rational point (a, b) with a != b. In this talk, we will see applications of the above criterion to classes of permutation polynomials, complete permutation polynomials, exceptional polynomials, Carlitz rank problems, the Carlitz conjecture.

Combinatorics

Thu, 12.07.18

Jeroen Schillewaert University of Auckland, NZ

Combinatorial methods in finite geometry

Abstract.

I will discuss a few different combinatorial techniques to study and characterise special classes of incidence structures (ovoids, spreads, maximal arcs,...) in finite geometry

Combinatorics

Thu, 05.07.18

Necati Alp Muyesser CMU

Ramsey-type results for balanced graphs

Abstract.

Consider G, a 2-coloring of a complete graph on n vertices, where both color classes have at least \ep fraction of all the edges. Fix some graph H, together with a 2-coloring of its edges. By H^c, we denote the same graph with the colors switched. How large does n have to be so that G necessarily contains one of H or H^c as a subgraph? Call the smallest such integer, if it exists, R_\ep(H). We completely characterize the H for which R_\ep(H) is finite, discuss some quantitative bounds, and consider some related problems. Based on joint works with Matthew Bowen and Ander Lamaison.

Combinatorics

Thu, 28.06.18

Alexey Pokrovskiy ETH Zürich

Ryser's Conjecture & diameter

Abstract.

Ryser conjectured that the vertices of every r-edge-coloured graph with independence number i can be covered be (r - 1)i monochromatic trees. Recently Milicevic conjectured that moreover one can ensure that these trees have bounded diameter. We'll show that the two conjectures are equivalent. As a corollary one obtains new results about Milicevic's Conjecture.

Combinatorics

Thu, 21.06.18

Benny Sudakov ETH Zürich

Rainbow structures, Latin squares & graph decompositions

Abstract.

A subgraph of an edge-coloured graph is called rainbow if all its edges have distinct colours. The study of rainbow subgraphs goes back to the work of Euler on Latin squares. Since then rainbow structures were the focus of extensive research and found applications in design theory and graph decompositions. In this talk we discuss how probabilistic reasoning can be used to attack several old problems in this area. In particular we show that well known conjectures of Ryser, Hahn, Ringel, Graham-Sloane and Brualdi-Hollingsworth hold asymptotically. Based on joint works with Alon, Montgomery, and Pokrovskiy.

Combinatorics

Wed, 13.06.18

John Bamberg UWA Perth

Hemisystem-like objects in finite geometry

Abstract.

Beniamino Segre showed in his 1965 manuscript 'Forme e geometrie hermitiane, con particolare riguardo al caso finito' that there is no way to partition the points of the Hermitian surface H(3,q^2) into lines, when q is odd. Moreover, Segre showed that if there is an m-cover of H(3,q^2), a set of lines covering each point m times, then m=(q+1)/2; half the number of lines on a point. Such a configuration of lines is known as a hemisystem and they give rise to interesting combinatorial objects such as partial quadrangles, strongly regular graphs, and imprimitive cometric Q-antipodal association schemes. This talk will be on developments in the field of hemisystems of polar spaces and regular near polygons and their connections to other interesting combinatorial objects. No background in finite geometry will be assumed.

Combinatorics

Wed, 30.05.18

Malte Renken FU Berlin

Finding Disjoint Connecting Subgraphs in Surface-embedded Graph

Abstract.

Given a graph $G$, a set $T \subseteq V(G)$ of terminal vertices and a partition of $T$ into blocks, the problem "Disjoint Connecting Subgraphs" is to find a set of vertex-disjoint subgraphs of G, each covering exactly one block. While NP-hard in general, Robertson and Seymour showed that the problem is solvable in polynomial time for any fixed size of $T$. Generalizing a result of Reed, we give an $O(n \log(n))$ algorithm for when $G$ is embedded into an arbitrary but fixed surface.

Combinatorics

Thu, 24.05.18

Anurag Bishnoi FU Berlin

A generalization of Chevalley-Warning and Ax-Katz via polynomial substitutions

Combinatorics

Wed, 09.05.18

Milos Stojakovic University of Novi Sad

Semi-random graph process

Abstract.

We introduce and study a novel semi-random multigraph process, described as follows. The process starts with an empty graph on n vertices. In every round of the process, one vertex v of the graph is picked uniformly at random and independently of all previous rounds. We then choose an additional vertex (according to a strategy of our choice) and connect it by an edge to v. For various natural monotone increasing graph properties P, we give tight upper and lower bounds on the minimum (extended over the set of all possible strategies) number of rounds required by the process to obtain, with high probability, a graph that satisfies P. Along the way, we show that the process is general enough to approximate (using suitable strategies) several well-studied random graph models. Joint work with: Omri Ben-Eliezer, Dan Hefetz, Gal Kronenberg, Olaf Parczyk and Clara Shikhelman.

Combinatorics

Thu, 26.04.18

Patrick Morris FU Berlin

Tilings in randomly perturbed hypergraphs

Abstract.

In 2003, Bohman, Frieze and Martin introduced a random graph model called the perturbed model. Here we start with some $\alpha>0$ and an arbitrary graph $G$ of minimum degree $\alpha n$. We are then interested in the threshold probability $p=p(n)$ for which $G \cup G(n,p)$ satisfies certain properties. That is, for a certain property, for example Hamiltonicity, we can ask what is the minimum probability $p(n)$, such that for \emph{any} $n$-vertex graph $G$ of minimum degree $\alpha n$, $G \cup G(n,p)$ has this property with high probability. This model has been well studied and the threshold probability has been established for various properties. One key property is the notion of having a $H$-tiling for some fixed graph $H$. By this, we mean a union of disjoint copies of $H$ in $G\cup G(n,p)$ that covers every vertex exactly once. This generalisation of a perfect matching is fundamental and was studied in the setting of perturbed dense graphs by Balogh, Treglown and Wagner in 2017. In this talk, we look to extend this problem to the setting of hypergraphs. This is work in progress and joint with Wiebke Bendenknecht, Jie Han, Yoshiharu Kohayakawa and Guilherme Mota.

Combinatorics

Wed, 25.04.18

Shagnik Das FU Berlin

Colourings without monochromatic chains

Abstract.

In 1974, Erdős and Rothschild introduced a new kind of extremal problem, asking which n-vertex graph has the maximum number of monochromatic-triangle-free red/blue edge-colourings. While this original problem strengthens Mantel’s theorem, recent years have witnessed the study of the Erdős-Rothschild extension of several classic combinatorial theorems. In this talk, we seek the Erdős-Rothschild extension of Sperner’s Theorem. More precisely, we search for the set families in 2^{[n]} with the most monochromatic-k-chain-free r-colourings. Time and interest permitting, we shall present some results, sketch some proofs, and offer many open problems. This is joint work with Roman Glebov, Benny Sudakov and Tuan Tran.

Combinatorics

Thu, 19.04.18

Ander Lamaison FU Berlin

Ramsey density of infinite paths

Combinatorics

Wed, 28.02.18

Penny Haxell University of Waterloo

Chromatic index of random multigraphs

Combinatorics

Wed, 14.02.18

Andrei Asinowski FU Berlin

Enumeration of lattice paths with forbidden patterns

Combinatorics

Wed, 07.02.18

Anurag Bishnoi FU Berlin

Zeros of a polynomial in a finite grid

Combinatorics

Thu, 01.02.18

Tibor Szabó FU Berlin

Exploring the projective norm graphs

Combinatorics

Wed, 24.01.18

Dániel Korándi EPFL

Rainbow saturation and graph capacities

Combinatorics

Thu, 18.01.18

Tamás Mészáros FU Berlin

Boolean dimension and tree-width

Combinatorics

Thu, 11.01.18

Torsten Muetze TU Berlin

Sparse Kneser graphs are Hamiltonian

Combinatorics

Thu, 21.12.17

Simona Boyadzhiyska FU Berlin

Interval orders with restrictions on the interval lengths

Combinatorics

Wed, 20.12.17

Christoph Spiegel UPC Barcelona

On a question of Sárkozy and Sós

Combinatorics

Thu, 14.12.17

Martin Skrodzki FU Berlin

Combinatorial and Asymptotical Results on the Neighborhood Grid

Combinatorics

Thu, 07.12.17

Lutz Warnke Georgia Institute of Technology

Paking nearly optimal Ramsey R(3,t) graphs

Combinatorics

Wed, 06.12.17

Bart De Bruyn Ghent University

Old and new results on extremal generalized polygons

Combinatorics

Wed, 29.11.17

Ander Lamaison FU Berlin

The random strategy in Maker-Breakers

Combinatorics

Thu, 16.11.17

Patrick Morris FU Berlin

Random Steiner Triple systems

Combinatorics

Thu, 09.11.17

Anurag Bishnoi FU Berlin

Spectral methods in extremal combinatorics

Combinatorics

Wed, 25.10.17

Andrew Treglown Birmingham

The complexity of perfect matchings and packings in dense hypergraphs

Combinatorics

Wed, 31.05.17 at 16:15

Shagnik Das Berlin

Some of my favourite problems from Sanya

Combinatorics

Thu, 27.04.17 at 10:15

Hong Liu University of Warwick

Edges not in any monochromatic copy of a fixed graph.

Combinatorics

Wed, 19.04.17 at 16:15

Jan Corsten London School of Economics

Grid Ramsey Problem.

Combinatorics

Thu, 30.03.17 at 10:15

Adam Zsolt Wagner University of Illinois at Urbana-Champaign

Families with few k-chains

Combinatorics

Thu, 09.02.17 at 10:15

Frank Mousset ETH Zürich

Covering sparse graphs by monochromatic cycles

Combinatorics

Thu, 26.01.17 at 10:15

Christopher Kusch FU Berlin

Random Strategies are nearly optimal for generalised van der Waerden games

Combinatorics

Thu, 19.01.17 at 10:15

William T. Trotter Georgia Institute of Technology

Dimension and Cut Vertices

Combinatorics

Thu, 12.01.17 at 10:15

Tibor Szabó FU Berlin

The Oberwolfach problems

Combinatorics

Wed, 11.01.17 at 16:15

Matthew Jenssen London School of Economics

Exact Ramsey numbers of odd cycles via nonlinear optimisation

Combinatorics

Wed, 04.01.17 at 16:15

Bartosz Walczak Jagiellonian University

Coloring curves that cross a fixed curve.

Combinatorics

Thu, 15.12.16 at 10:15

Jaroslaw Grytczuk Jagiellonian University / Warsaw University of Technology

Majority Choosability of Digraphs.

Combinatorics

Wed, 07.12.16 at 16:15

Gwenaël Joret Université Libre de Bruxelles

Orthogonal graph decomposition.

Combinatorics

Thu, 01.12.16 at 10:15

Veit Wiechert TU Berlin

On the boxicity of graphs with no K_t minor.

Combinatorics

Wed, 23.11.16 at 16:15

Torsten Muetze TU Berlin

Trimming and gluing Gray codes.

Combinatorics

Wed, 09.11.16 at 16:15

Tamás Mészáros FU Berlin

Some combinatorial applications of Gröbner bases and standard monomials.

Combinatorics

Thu, 27.10.16 at 10:15

Tibor Szabó FU Berlin

Vertex Folkman Numbers.

Combinatorics

Wed, 19.10.16 at 16:15

Piotr Micek FU Berlin

Weak coloring numbers and poset's dimension.

Combinatorics

Wed, 13.07.16 at 16:15

Boris Bukh Carnegie Mellon University

One-sided epsilon-approximants.

Abstract.

Two common approximation notions in discrete geometry are ε-nets and ε-approximants. Of the two, ε-approximants are stronger. For the family of convex sets, small ε-nets exist while small ε-approximants unfortunately do not. In this talk, we introduce a new notion "one-sided ε-approximants", which is of intermediate strength, and prove that small one-sided ε-approximants do exist. The proof is based on a (modification of) the regularity lemma for words by Axaenovich--Person--Puzynina. Joint work with Gabriel Nivasch.

Combinatorics

Thu, 07.07.16 at 10:15

Anita Liebenau Monash University

Ramsey equivalence of $K_n$ and $K_n + K_{n−1}$.

Abstract.

Szab\’o, Zumstein, and Z\”urcher proved in 2010 that, for $n\geq 4$, the complete graph $K_n$ is Ramsey equivalent to $K_n+K_{n-2}$, the graph formed by taking the disjoint union of a copy of $K_n$ and a copy of $K_{n-2}$. In fact, they proved that one can add {\em many} disjoint copies of $K_{n-2}$ to $K_n$, and the resulting graph is still Ramsey equivalent to $K_n$. The situation is quite different for $K_{n-1}$: Fox, Grinshpun, Liebenau, Person, and Szab\’o proved in 2014 that $K_n$ is {\em not} Ramsey equivalent to the graph $K_n + 2K_{n-1}$, the graph containing a copy of $K_n$ and two copies of $K_{n-1}$. Nevertheless, it was conjectured in both papers that $K_n$ and $K_n + K_{n−1}$ are Ramsey equivalent for $n\geq 4$. We prove this conjecture. This is joint work with Thomas Bloom. .

Combinatorics

Wed, 29.06.16 at 16:15

Benny Sudakov ETH Zürich

Equiangular lines and spherical codes in Euclidean spaces.

Abstract.

A set of lines in R^d is called equiangular if the angles between any two of them are the same. The problem of estimating the size of the maximum family of equiangular lines has had a long history since late 1940's. A closely related notion is that of a spherical code, which is a collection C of unit vectors in Rd such that x \cdot y \in L for any distinct x,y in C and some set of real numbers L. Spherical codes have been extensively studied since their introduction in the 1970's by Delsarte, Goethals and Seidel. Despite a lot of attention in the last forty years, there are still many open interesting questions about equiangular lines and spherical codes. In this talk we report recent progress on some of them. Joint work with I. Balla, F. Drexler and P. Keevash.

Combinatorics

Thu, 23.06.16 at 10:15

Dániel Korándi ETH Zürich

Saturation in random graphs.

Abstract.

A graph H is K_s-saturated if it is a maximal K_s-free graph, i.e., H contains no clique on s vertices, but the addition of any missing edge creates one. The minimum number of edges in a K_s-saturated graph was determined over 50 years ago by Zykov and independently by Erdős, Hajnal and Moon. In this talk, we consider the random analog of this problem: minimizing the number of edges in a maximal K_s-free subgraph of the Erdős-Rényi random graph G(n,p). We give asymptotically tight estimates on this minimum, and also provide exact bounds for the related notion of weak saturation in random graphs. Joint work with Benny Sudakov.

Combinatorics

Thu, 02.06.16 at 10:15

Christian Reiher University of Hamburg

A Ramsey Class for Steiner Systems.

Abstract.

We construct a Ramsey class whose objects are Steiner systems. In contrast to the situation with general $r$-uniform hypergraphs, it turns out that simply putting linear orders on their sets of vertices is not enough for this purpose: we also have to strengthen the notion of subobjects used from ``induced subsystems'' to something we call ``strongly induced subsystems''. Moreover we study the Ramsey properties of other classes of Steiner systems obtained from this class by either forgetting the order or by working with the usual notion of subsystems. This leads to an interesting induced Ramsey theorem in which {\it designs} get coloured. This is joint work with Vindya Bhat, Jaroslav Ne\v{s}et\v{r}il, and Vojt\v{e}ch R\"{o}dl.

Combinatorics

Thu, 19.05.16 at 10:15

Tuan Tran Czech Academy of Sciences

Structure and supersturation for intersecting families.

Abstract.

A k-uniform family of subsets of [n] is called intersecting if it does not contain a pair of disjoint sets. The celebrated Erdos-Ko-Rado Theorem from 1961 asserts that, provided n>2k, any such system has size at most {n-1 \choose k-1}. A natural question is how many disjoint pairs must appear in a set system of larger size. In this paper, we determine the minimum number of disjoint pairs in small k-uniform families for k=o(\sqrt{n}), thus extending a result of Das, Gan and Sudakov (2016). Our main tool is a removal lemma for families with few disjoint pairs. As another application of the removal lemma, we show that almost all k-uniform intersecting families on [n], with n>(2+o(1))k, are trivial, i.e. all k-sets share a common element. This is based on my joint work with Balogh, Das, Liu and Sharifzadeh

Combinatorics

Thu, 12.05.16 at 10:15

Tibor Szabó FU Berlin

On the complexity of Ryser's Conjecture.

Abstract.

Every r-uniform hypergraph has a vertex cover of size r times its matching number. Ryser's Conjecture states that if the hypergraph is also r-partite, then for a cover it is enough to take (r-1)-times the matching number many vertices. For r=2 Ryser's Conjecture reduces to Konig's Theorem, for r=3 it was proved by Aharoni by topolgical methods, and for larger r it is wide open. In a recent joint work with Abu-Khazneh, Barat, and Pokrovskiy, we argue that Ryser's Conjecture, if true, is probably difficult.

Combinatorics

Wed, 04.05.16 at 16:15

Katherine Staden University of Warwick

The Erdős-Rothschild problem on edge-colourings.

Abstract.

Let $\bm{k} = (k_1,\ldots,k_s)$ be an $s$-tuple of positive integers. Given a graph $G$, how many ways are there to colour the edges of $G$ with $s$ colours so that there is no $c$-coloured copy of the complete graph on $k_c$ vertices, for any $c=1,\ldots,s$? Write $F(G;\bm{k})$ for this quantity and let $F(n;\bm{k})$ be its maximum over all graphs $G$ on $n$ vertices. What is $F(n;\bm{k})$ and which graphs $G$ attain this maximum? This problem was first considered by Erd\H{o}s and Rothschild in 1974, but it has only been solved for a very small number of non-trivial cases. In this talk I will survey the history of the problem, and will discuss some recent general results with Oleg Pikhurko (Warwick) and Zelealem Yilma (Carnegie Mellon Qatar).

Combinatorics

Wed, 27.04.16 at 16:15

Dhruv Mubayi UI Chicago

Recent advances using the stepping up technique.

Abstract.

I will give some details of recent constructions in hypergraph Ramsey theory that settle longstanding problems in the field. These are obtained by adding some new ingredients to the stepping up method of Erdos and Hajnal that first appeared in 1965. Most of this is joint work with Andrew Suk.

Combinatorics

Thu, 18.02.16 at 10:15

Codruţ Grosu FU Berlin

A lower bound for the Towers of Hanoi game with more pegs.

Abstract.

The Towers of Hanoi puzzle is played with N disks and 3 pegs. The disks are initially placed on one peg in increasing order according to size, and the goal is to move all the disks on another peg, without ever placing a larger disk on a smaller one. The solution is simple and uses a recursive algorithm for moving the disks. A well-known generalization asks for the minimum number of moves when p pegs are available. This problem is much more difficult and only recently the case p = 4 was solved by Bousch. The purpose of my talk is to present a lower bound on the number of moves needed for p ≥ 5 pegs and N disks. This lower bound is asymptotically better than the previously best known when p is fixed and N tends to infinity.

Combinatorics

Thu, 11.02.16 at 10:30

Tamás Mészáros FU Berlin

A conjecture on shattering-extremal set systems

Abstract.

We say that a set system F ⊆ 2^[n] shatters a given set s ⊆ [n] if F|s = {f ∩ s : f ∈ F} = 2^s . One related notion is the VC-dimension of a set system: the size of the largest set shattered by F. The Sauer inequality states that in general, a set system F shatters at least |F| sets. A set system is called shattering-extremal if it shatters exactly |F| sets. Such families have many interesting features. Here we present several approaches to study shattering-extremal set systems together with a conjecture about the eliminability of elements from extremal families.

Combinatorics

Thu, 04.02.16 at 10:15

Christoph Spiegel FU Berlin

Van der Waerden Games - Part II

Combinatorics

Thu, 28.01.16 at 10:15

Christoph Spiegel FU Berlin

Van der Waerden Games

Combinatorics

Thu, 21.01.16 at 10:15

Giulia Codenotti FU Berlin

Kruskal-Katona and Macauley theorems in a relative setting

Abstract.

A relative simplicial complex is a family of sets which is the set-theoretic difference D\G of a simplicial complex D and a subcomplex G of D. Relative simplicial complexes were introduced by Reisner and Stanley, and in a recent paper of Adiprasito and Sanyal, properties of relative simplicial complexes play a key role in solving the upper bound problem for Minkowski sums of polytopes, which asks for an upper bound on the number of k-faces of a Minkowski sum of polytopes. This has raised interest in better understanding which properties of simplicial complexes can be "relativized". One fundamental result about simplicial complexes is the Kruskal-Katona theorem, which characterizes f-vectors of simplicial complexes. I will show a simple extension of the Kruskal-Katona theorem to relative simplicial complexes, and an analogue extension for Macauley theorem [which can be interpreted as an analogue of the Kruskal-Katona theorem for multicomplexes]. This is joint work with Raman Sanyal.

Combinatorics

Thu, 14.01.16 at 10:15

Torsten Muetze TU Berlin

Bipartite Kneser graphs are Hamiltonian

Abstract.

For integers k>=1 and n>=2k+1, the bipartite Kneser graph H(n,k) is defined as the graph that has as vertices all k-element and all (n-k)-element subsets of {1,2,...,n}, with an edge between any two vertices (=sets) where one is a subset of the other. It has long been conjectured that all bipartite Kneser graphs have a Hamilton cycle. The special case of this conjecture concerning the Hamiltonicity of the graph H(2k+1,k) became known as the 'middle levels conjecture' or 'revolving door conjecture', and has attracted particular attention over the last 30 years. One of the motivations for tackling these problems is an even more general conjecture due to Lovasz, which asserts that in fact every connected vertex-transitive graph (as e.g. H(n,k)) has a Hamilton cycle (apart from five exceptional graphs). In this talk I present a simple and short induction proof that all bipartite Kneser graphs H(n,k) have a Hamilton cycle (assuming that H(2k+1,k) has one). This is joint work with Pascal Su (ETH Zurich).

Combinatorics

Thu, 10.12.15 at 10:15

Julia Wolf University of Bristol

Counting monochromatic structures in finite abelian groups

Abstract.

In this talk we aim to determine the minimum number of monochromatic additive configurations in any 2-colouring of a finite abelian group (such as Z/pZ for p a prime). The techniques used to address this question, which include additive combinatorics and quadratic Fourier analysis, originate in quantitative approaches to Szemeredi’s theorem. Perhaps surprisingly, some of our results in the arithmetic setting have implications for a graph-theoretic problem that has been open since the 1960s.

Combinatorics

Thu, 03.12.15 at 10:15

Shagnik Das FU Berlin

The Erdős-Rothschild problem for intersecting families

Abstract.

The Erdős-Rothschild problem is a twist on the typical extremal problem, asking for the structure with the maximum number of r-colourings without a monochromatic forbidden substructure. While originally phrased in the context of Turán theory, it can extend any extremal problem. Recently, there has been a great deal of interest in the Erdős-Rothschild problem for intersecting families, particularly for families of sets or vector spaces. We will present a general framework that allows us to extend these previous results to much larger, and, in some cases, optimal, choices of parameters of the families in question. This proof also applies to new settings, such as intersecting families of permutations. Joint work with Dennis Clemens and Tu(r)an Tran.

Combinatorics

Thu, 26.11.15 at 10:15

József Balogh University of Illinois

On Some Recent Applications of the Container Method

Abstract.

I will talk about some recent applications of the container method. There are two types of applications, I present examples for both; one where it is unexpected that the method would work, the other where it is expected, but current versions of container lemmas are not applicable. Partly it is joint work with Jozsef Solymosi and Adam Wagner.

Combinatorics

Thu, 19.11.15 at 10:15

Olaf Parczyk Goethe Universität Frankfurt

Universality in random and sparse hypergraphs

Abstract.

Finding spanning subgraphs is a well studied problem in random graph theory, in the case of hypergraphs less is known and it is natural to study the corresponding spanning problems for random hypergraphs. We study universality, i.e. when does an r-uniform hypergraph contain any hypergraph on n vertices and with maximum vertex degree bounded by $\Delta$? For $\mathcal{H}^{(r)}(n,p)$ we show that this holds for $p=\omega( (\ln n/n)^{ 1/ \Delta } )$ a.a.s. Furthermore we derive from explicit constructions of universal graphs due to Alon, Capalbo constructions of universal hypergraphs of size almost matching the lower bound $\Omega (n^{r-r/ \Delta})$. This is joint work with Samuel Hetterich and Yury Person.

Combinatorics

Tue, 10.11.15 at 10:15

Pedro Berrizbeitia Universidad Simón Bolívar

On additive Properties of Multiplicative Groups on finite Index in Fields

Abstract.

Let m > 1 be an integer. Except for finitely many primes p, the equation x^m + y^m = t mod p has integer solutions x and y for all integer t. The problem is a classical one in Number Theory. In fact, if N_{p,t} is the number of solutions (x mod p, y mod p) of the equation, then |N_{p,t} - p| = O( p^{1/2} ). The analog problem for infinite or more general fields is the following: Let G be a multiplicative group of finite index in F*, the multiplicative group of units of the field F, what does G + G look like, in particular, when is G + G = F? The first publication on the subject appeard in 1989, when Leep and Shapiro, gave a positive answer when the index of G in F* is 3. That is, they proved that G + G = F, except for a small and short list of exceptional fields. They conjectured that the result was true in the case of index 5, for any infinite field F. They mentioned that they had not been succesfull even for F = Q, the rational numbers. In the talk we will prove that if G is of finite index in Q*, then G − G = Q, that is, every rational number is writen as the difference of two elements of G. The proof is a very nice application of the Van der Waerden Theorem on artithmetic progressions, that we will state without proof. More general results in Ramsey Theory allow to prove the same result of any infinite field, and even for some other more general rings. We will brieffly describe these more general results and consequences. We will also discuss the behaviour of G + G, of G + G + G, etc. In fact, we will scketch the solution published in 2011 of a conjecture posed in 1992 by Bergelson and Shapiro on an additive question and give Florian’s theorem on the general behaviour of G_n + G_n, for a specific sequence of subgroups of index n ∈ Q*.

Combinatorics

Thu, 05.11.15 at 10:15

Ping Hu University of Warwick

Short induced cycles in graphs

Abstract.

Let C(n) denote the maximum number of induced copies of 5-cycles in graphs on n vertices. For n large enough, we show that C(n)=abcde + C(a)+C(b)+C(c)+C(d)+C(e), where a+b+c+d+e = n and a,b,c,d,e are as equal as possible. Moreover, for n being a power of 5, we show that the unique graph on n vertices maximizing the number of induced 5-cycles is an iterated blow-up of a 5-cycle. The proof uses flag algebra computations and stability methods. Joint work with Balogh, Lidický and Pfender.

Combinatorics

Thu, 29.10.15 at 10:15

Christoph Spiegel FU Berlin

Threshold functions for systems of equations in random sets

Abstract.

We present a unified framework to deal with threshold functions for the existence of certain combinatorial structures in random sets. The structures will be given by certain linear systems of equations M · x = 0 and we will use the binomial random set model where each element is chosen independently with the same probability. This covers the study of several fundamental combinatorial families such as k-arithmetic progressions, k-sum-free sets, B_h [g] sequences and Hilbert cubes of dimension k. Furthermore, our results extend previous ones about B_h [2] sequences by Godbole et al. We show that there exists a threshold function for the property "A^m contains a non-trivial solution of M · x = 0" where A is a random set. This threshold function depends on a parameter maximized over all subsystems, a notion previously introduced by Rödl and Rucinski. The talk will contain a formal definition of trivial solutions for any combinatorial structure, extending a previous definition by Ruzsa. Furthermore, we will study the behavior of the distribution of the number of non-trivial solutions in the threshold scale. We show that it converges to a Poisson distribution whose parameter depends on the volumes of certain convex polytopes arising from the linear system under study as well as the symmetry inherent in the structures, which we formally define and characterize. Joint work with Juanjo Rué and Ana Zumalacárregui.

Combinatorics

Thu, 22.10.15 at 10:15

Tibor Szabó FU Berlin

Half-random Maker-Breaker games

Abstract.

We study Maker-Breaker positional games between two players, one of whom is playing randomly against an opponent with an optimal strategy. In both such scenarios, that is when Maker plays randomly and when Breaker plays randomly, we determine the sharp threshold bias of classical graph games, such as connectivity, Hamiltonicity, and minimum degree-k. The traditional, deterministic version of these games, with two optimal players playing, are known to obey the so-called probabilistic intuition. That is, the threshold bias of these games is asymptotically equal to the threshold bias of their random counterpart, where players just take edges uniformly at random. We find, that despite this remarkable agreement of the results of the deterministic and the random games, playing randomly against an optimal opponent is not a good idea: the threshold bias becomes significantly higher in favor of the clever player. An important qualitative aspect of the probabilistic intuition nevertheless carries through: for Maker to occupy a connected graph or a Hamilton cycle, the bottleneck is still the ability to achieve that there is no isolated vertex in his graph. The talk represents joint work with Jonas Groschwitz.

Combinatorics

Thu, 23.07.15 at 11:15

Dániel Korándi ETH Zürich

A random triadic process

Abstract.

Given a random 3-uniform hypergraph H=H(n,p) on n vertices where each triple independently appears with probability p, consider the following graph process. We start with the star G_0 on the same vertex set, containing all the edges incident to some vertex v_0, and repeatedly add an edge xy if there is a vertex z such that xz and zy are already in the graph and xzy∈H. We say that the process propagates if it reaches the complete graph before it terminates. In this talk we show that the threshold probability for propagation is p=1/2√n using the differential equation method. As an application, we obtain the upper bound p=1/2√n on the threshold probability that a random 2-dimensional simplicial complex is simply connected. Joint work with Yuval Peled and Benny Sudakov.

Combinatorics

Wed, 15.07.15 at 16:15

Clément Requilé FU Berlin

Triangles in random cubic planar graphs

Abstract.

This talk will be about the exact counting of triangles in cubic planar graphs, and some asymptotic consequences. The starting point is the study, done in [BKLMcD] by means of generating functions, of the asymptotic number of labeled cubic planar graphs with a fixed number of vertices. Our approach, following theirs, is based on connectivity decomposition and generating functions which reduce the problem to a map enumeration question. We show how to adapt this decompositions in order to encode triangles. At the end of the talk we will explain how to use these equations to get limiting laws for the number of triangles in cubic planar graphs, as well as the asymptotic number of triangle-free planar graphs on a given number of vertices. Work in progress with Juanjo Rué. [BKLMcD] M. Bodirsky, M. Kang, M. Löffler and C. McDiarmid. Random Cubic Planar Graphs. Random Structures and Algorithms, 30 (2007) 78-94.

Combinatorics

Wed, 08.07.15 at 16:15

Jozsef Balogh University of Illinois at Urbana-Champaign

On the applications of counting independent sets in hypergraphs

Abstract.

Recently, Balogh-Morris-Samotij and Saxton-Thomason developed a method of counting independent sets in hypergraphs. I will survey the field, and explain several applications. This includes counting maximal triangle-free graphs, counting -free graphs, estimate volume of metric spaces, etc. These results are partly joint with Liu, Morris, Petrickova, Samotij, Sharifzadeh, and Wagner.

Combinatorics

Thu, 02.07.15 at 10:15

Boris Bukh Carnegie Mellon University

Common subsequences in words and permutations

Abstract.

Every sufficiently large collection of objects always contains two similar objects. For example, a large collection of words contains a pair of words with a long common subsequence. How long? In this talk, we look at several versions of this problem. We will see how this problem leads to some algebraic constructions, Fourier-like arguments, and an innocently-looking problem about monotone functions. The talk is based on the joint works with Lidong Zhou, Jie Ma and Venkatesan Guruswami. The work began 3 years ago, on a visit to FU Berlin.

Combinatorics

Thu, 25.06.15 at 10:15

Christopher Kusch FU Berlin

Strong Ramsey Games: Drawing on an infinite board

Abstract.

We will consider a strong Ramsey-type game played on the edges of the complete -uniform hypergraph with infinitely many vertices. Two players, first player and second player, try to claim edges to build a copy of a fixed graph . First player starts and whoever builds a copy of first wins. It is known that if they play on finitely many vertices, player one can guarantee to win, if the number of vertices is large enough. We will then prove that this is false on infinitely many vertices and provide sufficient conditions a hypergraph needs to satisfy in order for second player to guarantee a draw as well as a -uniform example of such a hypergraph. This is joint work with Dan Hefetz, Lothar Narins, Alexey Pokrovskiy, Clément Requilé and Amir Sarid.

Combinatorics

Wed, 17.06.15 at 16:15

Florian Pfender UC Denver

Semidefinite programming in extremal graph theory and Ramsey theory

Abstract.

Ten years ago, Razborov developed the theory of flag algebras. In this theory, many extremal problems on densities of small substructures in large structures can easily be expressed and studied. One of the most successful methods inside this theory is the so called "plain flag algebra method." In this method, semidefinite programming is used to optimally combine a large set of true equalities and inequalities to bound densities in the extremal object. Many new results in extremal graph theory have been proved this way. In general, the method is often successful if the extremal example is a simple blow up of a small graph --- a very common outcome in this field. Another common outcome is an iterated blow up of a small graph. In this situation, the plain flag algebra method alone rarely succeeds. In this talk I will present a way how to extend the plain method to deal with a number of questions of this flavor. In the last part of the talk I will show a surprising trick how to use the plain method to improve the upper bounds on some small Ramsey numbers. This is joint work with Bernard Lidický.

Combinatorics

Thu, 04.06.15 at 10:15

Benny Sudakov ETH Zürich

Grid Ramsey problem and related questions

Abstract.

The Hales-Jewett theorem is one of the pillars of Ramsey theory, from which many other results follow. A celebrated result of Shelah says that Hales-Jewett numbers are primitive recursive. A key tool used in his proof, known as cube lemma, has become famous in its own right. In its simplest form, it says that if we color the edges of the Cartesian product in colors then, for sufficiently large, there is a rectangle with both pairs of opposite edges receiving the same color. Hoping to improve Selah’s result, Graham, Rothschild and Spencer asked more than 20 years ago whether cube lemma holds with , which is polynomial in . We show that this is not possible by providing a superpolynomial lower bound in . We also discuss a number of related questions, among them a solution of the problem of Erdos and Gyarfas on generalized Ramsey numbers. Joint work with Conlon, Fox and Lee.

Combinatorics

Wed, 03.06.15 at 16:15

Ana Zumalacárregui University of New South Wales

Additive bases for intervals

Abstract.

A set is said to be an additive basis for the interval if every element in the interval can be represented as sum of two elements of the set. A natural question arises in this context: how small could such a basis be? In this talk we will address this question and study the minimal cardinality of a Basis for (that is, the number of representations of every element in is at least ). Even though it is clear that such quantity is of order , an asymptotic for is not known to exist (even in the simplest case ). We will study this quantity and show that both the and the tend to the same constant as grows. The strategy follows the lines of [CRV'10] where the case of -Sidon sets for intervals was studied (that is the number of representations is at most ) and approaches the problem by considering successive constructions of sets whose support is restricted. A key point in the argument is to exploit good constructions -based on ideas from Ruzsa [R'90]- of sets on finite groups whose representation function is closed to be constant. Joint work with Javier Cilleruelo and Carlos Vinuesa. [CRV'10] J. Cilleruelo, I. Ruzsa, and C. Vinuesa. Generalized Sidon sets. Adv. Math., 225(5):2786-2807, 2010. [R'90] I. Z. Ruzsa. A just basis. Monatsh. Math., 109(2):145-151, 1990.

Combinatorics

Wed, 27.05.15 at 16:15

Sylwia Antoniuk Adam Mickiewicz University

On the connectivity Waiter-Client game

Abstract.

We consider a variation of the connectivity Waiter-Client game played on an -vertex graph which consists of disjoint spanning trees. In this game in each round Waiter offers Client edges of which have not yet been offered. Client chooses one edge and the remaining edges are discarded. The aim of Waiter is to force Client to build a connected graph. If this happens Waiter wins. Otherwise Client is the winner. It is known that for and for and even , Waiter can always force Client to build a connected graph. Bednarska-Bzdega et al. [BBHKL2014] asked if this is true for the remaining values of . We give and answer to this question, namely we show that for most of the Waiter does not always have a Winning strategy. This is a joint work with Codrut Grosu and Lothar Narins. [BBHKL2014] M. Bednarska-Bzdega, D. Hefetz, M. Krivelevich, T. Łuczak, Manipulative waiters with probabilistic intuition

Combinatorics

Thu, 21.05.15 at 10:15

Shagnik Das FU Berlin

Comparable pairs in set families

Abstract.

Given a family of subsets of , we say two sets are comparable if or . Sperner’s celebrated theorem gives the size of the largest family without any comparable pairs. This result was later generalised by Kleitman, who gave the minimum number of comparable pairs appearing in families of a given size. In this talk we shall consider a complimentary problem posed by Erdös and Daykin and Frankl in the early ‘80s. They asked for the maximum number of comparable pairs that can appear in a family of subsets of , a quantity we denote by . We will first resolve an old conjecture of Alon and Frankl, showing that when . Time (and interest) permitting, we shall then discuss some further improvements to bounds on for various ranges of the parameters. This is joint work with Noga Alon, Roman Glebov and Benny Sudakov.

Combinatorics

Thu, 09.04.15 at 11:15

Ewan Davies London School of Economics

Counting in hypergraphs via regularity inheritance

Abstract.

We develop a theory of regularity inheritance in 3-uniform hypergraphs. As a simple consequence we deduce a slight strengthening of a counting lemma of Frankl and Rödl. We believe that the approach is sufficiently flexible and general to permit extensions of our results in the direction of a hypergraph blow-up lemma.

Combinatorics

Mon, 23.03.15 at 10:15

Imre Leader University of Cambridge

Tiling with Arbitrary Tiles

Abstract.

A `tile' is a finite subset T of Zn. It may or may not be possible to partition Zn into copies of T. However, Chalcraft conjectured that every T does tile Zd for some d. In this talk, we will discuss some examples, and also a proof of the conjecture, recently obtained in joint work with Vytautas Gruslys and Ta Sheng Tan.

Combinatorics

Thu, 19.03.15 at 10:15

Alexey Pokrovskiy FU Berlin

Rainbow matchings and rainbow connectedness

Combinatorics

Thu, 12.03.15 at 10:15

Lluis Vena Charles University Prague

Deducing an arithmetic removal lemma from the removal lemma for hypergraphs and its applications

Abstract.

The (hyper)graph removal lemma says that if a large (hyper)graph K does not have many copies of a given (hyper)graph H, then K can be made free of copies of H by deleting a small number of edges. An arithmetic removal lemma says the following. Given a group G and some subset Xi of G, if a linear system Ax = 0 does not have many solutions with xi in Xi, then we can obtain new sets Xi' where the linear system Ax = 0 does not have any solutions if the variables xi take values in Xi'. The sets Xi' have been obtained from Xi by removing few of its elements. One of the applications of the arithmetic removal lemmas is a more direct proof of Szemerédi's Theorem, regarding finding arbitrarily long arithmetic progressions on the integers (or in other groups), and its multidimensional counterpart, regarding finding k-dimensional simplicies in Zk. In this talk we show a deduction of an arithmetic removal lemma using the combinatorial one.

Combinatorics

Thu, 26.02.15 at 10:15

Alexey Pokrovskiy FU Berlin

Open problems in Ramsey Theory (pt 2)

Abstract.

A selection of fascinating open problems in all areas of Ramsey Theory will be presented. These problems were collected at the AIM Graph Ramsey Theory workshop, San Jose, January 2015. If anyone has a problem they would like to present (not necessarily in Ramsey theory), feel free to bring it and present it.

Combinatorics

Thu, 19.02.15 at 10:15

Tibor Szabó FU Berlin and Alexey Pokrovskiy FU Berlin

Open problems in Ramsey Theory

Combinatorics

Thu, 12.02.15 at 10:15

Christopher Pütz FU Berlin

An exposition of the Green-Tao theorem

Abstract.

Szemerédi's theorem states that any subset A of the positive integers with positive natural density limsupN→∞ |A ∩ [N]|/N contains arbitrary long arithmetic progressions. Allowing sets to have natural density zero the assertion remains true under certain conditions. This result is called the relative Szemerédi theorem. One is able to construct a function that corresponds to a superset of almost all prime numbers, for which the relative Szemerédi theorem holds and provides arbitrary long arithmetic progressions in the prime numbers. This result is also known as the Green-Tao theorem and was first proven by Ben Green and Terence Tao. Lately there was a paper of Conlon, Fox and Zhao who gathered simplifications of the original proof that have been made in recent years and introduced a new key step that further simplifies the proof. In this talk I will give a sketch of the proof of the relative Szemerédi theorem for the special case of 3-term arithmetic progressions as well as an outline of how to construct such a function associated with a superset of almost all prime numbers. I will include the proofs of some well-chosen intermediate results.

Combinatorics

Thu, 22.01.15 at 11:00

Dennis Clemens FU Berlin

Reiher's Clique Density Theorem

Abstract.

One of the most classic results in Extremal Graph Theory is Turán's Theorem, which guarantees the existence of cliques of given order r in a graph G, provided that its edge density d exceeds a certain threshold. Naturally, one may wonder how many such cliques must necessarily be contained in G when the edge density d becomes larger than this threshold. Lovász and Simonovits [1] conjectured their number to be at least Fr(d)nr + O(nr-2), where F describes a certain piecewise concave function. After some partial results in the last decades, the conjecture was proven by Christian Reiher [2] recently, by using weighted graphs and Lagrange multipliers which help to transfer this discrete problem into a continuous setting. In the talk we will see a construction showing that the above bound is tight asymptotically and then we will see an overview on the proof by Christian Reiher. [1] L. Lovász and M. Simonovits: On the number of complete subgraphs in a graph II, Studies in pure mathematics, pages 459-495, Birkhäuser, 1983. [2] C. Reiher: The Clique Density Theorem, Hamburger Beiträge zur Mathematik 462, pages 1-25, 2012.

Combinatorics

Wed, 21.01.15 at 16:15

Codruţ Grosu FU Berlin

On transversals avoiding complete subgraphs

Abstract.

Let G be a multipartite graph with each block of size b and maximum degree d. It was shown by Haxell that b ≥ 2d is a sufficient (and best possible) condition for G to contain an independent transversal. Szabó and Tardos studied a generalization of this problem, where one requires the transversal to be Ks-free instead of independent. They conjectured that the optimal lower bound for b is of the order of d/s. The purpose of this talk is to present an symptotic proof of this conjecture, due to Harris and Srinivasan. The proof uses a new version of the Local Lemma, which I will try to explain.

Combinatorics

Thu, 15.01.15 at 10:15

Juanjo Rué FU Berlin

Arithmetic removal lemmas and independent sets in hypergraphs

Abstract.

In the last years, several authors have studied sparse and random analogues of a wide variety of results in extremal combinatorics. Very recently, due to the work of Balogh, Morris, and Samotij, and the work of Saxton and Thomasson on the structure of independent sets on hypergraphs, several of these questions have been addressed in a new framework by using the so-called containers in hypergraphs. In this talk I will present how to use this technology together with arithmetic removal lemmas due to Serra, Vena and Kral in the context of arithmetic combinatorics. We will show how to get sparse (and random) analogues of well-known additive combinatorial results even in the non-abelian situation. This talk is based on a work (still in progress!) joint with Oriol Serra and Lluís Vena.

Combinatorics

Thu, 08.01.15 at 10:15

Christopher Kusch FU Berlin

Random Algebraic Constructions

Abstract.

The aim of this talk is to introduce Bukh's random algebraic construction of large graphs not containing a given bipartite subgraph. If time permits, we discuss this method in the context of graphs with few paths of prescribed length between any two vertices as done by Conlon.

Combinatorics

Thu, 18.12.14 at 10:15

Dimitrios Thilikos University of Athens

Erdős–Pósa property for minor and topological minor models

Abstract.

A class of graphs C satisfies the Erdős–Pósa property if there exists a function f such that, for every integer k and every graph G, either G contains k vertex-disjoint subgraphs each isomorphic to a graph in C, or there is a subset S of V(G) of at most f(k) vertices such that G ∖ S has no subgraph in C. Erdős and Pósa (1965) proved that the set of all cycles satisfies this property for all graphs with f(k) = O(k log k). Given a connected graph H, let M(H) be the class of graphs that contain H as a minor. Robertson and Seymour (1986) proved that M(H) satisfies the Erdős-Pósa property if and only if H is planar. When H is planar, finding the smallest possible function fM(H) has been an active area of research in the last years. In this talk we will survey some recent combinatorial and algorithmic results in this direction, and we will particularly focus on other variants of the Erdős–Pósa property such as the case where the k subgraphs have to be edge-disjoint or the case where M(H) is the class of graphs that contain a graph H as a topological minor. On going work with Dimitris Chatzidimitriou, Jean-Florent Raymond, Ignasi Sau.

Combinatorics

Wed, 10.12.14 at 16:15

Piotr Micek Jagiellonian University/TU Berlin

Posets and minors

Abstract.

Posets of height 2 may have arbitrarily large dimension. But posets of bounded height with somehow restricted cover graphs do have bounded dimension. (If you are about to give up this talk. Let me just mention that I will try to make it a kind of introductory into posets dimension theory) In 1977, Trotter and Moore proved that a poset has dimension at most 3 whenever its cover graph is a forest. In a series of papers it is proved that when a poset has bounded height and its cover graph is planar (2014), or has bounded treewidth (2015+), or most generally excludes a fixed graph as a topological minor (2015+), then the poset has bounded dimension. We conjecture that a restriction on bounded height, forbidding a long chain in a poset, may be relaxed to exclusion of two long incomparable chains. We support our feeling providing three theorems: (1) Every poset without two long incomparable chains whose cover graph has bounded pathwidth has bounded dimension; (2) For every poset without two long incomparable chains whose cover graph excludes a fixed graph as a topological minor, all standard examples in the poset are small; (3) Every interval order, i.e. (2+2)-free poset, whose cover graph excludes a fixed graph as a topological minor has bounded dimension.

Combinatorics

Thu, 04.12.14 at 10:15

Cathryn Supko FU Berlin

Combinatorics

Thu, 27.11.14 at 10:15

Clément Requilé FU Berlin

A parameterized algorithm for the diameter improvement problem for plane graphs

Abstract.

A problem mentioned by Chung in 1987: given a plane graph and an integer d, is it possible to reduce the diameter of the graph to at most d by adding non-edges, while conserving planarity? Fellows and Dejter have shown in an unpublished paper in 1993 that the oriented case was NP-Complete and that both the oriented and undirected cases were FPT (FIxed Parameter Tractable). But their proof is mostly based on the Robertson and Seymour theorem and is therefore non-constructive as of yet. This type of result is in essence theoretical, but it gives us good hopes of finding efficient FPT algorithms. We will focus on a natural variant of this problem in the undirected case, where the number of edges that can be added per face is upper-bounded by an integer k. We will then give an FPT algorithm (parameterized by d and k) for this variant, build on dynamic programming. This talk is based on joint work with Dimitrios Thilikos (LIRMM, France/University of Athens).

Combinatorics

Thu, 20.11.14 at 10:15

Tuan Tran FU Berlin

A removal lemma for Kneser graphs

Abstract.

Given natural numbers n, k with 2 ≤ k < n/2. We write ([n] choose k) for the family of all subsets of size k of [n]. The Kneser graph K(n, k) is the graph whose vertex set is ([n] choose k ) where two sets A, B ∈ ([n] choose k ) are adjacent if and only if A ∩ B = ∅. The celebrated theorem of Erdős-Ko-Rado from 1961 says that every independent set in K(n, k) has size at most (n - 1 choose k - 1), and the only independent sets of this size are stars. We prove a removal lemma for these graphs. Loosely speaking, it tells us that every subfamily of ([n] choose k) of size roughly (n - 1 choose k - 1) with few disjoint pairs must be very close to a star. Armed with this lemma, we establish a sparse version of the Erdős-Ko-Rado theorem. This settles a question of Bollobás, Narayanan and Raigorodskii (2014). The talk represents joint work with Shagnik Das.

Combinatorics

Wed, 12.11.14 at 16:15

Tibor Szabó FU Berlin

On the minimum degree of minimal Ramsey graphs

Abstract.

A graph G is r-Ramsey for H if for any r-coloring of its edges there is a monochromatic copy of H. G is called r-Ramsey minimal for H if it is r-Ramsey for H, but no subgraph of it is r-Ramsey for H. We study the smallest minimum degree an r-Ramsey-minimal graph for the clique Kk can have. This function was introduced and determined for two colors by Burr, Erdős and Lovász in 1975. We extend their theorem for r colors and connect the function to the so-called Erdős-Rogers function, which was introduced and studied more than a decade earlier. This represents joint work with Jacob Fox, Andrey Grinshpun, Anita Liebenau, and Yury Person.

Combinatorics

Wed, 05.11.14 at 14:15

Olaf Parczyk FU Berlin

Relative entropy and Sidorenko’s conjecture

Abstract.

Following the paper by Balázs Szegedy we introduce the family of graphs H that admit a probability distribution of copies in an arbitrary graph G obtained by iterating conditionally independent couplings starting from the uniform distribution on edges. We investigate the famous conjecture by Erdős-Simonovits and Sidorenko inside this family. As a tool we use an inclusion exclusion type formula for relative entropy. The method gives a unified treatment for most known cases of the conjecture and it implies various new results as well.

Combinatorics

Thu, 10.07.14 at 14:15

Alice Händel FU Berlin

Partielle Transversale in Lateinischen Quadraten

Abstract.

Ein lateinisches Quadrat der Ordnung n ist ein n x n Feld bestehend aus n2 Zellen, welche mit n verschiedenen Symbolen gefüllt sind, wobei in jeder Zeile und jeder Spalte jedes Symbol genau einmal vorkommen darf. Eine Menge aus n Zellen, genau eine aus jeder Zeile und jeder Spalte, bestehend aus k verschiedenen Symbolen, heißt partielles Transversal der Länge k. Im Rahmen dieses Seminarvortrages wird der Beweis von Shor und Hatami, dass jedes lateinische Quadrat der Ordnung n ein partielles Transversal der Länge mindestens n - 11,053 log2 n besitzt, bewiesen.

Combinatorics

Wed, 09.07.14

Hiệp Hàn Emory University

Maximum number of colourings without monochromatic Schur triples

Abstract.

We investigate subsets of finite abelian groups which maximize the number of r-colourings without monochromatic Schur triples, i.e. without triples of the form (a, b, c) such that a + b = c. For r = 2, 3 and abelian groups G of order |G| = 2 mod 3 we show that the maximum is achieved only by largest sum-free sets. For abelian groups of even order and r = 4 the maximum is achieved by the union of two largest sum-free sets, whenever they exist. Joint work with Andrea Jimenez.

Combinatorics

Wed, 25.06.14 at 14:15

Alexey Pokrovskiy FU Berlin

Linkage structures in tournaments (part II)

Abstract.

Thomassen conjectured that there is a function f(k) such that every strongly f(k)-connected tournament contains k edge-disjoint Hamiltonian cycles. This conjecture was recently proved by Kuhn, Lapinskas, Osthus, and Patel who showed that f(k) < O(k2(log k)2) and conjectured that there was a constant C such that f(k) < Ck2. We'll discuss a proof of this conjecture, giving an overview of the Kuhn, Lapinskas, Osthus, and Patel proof and modifications which are needed to obtain the quadratic bound on f(k).

Combinatorics

Wed, 18.06.14 at 14:15

Alexey Pokrovskiy FU Berlin

Linkage structures in tournaments

Abstract.

A (directed) graph is k-linked if for two sets of vertices {x1, ..., xk} and {y1, ..., yk}, there are vertex disjoint paths {P1, ..., Pk}, such that Pi goes from xi to yi. A theorem of Bollobas and Thomason says that every 22k-connected (undirected) graph is k-linked. It is desirable to obtain analogues for directed graphs as well. Although Thomassen showed that the Bollobas-Thomason Theorem does not hold for general directed graphs, for tournaments he showed that there is a function f(k) such that every strongly f(k)-connected digraph is k-linked. The bound on f(k) was reduced to O(k log k) by Kuhn, Lapinskas, Osthus, and Patel, who also conjectured that a linear bound should hold. We'll talk about a proof of this conjecture. The proof uses linkage structures in tournaments which were recently introduced by Kuhn, Lapinskas, Osthus, and Patel in order to prove a conjecture of Thomassen about edge disjoint Hamiltonian cycles in tournaments. As a consequence of our results we will also show that there is a constant C such that every Ck2 connected tournament contains k edge-disjoint Hamiltonian cycles, solving another conjecture of Kuhn, Lapinskas, Osthus, and Patel.

Combinatorics

Wed, 11.06.14 at 14:15

Tamás Mészáros Central European University

Shattering extremal set systems

Abstract.

We say that a set system F ⊆ 2[n] shatters a given set S ⊆ [n] if 2S = {F ∩ S : F ∈ F}. One related notion is the VC-dimension of a set system: the size of the largest set shattered by F. The Sauer inequality states that in general, a set system F shatters at least |F| sets. A set system is called shattering-extremal if it shatters exactly |F| sets. Here we present two methods, one algebraic and one graph theoretical, to study shattering-extremal set systems. When considering a set system as a set of characteristic vectors, one can define the corresponding vanishing ideal of polynomials. The standard monomials and Gröbner bases of these ideals can be used to characterize extremal set systems and to obtain many interesting results in connection with these combinatorial objects. This algebraic characterization leads to an efficient method for testing extremality. The inclusion graph of a set system F ⊆ 2[n] is the labelled graph GF whose vertices are the elements of F, and there is an edge going from G to F with label j iff F = G ∪ {j}. GF is just the Hasse diagram of F labelled in a natural way. This graph theoretical point of view enables us to study the problem in a more familiar environment. We managed to characterize extremal set systems of VC-dimension at most 2 in terms of their inclusion graphs.

Combinatorics

Thu, 05.06.14 at 10:15

Lander Ramos Universitat Politècnica de Catalunya

Random planar graphs with minimum degree two

Abstract.

We illustrate how to use the symbolic method to determine asymptotic parameters of a combinatorial class. In particular, we compute the asymptotic exponential growth of the class of planar graphs with minimum degree at least two, as well as the expected number of edges of a random graph from this class.

Combinatorics

Wed, 14.05.14 at 14:15

Olaf Parczyk FU Berlin

On the logarithmic calculus and Sidorenko's conjecture

Abstract.

Sidorenko's conjecture states that if H is a bipartite graph then the random graph with edge density p has in expectation asymptotically the minimum number of copies of H over all graphs of the same order and edge density. It is known to be true for various families of graphs, including trees, even cycles and bipartite graphs with one vertex complete to the other side. We take a look at the paper by Li and Szegedy where they establish the logarithmic calculus. This is their abstract: We study a type of calculus for proving inequalities between subgraph densities which is based on Jensen's inequality for the logarithmic function. As a demonstration of the method we verify the conjecture of Erdős-Simonovits and Sidorenko for new families of graphs. In particular we give a short analytic proof for a result by Conlon, Fox and Sudakov. Using this, we prove the forcing conjecture for bipartite graphs in which one vertex is complete to the other side.

Combinatorics

Wed, 07.05.14 at 14:15

Lothar Narins FU Berlin

Tau and the Connectedness of Line Graphs

Abstract.

The topological connectedness of the independence complex is a useful and important tool that has lead to such things as the proof of Ryser's Conjecture for 3-partite 3-graphs. In this talk, I will present a lower-bound on the connectedness of the line graph of a hypergraph in terms of the hypergraph's vertex-cover number (tau). The bound is tight for general hypergraphs, but there are potentially improvements to be made in the case of r-partite r-graphs. I will sketch the proof of a conjectured lower-bound improvement for 3-partite 3-graphs for tau at most 12.

Combinatorics

Mon, 05.05.14 at 10:15

Deryk Osthus University of Birmingham

Proof of Two Conjectures of Thomassen on Tournaments

Abstract.

We prove the following two conjectures of Thomassen on highly connected tournaments: (i) For every k, there is an f(k) so that every strongly f(k)-connected tournament contains k edge-disjoint Hamilton cycles (joint work with Kühn, Lapinskas and Patel). (ii) For every k, there is an f(k) so that every strongly f(k)-connected tournament has a vertex partition A, B for which both A and B induce a strongly k-connected tournament (joint with Kühn and Townsend). Our proofs introduce the concept of `robust dominating structures', which will hopefully have further applications. I will also discuss related open problems on cycle factors and linkedness in tournaments.

Combinatorics

Wed, 30.04.14 at 14:15

Juanjo Rué FU Berlin

Applications of Tutte's tree decomposition in the enumeration of bipartite graph families

Abstract.

We adapt the grammar introduced by Chapuy, Fusy, Kang and Shoilekova to study bipartite graph families which are defined by their 3-connected components. More precisely, in this talk I will explain how to get the counting formulas for bipartite series-parallel graphs (and more generally of the Ising model over this family of graphs), as well as asymptotic estimates for the number of such graphs with a fixed size. This talk is based in a work in progress joint with Kerstin Weller.

Combinatorics

Wed, 09.04.14 at 14:15

Tibor Szabó FU Berlin

What is Ramsey-equivalent to a clique?

Abstract.

A graph G is Ramsey for H if every two-colouring of the edges of G contains a monochromatic copy of H. Two graphs H and H' are Ramsey-equivalent if every graph G is Ramsey for H if and only if it is Ramsey for H'. In the talk we discuss the problem of determining which graphs are Ramsey-equivalent to the complete graph Kk. In particular we prove that the only connected graph which is Ramsey-equivalent to Kk is itself. This gives a negative answer to a question of Zumstein, Zürcher, and the speaker. For the proof we determine the smallest possible minimum degree that a minimal Ramsey graph for Kk ⋅ K2 (the graph containing the clique with a pendant edge) can have. This represents joint work with Jacob Fox, Andrey Grinshpun, Anita Liebenau, and Yury Person.

Combinatorics

Mon, 31.03.14 at 10:15

Simeon Ball Universitat Politècnica de Catalunya

On the Turán number of complete bipartite graphs

Combinatorics

Wed, 05.03.14 at 14:15

Codruţ Grosu FU Berlin

An algebraic approach to Turán densities

Combinatorics

Wed, 26.02.14 at 13:15

Alexey Pokrovskiy FU Berlin

Reading Group: Independent Sets in Hypergraphs Part 5 - The KŁR Conjecture

Combinatorics

Wed, 19.02.14 at 14:15

Alexey Pokrovskiy FU Berlin

Reading Group: Independent Sets in Hypergraphs Part 4 - Applications

Combinatorics

Wed, 12.02.14 at 14:15

Codruţ Grosu FU Berlin

Reading Group: Independent Sets in Hypergraphs Part 3 - The Proof Continued

Combinatorics

Fri, 31.01.14 at 09:30

Dennis Clemens FU Berlin and Lothar Narins FU Berlin

Reading Group: Independent Sets in Hypergraphs Part 2 - The Proof

Combinatorics

Wed, 29.01.14

Miloš Stojaković University of Novi Sad

Threshold for Maker-Breaker H-game

Abstract.

We will look at the Maker-Breaker H-game played on the edge set of the random graph Gn,p. In this game two players, Maker and Breaker, alternately claim unclaimed edges of Gn,p, until all the edges are claimed. Maker wins if he claims all the edges of a copy of a fixed graph H; Breaker wins otherwise. It turns out that, with the exception of trees and triangles, the threshold for this game is given by the threshold of the corresponding Ramsey property of Gn,p with respect to the graph H. This is joint work with Rajko Nenadov and Angelika Steger.

Combinatorics

Wed, 29.01.14

Julia Ehrenmüller TU Hamburg-Harburg

On the intersection of longest paths

Abstract.

A longest path in a graph has the property that there exists no other path in the graph that is strictly longer. In 1966 Gallai asked whether all longest paths in a connected graph have nonempty intersection. This is not true in general and various counterexamples have been found. However, the answer to Gallai's question is positive for several well-known classes of graphs, e.g. trees, outerplanar graphs, split graphs, and 2-trees. In this talk we discuss these results and present a proof that all series-parallel graphs have a vertex that is common to all of its longest paths. We also comment on how this vertex can be found in quadratic time. Joint work with Cristina G. Fernandes and Carl G. Heise.

Combinatorics

Fri, 24.01.14 at 09:30

Victor Falgas-Ravry Umeå University

On the connectivity of k-nearest-neighbours random geometric graphs

Abstract.

Many real-life networks have an inherent geometry, which should be reflected in the random graph models used to analyse their behaviour. A typical example is that of radio networks: radio devices may find it easier to exchange information if they lie close to each other than if they lie far apart. This and other examples have motivated research into specifically geometric models of random graphs. In this talk I will present one such model, the k-nearest-neighbours random geometric graph model, and discuss its connectivity properties. I will present in particular a sharp threshold result, which is joint with Mark Walters (QMUL), as well as some more recent work of mine on subcritical components.

Combinatorics

Wed, 22.01.14 at 14:15

Juanjo Rué FU Berlin

Reading Group: Independent Sets in Hypergraphs Part 1 - Introduction

Combinatorics

Fri, 17.01.14 at 09:30

Sylwia Antoniuk Adam Mickiewicz University

Random triangular groups

Combinatorics

Wed, 18.12.13 at 14:15

Christian Reiher University of Hamburg

Counting odd cycles in locally dense graphs

Abstract.

Roughly speaking we prove that if a graph on n vertices has the property that each set of vertices whose size is linear in n spans at least as many edges as it spans in a random graph of density d, then the graph contains at least as many (odd) cycles of fixed length as the random graph does. With "at least" being replaced by "(almost) exactly" this is well known, but the present version seems to require a different approach. The result addresses a question of Y. Kohayakawa, B. Nagle, V. Rödl, and M. Schacht.

Combinatorics

Tue, 17.12.13 at 14:15

Bernhard Schmitt Nanyang Technological University, Singapore

Unique Sums and Differences in Finite Abelian Groups

Abstract.

Let A and B be subsets of a finite abelian group G. We say that A + B contains a unique sum if there exists g ∈ G such that g = a + b for exactly one pair (a, b) ∈ A × B. Unique differences are defined analogously. The main goal in the investigation of these phenomena is to find sufficient conditions for the existence of unique sums and differences. Such results have a variety of applications, for instance, in the context of cyclotomic integers of small modulus, field extensions, spectral properties of subsets of Fp, balanced sets, and circulant weighing matrices. I will present a new method to study unique sums and differences, which mainly relies on the Smith Normal Form of the corresponding linear relations. This yields substantial improvements upon previously known results. For instance, we obtain the following. Let G be a finite abelian group and let p be the smallest prime divisor of the order of G. If A and B are subsets of G with ∜(12)|A|+|B|-2 < p, then A + B contains a unique sum.

Combinatorics

Wed, 11.12.13

Kathleen Johst FU Berlin

The k-color Ramsey number of a graph with m edges

Abstract.

The k-color Ramsey number rk(H) of a graph H is the smallest integer N, such that in each k-coloring of the edges of the complete graph KN on N vertices there is a monochromatic copy of H. In my talk I show an upper bound rk(H) ≤ k2√(km)(1 + o(1)) for bipartite graphs H with m edges and no isolated vertices and k ≥ 2. Further, for a general graph H with m edges and no isolated vertices I discuss an upper bound rk(H) ≤ k3km2/3, for k ≥ 3.

Combinatorics

Wed, 27.11.13 at 14:15

Alexey Pokrovskiy FU Berlin

Nonnegative sums in a set of numbers

Combinatorics

Wed, 20.11.13

Piotr Micek Jagiellonian University

Nonrepetitve sequences, colorings and entropy compression method

Abstract.

A sequence is nonrepetitive if it does not contain two adjacent identical blocks. The remarkable construction of Thue asserts that 3 symbols are enough to build an arbitrarily long nonrepetitive sequence. It is still not settled whether the following extension holds: for every sequence of 3-element sets L1, ..., Ln there exists a nonrepetitive sequence s1, ..., sn with si ∈ Li. We propose a new non-constructive way to build long nonrepetitive sequences and provide an elementary proof that sets of size 4 suffice confirming the best known bound. The simple double counting (entropy compression method) in the heart of the argument is inspired by the recent algorithmic proof of the Lovász local lemma due to Moser and Tardos. We will discuss recent results concerning nonrepetitive colorings of graphs with a special emphasis on applications of entropy compression method. Joint work with Jarosław Grytczuk and Jakub Kozik.

Combinatorics

Wed, 13.11.13

Frederik Garbe FU Berlin

On Graphs with Excess 2

Abstract.

The Moore bound m(d, k) = 1 + d Σi=1,...,k-1(d - 1)i is a lower bound for the number of vertices of a graph by given girth g = 2k + 1 and minimal degree d. Hoffmann and Singleton, Bannai and Ito, Damerell showed that graphs with d > 2 tight to this bound can only exist for girth 5 and degree 3, 7, 57. The difference to the Moore bound by given girth is called the excess of a graph. In the case of girth 5 Brown showed that there are no graphs with excess 1 and Bannai and Ito showed that for g ≥ 7 there are also no graphs with excess 1. We generalize the result of Kovács that, under special conditions for the degree d, there are no graphs with excess 2 and girth 5 and prove the new result that an excess-2-graph with odd degree and girth 9 cannot exist. In this proof we discover a link to certain elliptic curves. Furthermore we prove the non-existence of graphs with excess 2 for higher girth and special valences under certain congruence conditions.

Combinatorics

Wed, 06.11.13 at 14:15

Peter Keevash University of Oxford

Dynamic concentration of the triangle-free process

Abstract.

The triangle-free process begins with an empty graph on n vertices and iteratively adds edges chosen uniformly at random subject to the constraint that no triangle is formed. We determine the asymptotic number of edges in the maximal triangle-free graph at which the triangle-free process terminates. We also bound the independence number of this graph, which gives an improved lower bound on Ramsey numbers: we show R(3, t) > (1/4 - o(1))t2/log t, which is within a 4 + o(1) factor of the best known upper bound. Furthermore, we determine which bounded size subgraphs are likely to appear in the maximal triangle-free graph produced by the triangle-free process: they are precisely those triangle-free graphs with maximal average density at most 2.

Combinatorics

Thu, 31.10.13

László Lovász Eötvös Loránd University

Extremal graphs and graph limits

Abstract.

Growing sequences of dense graphs have a limit object in terms of a symmetric measurable 2-variable function. A typical use of this fact in graph theory is the following: we want to prove a result, say an inequality between subgraph densities. We look at a sequence of counterexamples, and consider their limit. Often this allows clean formulations and arguments that would be awkward or impossible in the finite setting. This setting also allows us to pose and in some cases answer general questions about extremal graph theory: which inequalities between subgraph densities are valid, and what is the possible structure of extremal graphs.

Combinatorics

Wed, 23.10.13

Tuan Tran FU Berlin

Subgraphs of dense multipartite graphs

Abstract.

Let H be a non-bipartite graph. Pfender conjectured that for large ℓ depending on H, every balanced ℓ-partite graph whose parts have pairwise edge density greater than (χ(H) - 2)/(χ(H) - 1) contains a copy of H. He verified the conjecture for cliques. In this work, we show that the same premise implies the existence of much larger graphs. As a consequence, we confirm the conjecture for a family of graphs. Finally, we disprove the conjecture in general by constructing several families of counterexamples. This is a joint work with Lothar Narins.

Combinatorics

Wed, 16.10.13

Juanjo Rué FU Berlin

On the probability of planarity of a random graph near the critical point

Abstract.

Consider the uniform random graph G(n, M) with n vertices and M edges. Erdős and Rényi (1960) conjectured that the limit lim P[G(n, n/2) is planar] exists and is a constant strictly between 0 and 1. Łuczak, Pittel and Wierman (1994) proved this conjecture and Janson, Łuczak, Knuth and Pittel (1993) gave lower and upper bounds for this probability. In this work we determine the exact probability of a random graph being planar near the critical point M = n/2. More precisely, for each u, we find an exact analytic expression for p(u) = lim P[G(n, n/2(1 + u n-1/3) is planar] In particular, we obtain p(0) is approximately equal to 0.99780. Additionally, we are also capable to extend these results to classes of graphs closed under taking minors. This is a joint work with Marc Noy (UPC-Barcelona) and Vlady Ravelomanana (LIAFA-Paris).

Combinatorics

Thu, 20.06.13

Julia Böttcher London School 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.

Combinatorics

Thu, 13.06.13 at 16:00

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.

Combinatorics

Wed, 12.06.13 at 14:00

Andrey Kupavskii Moscow State University

Two notions of unit distance graphs

Abstract.

A complete (unit) distance graph in Rd 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 Rd is any subgraph of such a graph. We show that for any fixed d the number of complete distance graphs in Rd on n labelled vertices is 2(1 + o(1))dn log2n while the number of distance graphs in Rd on n labelled vertices is 2(1 - 1/⌊d/2⌋ + o(1))n2/2.

Combinatorics

Thu, 04.04.13

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.

Combinatorics

Thu, 21.02.13

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.

Combinatorics

Thu, 14.02.13 at 10:00

Tibor Szabó FU Berlin and Tuan Tran FU Berlin

Ramanujan Graphs: The Construction

Combinatorics

Thu, 31.01.13 at 10:00

Codruţ Grosu FU Berlin and Anita Liebenau FU Berlin

Ramanujan Graphs: PSL 2 ( q )

Combinatorics

Thu, 17.01.13

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 = Cd, as n → ∞, asymptotically almost all graphs with n vertices and ⌊Cn2 - 1/d log1/dn⌋ 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.

Combinatorics

Thu, 10.01.13 at 10:00

Dennis Clemens FU Berlin and Lothar Narins FU Berlin

Ramanujan Graphs: Number Theory

Combinatorics

Thu, 20.12.12 at 10:00

Frederik Garbe FU Berlin and Tuan Tran FU Berlin

Ramanujan Graphs: Algebraic Graph Theory

Combinatorics

Thu, 13.12.12

Tuan Tran FU Berlin

Subspace evasive sets

Abstract.

Let F be a finite field. A subset S ⊆ Fn is called (k, c)-evasive if it has intersection of size at most c with every k-dimensional affine subspace of Fn. A simple probabilistic argument shows that a random set S ⊂ Fn 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 ⊂ Fn of size |F|(1 - ε)n. In this talk we will present the construction and its application in extremal combinatorics.

Combinatorics

Thu, 06.12.12

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 G1, ..., Gn 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.

Combinatorics

Thu, 29.11.12

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

Combinatorics

Thu, 22.11.12

Codruţ Grosu FU Berlin

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

Combinatorics

Thu, 01.11.12

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.

Combinatorics

Wed, 04.07.12

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.

Combinatorics

Wed, 27.06.12

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.

Combinatorics

Wed, 20.06.12

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

Combinatorics

Wed, 13.06.12

Peter Allen London School of Economics and Julia Böttcher London School of Economics

Tight cycles in dense uniform hypergraphs

Combinatorics

Fri, 08.06.12

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.

Combinatorics

Wed, 06.06.12

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 = (z1, z2, ..., 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 = (x1, x2, ..., xn) 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 zi = xi, 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). This is joint work with Benjamin Doerr, Reto Spöhel and Carola Winzen from MPI Saarbrücken.

Combinatorics

Wed, 30.05.12

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

Combinatorics

Wed, 23.05.12

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.

Combinatorics

Wed, 16.05.12

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: A description of the low-dimensional faces of the polytope P(G) Non-linear relations between the components of the f-vector of P(G) 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

Combinatorics

Wed, 09.05.12

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.

Combinatorics

Wed, 02.05.12

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.

Combinatorics

Wed, 25.04.12

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.

Combinatorics

Wed, 18.04.12

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

Combinatorics

Wed, 22.02.12

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.

Combinatorics

Wed, 15.02.12

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.

Combinatorics

Wed, 08.02.12

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.

Combinatorics

Wed, 25.01.12

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 rν, but it is conjectured that there is always a cover of size at most (r - 1)ν.

Combinatorics

Wed, 18.01.12

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.

Combinatorics

Wed, 11.01.12

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.

Combinatorics

Fri, 16.12.11

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(n, q) 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(n, q)? 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.

Combinatorics

Fri, 09.12.11

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)

Combinatorics

Fri, 02.12.11

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.

Combinatorics

Wed, 23.11.11

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.

Combinatorics

Wed, 16.11.11

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.

Combinatorics

Fri, 11.11.11

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.

Combinatorics

Fri, 04.11.11

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

Combinatorics

Fri, 28.10.11

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.

Combinatorics

Wed, 19.10.11

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

Combinatorics

Fri, 30.09.11

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.

Combinatorics

Wed, 07.09.11

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

Combinatorics

Tue, 23.08.11

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.

Combinatorics

Wed, 13.07.11

Kevin Milans University of South Carolina

Combinatorics

Wed, 06.07.11

Uri Zwick Tel Aviv University

All-Pairs Shortest Paths in O(n2) Expected Time

Abstract.

We present an All-Pairs Shortest Paths (APSP) algorithm whose expected running time on a complete directed graph on n vertices whose edge weights are chosen independently and uniformly at random from [0, 1] is O(n2). This resolves a long standing open problem. The algorithm is a variant of the dynamic all-pairs shortest paths algorithm of Demetrescu and Italiano. The analysis relies on a proof that the expected number of locally shortest paths in such randomly weighted graphs is O(n2). We also present a dynamic version of the algorithm that recomputes all shortest paths after a random edge update in O(log2 n) expected time. Joint work with Yuval Peres, Dmitry Sotnikov and Benny Sudakov.

Combinatorics

Wed, 29.06.11

Benny Sudakov UCLA

Nonnegative k-sums, fractional covers, and probability of small deviations

Abstract.

More than twenty years ago, Manickam, Miklos, and Singhi conjectured that for any integers n ≥ 4k, every set of n real numbers with nonnegative sum has at least (n - 1 choose k - 1) k-element subsets whose sum is also nonnegative. In this talk we discuss the connection of this problem with matchings and fractional covers of hypergraphs, and with the question of estimating the probability that the sum of nonnegative independent random variables exceeds its expectation by a given amount. Using these connections together with some probabilistic techniques, we verify the conjecture for n ≥ 33k2. This substantially improves the best previously known exponential lower bound on n. If time permits we will also discuss applications to finding the optimal data allocation for a distributed storage system and how our approach can be used to prove some theorems on minimum degree ensuring the existence of perfect matchings in hypergraphs. Joint work with N. Alon and H. Huang, last part is also joint with P. Frankl, V. Rodl and A. Rucinski.

Combinatorics

Wed, 22.06.11

Hanno Lefmann TU Chemnitz

Edge Colorings of Graphs and Fixed Forbidden Monochromatic Subgraphs

Abstract.

Given a fixed positive integer r and a fixed graph F, we consider for host-graphs H on n vertices, n large, the number cr,F(H) of r-colorings of the set of edges of H such that no monochromatic copy of F arises. In particular, we are looking at the maximum cr,F(n) of cr,F(H) over all host-graphs H on n vertices. For forbidden fixed complete graphs F = Kℓ the quantity cr,F(n) has been investigated by Yuster, and Alon et al. and they proved for r = 2 or r = 3 colors that the maximum number of r-colorings is achieved by the corresponding Turán graph for F, while for r ≥ 4 colors this does not hold anymore. Based on similar results for some special forbidden hypergraphs, one might suspect that such a phaenomenon holds in general. However, it seems this is not valid for (at least some) classes of forbidden bipartite graphs.

Combinatorics

Wed, 15.06.11

Anita Liebenau FU Berlin

A survey on the 'Cops-and-robbers problem'

Abstract.

Cops and robbers - in theory almost as thrilling as in an action film. The game was introduced by Nowakowski and Winkler, and by Quilliot more than thirty years ago: A number of cops moves along the edges of a graph and try to catch the robber. First, the cops move (at most) one step, then the robber. The cop number c(G), introduced by Aigner and Fromme in 1982, is the minimal number of cops needed in G in order to catch the robber. Numerous questions connected with this game have been posed and partly answered: What kind of graphs can be covered by one cop alone (the so-called cop-win graphs)? How many cops are enough to catch the robber on a planar graph? What can we say about graphs embeddable in orientable surfaces of genus g? How many cops do you need/are enough on general graphs? Variations include a drunken robber (who moves randomly, and not in an intelligent way), a very fast robber (who may move along longer paths in one step), and non-perfect information. In the talk, I will define all necessary concepts, and give an overview of what has been done in these last three decades. Further, I will sketch a proof by Scott and Sudakov (2011) of one of the most recent upper bounds on c(G).

Combinatorics

Thu, 09.06.11

Endre Szemerédi Rényi Institute of Mathematics

Long Arithmetic Progression in Sumsets

Abstract.

We are going to give exact bound for the size of longest arithmetic progression in sumset sums. In addition we describe the structure of the subset sums and give applications in number theory and probability theory. (this part is partially joint work with Van Vu)

Combinatorics

Fri, 20.05.11

Timothy Gowers University of Cambridge

A combinatorial proof of the density Hales-Jewett theorem

Combinatorics

Fri, 13.05.11

Dan Spielman Yale University

On some problems that have been bugging me

Combinatorics

Thu, 12.05.11

Dennis Clemens FU Berlin

The uniqueness conjecture of Markoff numbers and equivalent problems: Part II

Combinatorics

Wed, 04.05.11

Dennis Clemens FU Berlin

The uniqueness conjecture of Markoff numbers and equivalent problems: Part I

Abstract.

In 1879/80 Andrei A. Markoff studied the minima of indefinite quadratic forms and found an amazing relationship to the Diophantine equation x2 + y2 + z2 = 3xyz, which today is named the Markoff equation. Later Georg Frobenius conjectured that each solution of this equation is determined uniquely by its maximal component. Defining these components as the so-called Markoff numbers this conjecture means that for each Markoff number m there exists up to permutation exactly one triple (m, p, q) with maximum m solving the Markoff equation. Till this day it is not known whether the conjecture is true, or not. However, we are able to prove uniqueness for certain Markoff numbers and we can find different statements, such as a statement in Markoff's theory on the minima of quaratic forms, being equivalent to the uniqueness conjecture of the Markoff numbers. At first I will give a short overview on the properties of Markoff numbers as well as some easier results concerning the uniqueness conjecture. We will see how the solutions of Markoff's equation, called Markoff triples, can be computed recursively such that we will get a tree of infinitely many Markoff triples. Then, by using correspondences to other trees we will get different statements from Number Theory, Graph Theory and Linear Algebra being equivalent to the uniqueness conjecture. The second part of my presentation will be concerned with the best known result on this conjecture proven by J. O. Button in 2001. With a bijection between Markoff triples and elements in certain number fields we will see how the uniqueness problem can be reformulated as a question in Ideal Theory. Taking results on ideals and continued fractions we finally can conclude a criterion proving uniqueness for a big subset of Markoff numbers.

Combinatorics

Thu, 24.02.11

Fiona Skerman Australian National University

Row and column sums of random 0-1 matrices

Abstract.

Construct a random m × n matrix by independently setting each entry to 1 with probability p and to 0 otherwise. We study the joint distribution of the row sums s = (s1, ..., sm) and column sums t = (t1, ..., tn). Clearly s and t have the same sum, but otherwise their dependencies are complicated. We prove that under certain conditions the distribution of (s, t) is accurately modelled by (S1, ..., Sm, T1, ..., Tn), where each Sj has the binomial distribution Binom(n, p'), each Tk has the binomial distribution Binom(m, p'), p' is drawn from a truncated normal distribution, and S1, ..., Sm, T1, ..., Tn are independent apart from satisfying Σj=1,...,m Sj = Σk=1,...,n Tk. We also consider the case of random 0-1 matrices where only the number of 1s is specified, and also the distribution of s when t is specified. In the seminar I will include details of one of the bounding arguments used in this last case. This bounding argument is an application of the generalised Doob's martingale process. These results can also be expressed in the language of random bipartite graphs. Joint work with Brendan McKay.

Combinatorics

Wed, 23.02.11

Katherine Edwards McGill University

Packing T-joins in Planar Graphs

Abstract.

Let G be a graph and T an even sized subset of its vertices. A T-join is a subgraph of G whose odd-degree vertices are precisely those in T, and a T-cut is a cut δ(S) where S contains an odd number of vertices of T. It has been conjectured by Guenin that if all T-cuts of G have the same parity and the size of every T-cut is at least k, then G contains k edge-disjoint T-joins. We discuss some recent progress on this conjecture and related results.

Combinatorics

Wed, 16.02.11

Oliver Friedman LMU München

On Exponential Lower Bounds for Solving Infinitary Payoff Games and Linear Programs: Part II

Abstract.

Policy iteration is one of the most important algorithmic schemes for solving problems in the domain of determined game theory such as parity games, stochastic games and Markov decision processes, and many more. It is parameterized by an improvement rule that determines how to proceed in the iteration from one policy to the next. It is a major open problem whether there is an improvement rule that results in a polynomial time algorithm for solving one of the considered game classes. Simplex algorithms for solving linear programs are closely related to policy iteration algorithms. Like policy iteration, the simplex algorithm is parameterized by a so-called pivoting rule that describes how to proceed from one basic feasible solution in the linear program to the next. Also, it is a major open problem whether there is a pivoting rule that results in a (strongly) polynomial time algorithm for solving linear programs. We describe our recent constructions for parity games that give rise to superpolynomial and exponential lower bounds for all major improvement rules, and how to extend these lower bounds to more expressive game classes like stochastic games. We show that our constructions for parity games can be translated to Markov decision processes, transferring our lower bounds to their domain, and finally show how the lower bounds for the MDPs can be transferred to the linear programming domain, solving problems that have been open for several decades.

Combinatorics

Fri, 28.01.11

Dmitry Shabanov Moscow State University

The Problem of Erdős and Hajnal Concerning Colorings of Hypergraphs and its Generalizations

Abstract.

The talk is devoted to the classical exremal combinatorial problem that was stated by P.Erdős and A.Hajnal in the 60-s. The task is to find the value m(n, r) equal to the minimum number of edges in an n-uniform non-r-colorable hypergraph. This problem has a lot of generalizations and is closely related to the classical problems of Ramsey theory. We shall discuss the known bounds in the Erdős-Hajnal problem, present some new results and pay special attention to the probabilistic methods, by which these results have been obtained.

Combinatorics

Fri, 21.01.11

Tibor Szabó FU Berlin

The Local Lemma is tight for SAT II

Abstract.

I will give a construction of unsatisfiable k-SAT formulas, where each variable is contained in only a few clauses. The numerical value of "few" is asymptotically best possible. Joint work with Heidi Gebauer and Gabór Tardos.

Combinatorics

Fri, 14.01.11

Tibor Szabó FU Berlin and Gabór Tardos Rényi Institute of Mathematics

The Oberwolfach Problems

Combinatorics

Fri, 17.12.10

Tibor Szabó FU Berlin

The Local Lemma is tight for SAT

Abstract.

We construct unsatisfiable k-CNF formulas where every clause has k distinct literals and every variable appears in at most (2/e + o(1))2k/k clauses. The lopsided Loca Lemma shows that our result is asymptotically best possible. The determination of this extremal function is particularly important as it represents the value where the k-SAT problem exhibits its complexity hardness jump: from having every instance being a YES-instance it becomes NP-hard just by allowing each variable to occur in one more clause. We also consider the related extremal function l(k) which denotes the maximum number, such that every k-CNF formula with each clause containing k distinct literals and each clause having a common variable with at most l(k) other clauses, is satisfiable. We establish that l(k) = (1/e + o(1))2k The SAT-formulas are constructed via special binary trees. In order to construct the trees a continuous setting of the problem is defined, giving rise to a differential equation. The solution at 0 diverges, which in turn implies that the binary tree obtained from the discretization of this solution has the required properties. Joint work with Heidi Gebauer and Gabór Tardos.

Combinatorics

Fri, 10.12.10

Yury Person FU Berlin

Extremal Hypergraphs for Hamilton Cycles

Abstract.

We study sufficient conditions for various Hamilton cycles in k-uniform hypergraphs and obtain both Turán- and Dirac-type results. In particular, we show that the only extremal 3-uniform hypergraph (for n moderately large) not containing a loose Hamilton cycle on n vertices consists of the complete hypergraph on n - 1 vertices and an isolated vertex (thus answering a question of Woitas). More generally, we determine extremal hypergraphs for so-called l-tight Hamilton cycles and we give first sufficient conditions on the minimum degree δ of type c(n choose k - 1), with fixed c < 1 and n sufficiently large, that ensure the existence of Hamilton cycles. Joint work with Roman Glebov and Wilma Weps.

Combinatorics

Fri, 03.12.10

Michael Krivelevich Tel Aviv University

The Size Ramsey Number of a Directed Path

Abstract.

Given a (di)graph H and an integer q ≥ 2, the size Ramsey number re(H, q) is the minimal number m for which there is a (di)graph G with m edges such that every q-coloring of G contains a monochromatic copy of H. We study the size Ramsey number of the directed path of length n in oriented graphs, where no antiparallel edges are allowed. We give nearly tight bounds for every fixed number of colors, showing that for every q ≥ 2, the corresponding number re(H, q) has asymptotic order of magnitude n2q - 2 + o(1). A joint work with Ido Ben-Eliezer (Tel Aviv U.) and Benny Sudakov (UCLA).

Combinatorics

Fri, 09.07.10 at 11:00

Gábor Mészáros HU Berlin

Road Coloring Problem

Abstract.

The road coloring problem deals with the question whether there exists an edge-coloring of a network such that by using special instructions, one can reach or locate an object or destination from any other point within the network. Precisely, if you have a directed graph G with regular out-degree k, the main question is, whether you can color the edges such a way, that: all k edges leaving any vertex have distinct colors and there is a suitable sequence w of colors, such that no matter which vertex we choose as start-point we get the same end-point, reading the word w label to label and choosing the suitable edge (according to w), on which we can travel to the next vertex. It was first conjectured in 1970 by Weiss and Adler, that one can always find an appropriate coloring with a suitable word, if the digraph is strongly connected and aperiodic, that is, there is no integer k > 1 that divides the length of every cycle of the graph. In 2007 Trahtman proved the conjecture (now it is called Road coloring theorem). In my talk I will present a partial result proved by Kari (2002), which says that the theorem is true if the graph is eulerian and regular, that is, all vertices have in and outdegree k.

Combinatorics

Fri, 25.06.10 at 11:00

Anusch Taraz TU Munich

On co-prime labellings of trees

Abstract.

A conjecture by Entringer from around 1980 states that the vertices of every n-vertex tree can be labelled with numbers 1 up to n in such a way that adjacent vertices get co-prime labels. In joint work with P.E. Haxell and O. Pikhurko we recently managed to prove this conjecture for sufficiently large n. I will discuss the proof in this talk.

Combinatorics

Wed, 16.06.10 at 11:00

Wilma Weps FU Berlin

On Size Ramsey Number of Graphs with Bounded Maximum Degree

Abstract.

The size Ramsey number r̂(G) of a graph G is the smallest number of integers r̂ such that there exists a graph F with r̂ edges for which every red-blue-edge-coloring contains a monochromatic copy of G. Josef Beck raised the question whether for a graph G with bounded maximum degree d there exists a constant c(d) depending only on the maximum degree such that r̂(G) < c(d)·n, with n the number of vertices of G. It has shown to be true that such a constant exists if G is a cycle or a tree. In my talk I will present a counterexample by Rödl and Szemerédi which shows that the statement above already fails if d = 3.

Combinatorics

Fri, 11.06.10 at 11:00

Balázs Szegedy University of Toronto

Limits of discrete structures (recent directions)

Abstract.

This talk is a status report on a recently developing subject in the frame of which big finite structures are viewed as approximations of infinite analytic structures. This framework enables one to use differential calculus, measure theory, topology and other infinite tools to analyze finite structures.

Combinatorics

Wed, 02.06.10 at 11:00

Gábor Mészáros HU Berlin

Path Size Ramsey Numbers

Abstract.

The size Ramsey number r̂(G) of a graph G is the smallest integer r̂ such that there is a graph F of r̂ edges with the property that any two-coloring of the edges of G yields a monochromatic copy of G. An obvious upper bound is known for the size Ramsey number of an arbitrary graph G, namely r̂(G) ≤ (r(G) choose 2) where r(G) denotes the Ramsey number of G. For paths Erdős offered 100$ for a proof or disproof of the following conjectures: r̂(Pn)/n → ∞ r̂(Pn)/n2 → 0 In 1983 Beck proved that for every sufficiently large value of n r̂(Pn) < 900·n, which result answered Erdős's question. In my talk I will present Beck's proof and discuss some related results in the area, including some interesting counterexamples which tell us that Beck's result is not necessarily true for general trees.

Combinatorics

Wed, 19.05.10 at 11:00

Roman Glebov FU Berlin

On-line Ramsey Numbers II

Abstract.

In Ramsey theory, we mostly look at the number r(t) denoting the minimum number of vertices sich that a two-coloring of the edges of the clique on r(t) many vertices necessarily produces a monochromatic t-subclique (we also say an r(t)-clique "arrows" a t-clique). The size Ramsey number r'(t) is the smallest number of edges such that there exists a graph with r'(t) edges arrowing an r(t)-clique. In my two talks I present the on-line version of this problem according to a resent paper by David Conlon. In a two-players-game, Builder draws edges one-by-one, and Painter colors them as each appears. Builder's aim is to force Painter to draw a monochromatic t-clique. In my second talk on the on-line Ramsey numbers, I present a specific upper bound for r''(t) of order 4t - c(log2(t))/(loglog(t)).

Combinatorics

Wed, 12.05.10 at 11:00

Roman Glebov FU Berlin

On-line Ramsey Numbers I

Abstract.

In Ramsey theory, we mostly look at the number r(t) denoting the minimum number of vertices sich that a two-coloring of the edges of the clique on r(t) many vertices necessarily produces a monochromatic t-subclique (we also say an r(t)-clique "arrows" a t-clique). The size Ramsey number r'(t) is the smallest number of edges such that there exists a graph with r'(t) edges arrowing an r(t)-clique. In my two talks I present the on-line version of this problem according to a resent paper by David Conlon. In a two-players-game, Builder draws edges one-by-one, and Painter colors them as each appears. Builder's aim is to force Painter to draw a monochromatic t-clique. The minimum number of edges which Builder must draw is the on-line Ramsey number r''(t). The main result presented in the first talk is the fact that for in finitely many values of t, r''(t) is exponentially smaller than r'(t).

Combinatorics

Wed, 05.05.10 at 11:00

Yury Person HU Berlin

A conjecture of Erdős on graph Ramsey numbers

Abstract.

For a given graph G, let r(G) be the minimum number n such that any two-coloring of the edges of the complete graph Kn on n vertices yields a monochromatic copy of G. For example it is known that r(Kk) is at least 2k/2 and at most 22k and despite efforts of many researchers the constant factors in the exponents remain the same for more than 60 years! For a graph G with m edges and no isolated vertices Erdős conjectured that r(G) < 2C√(m) (this would be then best possible up to a constant factor in view of the above mentioned bounds for r(Kk)). Very recently, Benny Sudakov proved this conjecture. In my talk I will present Sudakov's proof and discuss some related results and propblems in the area.

Combinatorics

Wed, 28.04.10 at 11:00

Oleg Pikhurko Carnegie Mellon University

An analytic approach to stability

Abstract.

This is an attempt to understand how the recently developed theory of graph limits may apply to finite problem of extremal graph theory. We formulate the notion of a stable problem (meaning, roughly speaking, that almost extremal graphs have structure close to that of an extremal graph) and give an equivalent characterization in terms of graph limits. As an application, we present a new proof of the Erdős-Simonovits stability theorem.

Combinatorics

Wed, 21.04.10 at 11:15

Tibor Szabó FU Berlin

A combinatorial model for the diameter of a polyhedra

Abstract.

The Hirsch Conjecture states that the diameter of a d-dimensional polytope with n facets is at most n - d. The best general upper bound due to Kalai and Kleitman is n1 + log d. For constant dimension Larman showed that the diameter is linear in n. Recently, Eisenbrand, Hähnle, Razborov, and Rothvoß introduced a combinatorial model for the problem which admits both of the upper bound proofs, gives rise to a superlinear lower bound. The lower bound is proved using the Lovász Local Lemma. In the talk we present this paper.

Combinatorics

Thu, 18.03.10

Anita Liebenau Cambridge University

Balog-Szemerédi-Gowers Theorem

Abstract.

The Balog-Szemerédi-Gowers theorem is a result in the field of additive combinatorics and gives a relationship between the sizes of sum sets and partial sum sets. Surprisingly, the proof is purely graph theoretical and relies on a statement about paths of length 3 in a bipartite graph. It is the object of this talk to develop this relationship as well as giving sketches of the proofs of the corresponding statements in graph theory. I will assume only basic definitions of graph theory and no previous knowledge about additive combinatorics.

Combinatorics

Fri, 12.03.10 at 12:00

Wilma Weps FU Berlin

Nonrepetitive colorings of graphs

Abstract.

Nonrepetitive coloring of graphs is a graph theoretic variant of the nonrepetitive sequences of Thue. A (in)finite sequence is called k-nonrepetitive (k ≥ 2) if it contains no k-repetition, i.e. a block B of the form B = CC...C (k-times) with C being a nonempty block. A vertex coloring f of a graph G is called nonrepetitive if each path P in G has a 2-nonrepetitive sequence f(P) of colors. Defining the Thue number of a graph to be the smallest number of colors needed for such a coloring, one is interested in estimating this graph invariant. I will present a theorem by Alon et al. proving the Thue number is bounded by the maximum degree of a graph; furthermore, a theorem by Kündgen and Pelsmajer showing the Thue number is bounded by the treewidth of a graph from above. However, for most classes of graphs the exact value of the Thue number remains unknown.

Combinatorics

Wed, 03.03.10 at 12:00

Gábor Tardos Simon Fraser University, Rényi Institute

Conflict free coloring of neighborhoods in graphs

Abstract.

A (not necessarily proper) vertex coloring of a graph is called conflict-free (with respect to the neighborhoods) if the neighborhood N(x) of any vertex x contains a vertex whose color is not repeated in N(x). We consider how many colors are needed in the worst case for conflict-free coloring of an n vertex graph. Surprisingly the answer depends very strongly on whether one considers the neighborhood N(x) to contain or exclude x itself. The results are joint with János Pach.

Combinatorics

Tue, 23.02.10 at 11:15

Heidi Gebauer ETH Zürich

Game Theoretic Ramsey Numbers

Abstract.

The Ramsey Number, R(k), is defined as the minimum N such that every 2-coloring of the edges of KN (the complete graph on N vertices) yields a monochromatic k-clique. For 60 years it is known that 2(k/2) < R(k) < 4k, and it is a widely studied open problem to find significantly better bounds. In this talk we consider a game theoretic variant of the Ramsey number: Two players, called Maker and Breaker, alternately claim an edge of KN. Maker's goal is to completely occupy a Kk and Breaker's goal is to prevent this. The game theoretic Ramsey Number R'(k) is defined as the minimum N such that Maker has a strategy to build a Kk in the game on KN. In contrast to ordinary Ramsey numbers, R'(k) has been determined precisely -- a result of Beck. We will sketch a new, weaker result about R'(k) and use it to solve some related open problems.

Combinatorics

Fri, 22.01.10 at 10:00

Andrew Treglown University of Birmingham

Hamilton cycles in directed graphs

Abstract.

Since it is unlikely that there is a characterization of all those graphs which contain a Hamilton cycle it is natural to ask for sufficient conditions which ensure Hamiltonicity. One of the most general of these is Chvátal's theorem that characterizes all those degree sequences which ensure the existence of a Hamilton cycle in a graph: Suppose that the degrees of a graph G are d1 ≤ ... ≤ dn. If n ≥ 3 and di ≥ i + 1 or dn - i ≥ n - i for all i < n/2 then G is Hamiltonian. This condition on the degree sequence is best possible in the sense that for any degree sequence violating this condition there is a corresponding graph with no Hamilton cycle. Nash-Williams conjectured a digraph analogue of Chvátal's theorem quite soon after the latter was proved. In the first part of the talk I will discuss an approximate version of this conjecture. A Hamilton decomposition of a graph or digraph G is a set of edge-disjoint Hamilton cycles which together cover all the edges of G. A conjecture of Kelly from 1968 states that every regular tournament has a Hamilton decomposition. We recently proved the following approximate version of Kelly's conjecture: Every regular tournament on n vertices contains (1/2 - o(1))n edge-disjoint Hamilton cycles. I will discuss some of our techniques as well as some related open problems in the area. This is joint work with Daniela Kühn and Deryk Osthus.

Combinatorics

Wed, 13.01.10 at 12:00

Reto Spöhel ETH Zürich

Upper bounds for asymmetric Ramsey properties of random graphs

Abstract.

Consider the following problem: Is there a coloring of the edges of the random graph Gn,p with two colors such that there is no monochromatic copy of some fixed graph F? A celebrated result by Rödl and Rucinski (1995) states a general threshold function p0(F, n) for the existence of such a coloring. Kohayakawa and Kreuter (1997) conjectured a general threshold function for the asymmetric case (where different graphs F1 and F2 are forbidden in the two colors), and verified this conjecture for the case where both graphs are cycles. Implicit in their work is the following more general statement: The conjectured threshold function is an upper bound on the actual threshold provided that i) the two graphs satisfy some balancedness condition, and ii) the so-called KŁR-Conjecture is true for the sparser of the two graphs. We present a new upper bound proof that does not depend on the KŁR-Conjecture. Together with earlier lower bound results [Marciniszyn, Skokan, S., Steger (2006)], this yields in particular a full proof of the Kohayakawa-Kreuter conjecture for the case where both graphs are cliques.

Combinatorics

Fri, 08.01.10 at 12:00

Yury Person HU Berlin

Minimum H-decompositions of graphs

Abstract.

Let φH(G) be the minimum number of graphs needed to partition the edge set of G into edges (K2) and edge-disjoint copies of H. The problem is what graph G on n vertices maximizes φH(G)? Bollobás showed that for H = Kr, r ≥ 3 the only maximizer is the Turán graph. Pikhurko and Sousa extended his result for general H with χ(H) = r ≥ 3 and proved an upper bound being tr - 1(n) + o(n2), where tr - 1(n) is the number of edges in (r - 1)-partite Turán graph on n vertices. They also conjectured that φH(G) = ex(n, H). In the talk, we verify their conjecture for odd cycles, and show that the only graph maximizing φC2l + 1(G) is the Turán graph, for large n. Joint work with Lale Özkahya.

Combinatorics

Thu, 07.01.10 at 10:15

Anna Huber MPII Saarbrücken

Performance and Robustness of Randomized Rumor Spreading Protocols

Abstract.

Randomized rumor spreading is a classical protocol to disseminate information in a network. Initially, one vertex of a finite, undirected and connected graph has some piece of information ("rumor"). In each round, every one of the informed vertices chooses one of its neighbors uniformly and independently at random and informs it. At SODA 2008, a quasirandom version of this protocol was proposed. There, each vertex has a cyclic list of its neighbors. Once a vertex has been informed, it chooses uniformly at random only one neighbor. In the following round, it informs this neighbor and in each subsequent round it informs the next neighbor from its list. I will talk about recent results on the performance and robustness of these two protocols, in particular about the runtime on random graphs and about the robustness on the complete graph.

Combinatorics

Wed, 06.01.10 at 12:00

Wojciech Samotij University of Illinois at Urbana-Champaign

Counting graphs without a fixed complete bipartite subgraph

Abstract.

A graph is called H-free if it contains no copy of H. Denote by fn(H) the number of (labeled) H-free graphs on n vertices. Since every subgraph of an H-free graph is also H-free, it immediately follows that fn(H) ≥ 2ex(n, H). Erdős conjectured that, provided H contains a cycle, this trivial lower bound is in fact tight, i.e. fn(H) = 2(1 + o(1))ex(n, H). The conjecture was resolved in the affirmative for graphs with chromatic number at least 3 by Erdős, Frankl and Rödl (1986), but the case when H is bipartite remains wide open. We will give an overview of the known results in case χ(H) = 2 and present our recent contributions to the study of H-free graphs. This is joint work with Jozsef Balogh (University of California, San Diego).

Combinatorics

Fri, 11.12.09 at 14:15

Michael Krivelevich Tel Aviv University

Intelligence vs Randomness: the power of choices

Abstract.

Consider the following very standard experiment: n balls are thrown independently at random each into n bins (if you are practically inclined, think about distributing n jobs at random between n machines). It is quite easy to see that the maximum load over all bins will be almost surely about ln n/lnln n. If however each ball is allowed to choose between two randomly drawn bins, the typical maximum bin load drops dramatically to about lnln n, as shown in a seminal paper of Azar, Broder, Karlin and Upfal from 1994 - an exponential improvement! The above described result is just one manifestation of a recently widely studied phenomenon, where a limited manipulation of the otherwise truly random input is capable to advance significantly various goals. In this talk I will describe results of this type, mainly focusing on the so called controlled random graph processes, where at each stage an algorithm is presented with a collection of randomly drawn edges and is allowed to manipulate this collection in a certain predefined way. Models to be defined and discussed include the Achlioptas process and Ramsey-type games on random graphs.

Combinatorics

Thu, 26.11.09 at 10:15

Angelika Steger ETH Zürich

A deletion method for local subgraph counts

Abstract.

For a given graph H let X denote the random variable that counts the number of copies of H in a random graph. For subgraph counts one can use Janson’s inequality to obtain upper bounds on the probability that X is smaller than its expectation. For the corresponding upper tail, however, such bounds are not obtained easily and are known to not hold with similarly small probabilities. In this talk we thus consider the following variation of the problem: we want to find a subgraph that on the one hand still contains at roughly E[X] many H-subgraphs, and on the other hand has the property that every vertex (and more generally every small subset of vertices) is contained in ‘not too many‘ H-subgraphs. This is joint work with Reto Spöhel and Lutz Warnke.

Combinatorics

Fri, 20.11.09 at 12:00

Roman Glebov FU Berlin

Extremal Graphs for Clique-Paths

Abstract.

In this talk, we deal with a Turán-type problem: given a positive integer n and a forbidden graph H, how many edges can there be in a graph on n vertices without a subgraph H? And how does a graph look like, if it has this extremal edge number? The forbidden graph in this talk is a clique-path, that is an k-path, where each edge is blown up to an r-clique, r ≥ 3. We determine both the extremal number and the extremal graph for sufficiently large n.

Combinatorics

Mon, 09.11.09 at 10:15

Philipp Zumstein ETH Zürich

Polychromatic Colorings of Plane Graphs

Abstract.

A vertex k-coloring of a plane graph G is called polychromatic if in every face of G all k colors appear. Let p(G) be the maximum number k for which there is a polychromatic k-coloring. For a plane graph G, let g(G) denote the length of the shortest face in G. We show p(G) ≥ (3g(G) - 5)/4 for every plane graph G and on the other hand for each g we construct a plane graph H with g(H) = g and p(H) ≤ (3g + 1)/4. Furthermore, we show that the problem of determining whether a plane graph admits a vertex coloring by 3 colors in which all colors appear in every face is NP-complete, even for graphs in which all faces are of length 3 or 4 only. The investigation of this problem is motivated by its connection to a variant of the art gallery problem in computational geometry. Joint work with Noga Alon, Robert Berke, Kevin Buchin, Maike Buchin, Peter Csorba, Saswata Shannigrahi, and Bettina Speckmann.

Combinatorics

Mon, 26.10.09 at 10:15

Dominik Scheder ETH Zürich

Deterministic Local Search for 3-SAT

Abstract.

In an attempt to derandomize Schoening's famous algorithm for k-SAT, Dantsin et al. proposed a deterministic k-SAT algorithm based on covering codes and deterministic local search. The deterministic local search procedure was subsequently improved by several authors. I will present the main ideas behind the algorithm and the latest improvements, one of them by myself. At the heart of my improvement is the idea that recursive search-trees can sometimes be Copy-Pasted to save time.

Combinatorics

Fri, 23.10.09 at 12:00

Tomislav Doslic University of Zagreb

Computing the bipartite edge frustration of some classes of graphs

Abstract.

The bipartite edge frustration of a graph is defined as the smallest number of edges that have to be deleted from the graph in order to obtain a bipartite spanning subgraph. The quantity is, in general, difficult to compute; however it can be efficiently computed for certain classes of graphs. I will speak about computing the bipartite edge frustration of some planar graphs, in particular fullerenes, and of some composite graphs.

Combinatorics

Fri, 16.10.09 at 12:00

Tibor Szabó FU Berlin

Minimum degree of minimal ramsey graphs

Abstract.

A graph G is called H-Ramsey if any two-coloring of the edges of G contains a monochromatic copy of H. An H-Ramsey graph is called H-minimal if no proper subgraph of it is H-Ramsey. We investigate the minimum degree of H-minimal graphs, a problem initiated by Burr, Erdős, and Lovász. We determine the smallest possible minimum degree of H-minimal graphs for numerous bipartite graphs H, including bi-regular bipartite graphs and forests. We also make initial progress for graphs of larger chromatic number.

Research Seminar Combinatorics 📅