Springe direkt zu Inhalt

Research Seminar Combinatorics

Next Talk

Thursday, November 26th, 2020 at 16:15
Webex Meeting Number: 121 729 0339
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.

<iframe src="https://calendar.google.com/calendar/embed?mode=agenda&height=600&wkst=1&bgcolor=%23FFFFFF&src=dq5vbd4jmriuttn2k4c12s228c%40group.calendar.google.com&color=%23711616&ctz=Europe%2FBerlin" style="border-width:0" width="800" height="350" frameborder="0" scrolling="no"></iframe>

Google Calendar

Schedule and abstracts 2020/2021

DateSpeakerTitle
02.12.2020 Ander Lamaison
(Masaryk University Brno)
TBA
26.11.2020 Anurag Bishnoi
(TU Delft)
Lower bounds for diagonal Ramsey numbers
18.11.2020 Raphael Steiner
(TU Berlin)
Disjoint cycles of distinct lengths in directed graphs of large connectivity or large minimum degree
12.11.2020 Tibor Szabó
(FU Berlin)
Mader-perfect digraphs
04.11.2020 Alp Müyesser
(FU Berlin)
A rainbow version of Hajnal-Szemerédi Theorem
02.12.2020
Ander Lamaison (Masaryk University Brno)
TBA

Abstract: tba

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

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

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

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


Links

Mailing list:

To subscribe to the mailing-list of the seminar, please follow this link:
https://lists.fu-berlin.de/listinfo/combinatorics-seminar

Seminar calendar:

To add the .ics file of the calendar to your favorite calendar reader (that supports the ICal format), please follow this link:
ICal calendar.

To add the calendar feeds to your favorite feed reader, please follow this link:
Calendar feeds.

Notes:

For any request, please send an e-mail to:
combinatorics-seminar-owner@lists.fu-berlin.de

Archives

Schedule and abstracts 2019/2020

Schedule and abstracts 2018/2019

Schedule and abstracts 2017/2018

Schedule and abstracts 2016/2017

Schedule and abstracts 2015/2016

Schedule and abstracts 2014/2015

Schedule and abstracts 2013/2014

Schedule and abstracts 2012/2013

Schedule and abstracts 2011/2012

Schedule and abstracts 2010/2011

Schedule and abstracts 2009/2010