Mamadou Moustapha Kanté, MSOL-Definable decompositions
I will first introduce the notion of recognisability of languages of terms and then its extensions to sets of relational structures. In a second step, I will discuss relations with …
10 events found.
Events
-
-
Room B332 IBS (기초과학연구원)
-
Noleen Köhler, Twin-Width VIII: Delineation and Win-Wins
Room B332 IBS (기초과학연구원)We introduce the notion of delineation. A graph class $\mathcal C$ is said delineated by twin-width (or simply, delineated) if for every hereditary closure $\mathcal D$ of a subclass of …
-
Pedro Montealegre, A Meta-Theorem for Distributed Certification
Zoom ID: 869 4632 6610 (ibsdimag)Distributed certification, whether it be proof-labeling schemes, locally checkable proofs, etc., deals with the issue of certifying the legality of a distributed system with respect to a given boolean predicate. A certificate …
-
Jan Hladký, Invitation to graphons
Zoom ID: 224 221 2686 (ibsecopro)The first course in graph theory usually covers concepts such as matchings, independent sets, colourings, and forbidden subgraphs. Around 2004, Borgs, Chayes, Lovász, Sós, Szegedy, and Vestergombi introduced a very …
-
Abhishek Methuku, A proof of the Erdős–Faber–Lovász conjecture
Room B332 IBS (기초과학연구원)The Erdős–Faber–Lovász conjecture (posed in 1972) states that the chromatic index of any linear hypergraph on n vertices is at most n. In this talk, I will sketch a proof …
-
-
Benjamin Bergougnoux, Tight Lower Bounds for Problems Parameterized by Rank-width
Zoom ID: 869 4632 6610 (ibsdimag)We show that there is no $2^{o(k^2)} n^{O(1)}$ time algorithm for Independent Set on $n$-vertex graphs with rank-width $k$, unless the Exponential Time Hypothesis (ETH) fails. Our lower bound matches …
-
Raphael Steiner, Strengthening Hadwiger’s conjecture for 4- and 5-chromatic graphs
Room B332 IBS (기초과학연구원)Hadwiger's famous coloring conjecture states that every t-chromatic graph contains a $K_t$-minor. Holroyd conjectured the following strengthening of Hadwiger's conjecture: If G is a t-chromatic graph and S⊆V(G) takes all …
-
Robert Hickingbotham, Treewidth, Circle Graphs and Circular Drawings
Zoom ID: 869 4632 6610 (ibsdimag)A circle graph is an intersection graph of a set of chords of a circle. In this talk, I will describe the unavoidable induced subgraphs of circle graphs with large …
-
Meike Hatzel, Fixed-Parameter Tractability of Directed Multicut with Three Terminal Pairs Parametrised by the Size of the Cutset: Twin-Width Meets Flow-Augmentation
Room B332 IBS (기초과학연구원)We show fixed-parameter tractability of the Directed Multicut problem with three terminal pairs (with a randomized algorithm). This problem, given a directed graph $G$, pairs of vertices (called terminals) $(s_1,t_1)$, …
-
Daniel Altman, On an arithmetic Sidorenko conjecture, and a question of Alon
Zoom ID: 224 221 2686 (ibsecopro)Let $G=\mathbb{F}_p^n$. Which systems of linear equations $\Psi$ have the property that amongst all subsets of $G$ of fixed density, random subsets minimise the number of solutions to $\Psi$? This …