List of upcoming online seminars in discrete mathematics, combinatorics, and graph theory

by Cosmin Pohoata (IAS School of Math) as part of Copenhagen-Jerusalem Combinatorics Seminar

Interactive livestream: https://ucph-ku.zoom.us/j/69937085835?pwd=S3J6UjQ0eFVPOU1hRUdCMHRnYXozUT09
Abstract: TBA

Title: Strengthening Hadwiger’s conjecture for 4- and 5-chromatic graphs
by Raphael Steiner (ETH Zürich) as part of IBS/KAIST Discrete Math Seminar

View-only livestream: https://www.youtube.com/c/ibsdimag
Lecture held in Room B232, IBS.
Abstract: TBA

Title: Treewidth, Circle Graphs and Circular Drawings
by Robert Hickingbotham (Monash University) as part of IBS Virtual Discrete Math Colloquium

Abstract: TBA

We introduce the following submodular generalization of the Shortest Cycle problem. For a nonnegative monotone submodular cost function $f$ defined on the vertices (or, equivalently, the edges) of an undirected graph $G$, we seek for a cycle $C$ in $G$ of minimum cost $Opt=f(C)$. We construct an algorithm that, given an $n$-vertex graph $G$, parameter $ε > 0$, and the function $f$ represented by an oracle, in time $n^{O(\log 1/ε)}$ finds a cycle $C$ in $G$ with $f(C)\leq (1+ε)Opt$. This is in sharp contrast with the non-approximability of the closely related Monotone Submodular Shortest $(s,t)$-Path problem, which requires exponentially many queries to the oracle for finding an $n^{2/3-ε}$-approximation [Goel et al., FOCS 2009]. When the function $f$ is integer-valued, our algorithm yields that a cycle of cost $Opt$ can be found in time $n^{O(\log Opt)}$. In particular, for $Opt=n^{O(1)}$ this gives a quasipolynomial-time algorithm computing a cycle of minimum submodular cost.

Joint work with: Fedor V. Fomin, Tuukka Korhonen, Daniel Lokshtanov, and Giannos Stamoulis

by Geunho Lim (University of California, Santa Barbara) as part of Copenhagen-Jerusalem Combinatorics Seminar

Interactive livestream: https://ucph-ku.zoom.us/j/69937085835?pwd=S3J6UjQ0eFVPOU1hRUdCMHRnYXozUT09
Abstract: TBA

Title: Fixed-Parameter Tractability of Directed Multicut with Three Terminal Pairs Parametrised by the Size of the Cutset: Twin-Width Meets Flow-Augmentation
by Meike Hatzel (National Institute of Informatics) as part of IBS/KAIST Discrete Math Seminar

View-only livestream: https://www.youtube.com/c/ibsdimag
Lecture held in Room B232, IBS.
Abstract: TBA

by Daniel Altman (University of Oxford) as part of IBS Virtual Discrete Math Colloquium

Abstract: TBA

by Stephanie Mui (NYU Courant) as part of Copenhagen-Jerusalem Combinatorics Seminar

Interactive livestream: https://ucph-ku.zoom.us/j/69937085835?pwd=S3J6UjQ0eFVPOU1hRUdCMHRnYXozUT09
Abstract: TBA

by Fabio Alejandro Calderón Mateus (Universidad Nacional de Colombia) as part of Copenhagen-Jerusalem Combinatorics Seminar

Interactive livestream: https://ucph-ku.zoom.us/j/69937085835?pwd=S3J6UjQ0eFVPOU1hRUdCMHRnYXozUT09
Abstract: TBA

Title: Recent progress on the Union-closed conjecture and related
by Stijn Cambie (IBS Extremal Combinatorics and Probability Group) as part of IBS/KAIST Discrete Math Seminar

View-only livestream: https://www.youtube.com/c/ibsdimag
Lecture held in Room B232, IBS.
Abstract: TBA

The //disjoint paths logic//, FOL+DP, is an extension of First Order Logic (FOL) with the extra atomic predicate dp$_k(x_1,y_1,\ldots,x_k,y_k),$ expressing the existence of internally vertex-disjoint paths between $x_i$ and $y_i,$ for $i\in \{1,\ldots, k\}$. This logic can express a wide variety of problems that escape the expressibility potential of FOL. We prove that for every minor-closed graph class, model-checking for FOL+DP can be done in quadratic time. We also introduce an extension of FOL+DP, namely the //scattered disjoint paths logic//, FOL+SDP, where we further consider the atomic predicate $s$-sdp$_k(x_1,y_1,\ldots,x_k,y_k),$ demanding that the disjoint paths are within distance bigger than some fixed value $s$. Using the same technique we prove that model-checking for FOL+SDP can be done in quadratic time on classes of graphs with bounded Euler genus.

Joint work with Petr Golovach and Dimitrios M. Thilikos

by István Tomon (Umeå University) as part of Copenhagen-Jerusalem Combinatorics Seminar

Interactive livestream: https://ucph-ku.zoom.us/j/69937085835?pwd=S3J6UjQ0eFVPOU1hRUdCMHRnYXozUT09
Abstract: TBA

by Eunjin Oh (POSTECH) as part of IBS/KAIST Discrete Math Seminar

View-only livestream: https://www.youtube.com/c/ibsdimag
Lecture held in Room B232, IBS.
Abstract: TBA

by Marcelo Sales (Emory University) as part of IBS Virtual Discrete Math Colloquium

Abstract: TBA

by Meghana M. Reddy (ETH Zürich) as part of Copenhagen-Jerusalem Combinatorics Seminar

Interactive livestream: https://ucph-ku.zoom.us/j/69937085835?pwd=S3J6UjQ0eFVPOU1hRUdCMHRnYXozUT09
Abstract: TBA

by Rosna Paul (Graz University of Technology) as part of Copenhagen-Jerusalem Combinatorics Seminar

Interactive livestream: https://ucph-ku.zoom.us/j/69937085835?pwd=S3J6UjQ0eFVPOU1hRUdCMHRnYXozUT09
Abstract: TBA

by Qizhong Lin (Fuzhou University) as part of IBS Virtual Discrete Math Colloquium

Abstract: TBA

Title: Configurations of boxes
by István Tomon (Umeå universitet) as part of IBS/KAIST Discrete Math Seminar

View-only livestream: https://www.youtube.com/c/ibsdimag
Lecture held in Room B232, IBS.
Abstract: TBA

by Jie Han (Beijing Institute of Technology) as part of IBS Virtual Discrete Math Colloquium

Abstract: TBA

by Maria Chudnovsky (Princeton University) as part of IBS/KAIST Discrete Math Seminar

View-only livestream: https://www.youtube.com/c/ibsdimag
Lecture held in Room B232, IBS.
Abstract: TBA

by Oliver Janzer (University of Cambridge) as part of IBS/KAIST Discrete Math Seminar

View-only livestream: https://www.youtube.com/c/ibsdimag
Lecture held in Room B232, IBS.
Abstract: TBA