[Facets-of-complexity] Invitation and link to Monday Lecture - January 4th 2021 - online via zoom

[Ita Brunke <i.brunke@inf.fu-berlin.de>]

You are cordially invited to our next Monday Lecture - in the New Year. Next Monday Lecture, there will be again the hearing of our PhD candidates.

We will have three talks. Talks will be 30 min. 15 min discussions, 15 min break.
All Monday Lectures and Colloquia of winter term 2020/21 will be given online via zoom.

You may find valid Invitation for zoom throughout all winter term here:
http://www.facetsofcomplexity.de/monday/WS-2020-21/index.html

Invitation link:
https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09

Monday Lecture will be on January 4th 2021 at 14:00 h, 15:00, 16:00.

Online via:
Zoom - Invitation

Time: Monday, January 4th - 14:00 h

Lecture: Sampada Kolhatkar

Title: Bivariate chromatic polynomials of mixed graphs

Abstract:

For a graph G=(V,E), the chromatic polynomial X_G counts the number of vertex colourings as a function of number of colours. Stanley’s reciprocity theorem connects the chromatic polynomial with the enumeration of acyclic orientations of G. One way to prove the reciprocity result is via the decomposition of chromatic polynomials as the sum of order polynomials over all acyclic orientations. From the Discrete Geometry perspective, the decomposition is as the sum of Ehrhart polynomials through real braid arrangement. Beck, Bogart, and Pham proved the analogue of this reciprocity theorem for the strong chromatic polynomials for mixed graph. Dohmen–Pönitz–Tittmann provided a new two variable generalization of the chromatic polynomial for undirected graphs. We extend this bivariate chromatic polynomial to mixed graphs, provide a deletion-contraction like formula and study the colouring function geometrically via hyperplane arrangements.

Time: Monday, January 4th - 15:00 h

Lecture: Alp Müyesser

Title: Rainbow factors and trees

Abstract:

Generalizing a conjecture of Aharoni, Joos and Kim asked the following intriguing question. Let H be a graph on m edges, and let G_i (1<=i<=m) be a sequence of m graphs on the common vertex set [n]. What is the weakest minimum degree restriction we can impose on each G_i to guarantee a rainbow copy of H? Joos and Kim answered this question when H is a Hamilton cycle or a perfect matching. We provide an asymptotic answer when H is an F-factor, or a spanning tree with maximum degree o(n/log n). This is joint work with Richard Montgomery and Yani Pehova.

Time: Monday, January 4th - 16:00 h

Lecture: Shubhang Mittal

Title: tba

Abstract:

tba