The Logo and Seal of the Freie Universität BerlinFreie Universität Berlin

Department of Mathematics and Computer Science


Service Navigation

  • Homepage
  • Imprint
  • Privacy Policy
EN
  • DE: Deutsch
  • EN: English
Quick access
spinner
Information about data transfer when using Google Search™
Department of Mathematics and Computer Science/Mathematics/

Combinatorics and Graph Theory

Menu
  • People

    loading...

  • Alumni

    loading...

  • Guests

    loading...

  • Teaching

    loading...

  • Research Seminar

    loading...

  • Publications

    loading...

  • Events

    loading...

  • News

    loading...

Breadcrumbs Navigation

  • Homepage
  • Mathematics
  • Workgroups
  • Combinatorics and Graph Theory
  • Research Seminar
  • 2018/2019

2018/2019

Talks take place from 16:15 at 

Königin-Luise-Str. 24 / 26, 14195 Berlin, room SR 006, on Wednesdays, and
Arnimallee 7, 14195 Berlin, room SR E.31, on Thursdays.

DateSpeakerTitle
21.02.2019

Jan van den Heuvel
(LSE)

Partial solutions to Hadwiger's Conjecture
13.02.2019

Ferdinand Ihringer
(Ghent University)

Rank Bounds on the Independence Number

06.02.2019

David Fabian
(FU Berlin)

Rainbow arithmetic progressions and anti-van der Waerden numbers

30.01.2019

László Kozma
(FU Berlin)

Hamiltonicity below Dirac's condition

23.01.2019

Anurag Bishnoi
(FU Berlin)

Non-intersecting Ryser hypergraphs

16.01.2019

Jan Corsten
(LSE)

Erdős-Rothschild problem for five and six colours

09.01.2019

Péter Pál Pach
(BME)

Polynomial Schur's theorem

19.12.2018

Christoph Spiegel
(UPC)

Intervals in the Hales-Jewett Theorem

12.12.2018

Jozef Skokan
(LSE)

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

05.12.2018

Alexandra Wesolek
(FU Berlin)

Bootstrap percolation in Ore-type graphs

29.11.2018

Hong Liu
(Warwick)

Enumeration in arithmetic setting

28.11.2018

Andrew Newman
(TU Berlin)

Small simplicial complexes with large torsion in homology

21.11.2018

Sophia Elia
(FU Berlin)

A comparison of Quotient Posets

07.11.2018

Patrick Morris
(FU Berlin)

On the discrepancy of permutation families

31.10.2018

Tamás Mészáros
(FU Berlin)

Sample compression schemes

24.10.2018 Roman Glebov
(Ben Gurion University)

Perfect Matchings in Random Subgraphs of Regular Bipartite Graphs

21.02.2019
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?

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

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

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

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

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

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

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

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


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

29.11.2018
Hong Lius (Warwick)
Enumeration in arithmetic setting

Abstract: I will discuss several recent extremal results on enumerating subsets of integers/groups with various additive and multiplicative constraints.

28.11.2018
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? 

21.11.2018
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 n elements. Stanley showed that |Hom(P,n)| is given by a polynomial in n. 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 n using quotient posets. We touch on an alternative approach to the proof through the Ehrhart theory of order polytopes.

31.10.2018
Patrick Morris (FU Berlin)
On the discrepancy of permutation families

Abstract: For a set family S⊆ 2n, the discrepancy of S is 

disc(S):=minχ:[n]→±1 maxS∈ S |∑x∈S χ(x)|.

One can think of this as a colouring problem. Given a set system, we are interested in colouring the ground set red/blue such that in every set the difference between the number of red and number of blue points is as small as possible. Given a set of permutations π1,...,πk on [n], we can define a set family S(π1,...,πk) by taking all sets that occur as intervals in each of the permutations. Formally, 

S(π1,...,πk):={ {πj(x),πj(x+1),...,πj(y)} : 1≤x≤y≤n, j∈[k] }.

How large can the discrepancy of such a family be?

It turns out that for any n∈ ℕ and two permutations, π,σ on [n], we have that disc(S(π,σ))≤ 2. What about three permutations?  Beck conjectured (around 1987) that this should also be bounded by a constant. In 2009, Matoušek described this as ``one of the most tantalising questions in combinatorial discrepancy". In this talk, we will present the eventual resolution of this conjecture by Newman and Nikolov in 2011. The talk will end with an invitation to an open problem. 


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

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




News

spinner

Service Navigation

  • Homepage
  • Imprint
  • Privacy Policy

This Page

  • Print
  • Subscribe RSS-Feed
  • Deutsch