Abhishek Methuku, A proof of the Erdős–Faber–Lovász conjecture
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 …
10 events found.
Discrete Math Seminar
Events
-
-
Room B332 IBS (기초과학연구원)
-
-
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 …
-
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)$, …
-
Maya Sankar, The Turán Numbers of Homeomorphs
Room B332 IBS (기초과학연구원)Let $X$ be a 2-dimensional simplicial complex. Denote by $\text{ex}_{\hom}(n,X)$ the maximum number of 2-simplices in an $n$-vertex simplicial complex that has no sub-simplicial complex homeomorphic to $X$. The asymptotics …
-
-
Eunjin Oh (오은진), Parameterized algorithms for the planar disjoint paths problem
Room B332 IBS (기초과학연구원)Given an undirected planar graph $G$ with $n$ vertices and a set $T$ of $k$ pairs $(s_i,t_i)_{i=1}^k$ of vertices, the goal of the planar disjoint paths problem is to find …
-
Stijn Cambie, Recent progress on the Union-closed conjecture and related
Room B332 IBS (기초과학연구원)We give a summary on the work of the last months related to Frankl's Union-Closed conjecture and its offsprings. The initial conjecture is stated as a theorem in extremal set …
-
Younjin Kim (김연진), Problems on Extremal Combinatorics
Room B332 IBS (기초과학연구원)Extremal Combinatorics studies the maximum or minimum size of finite objects (numbers, sets, graphs) satisfying certain properties. In this talk, I introduce the conjectures I solved on Extremal Combinatorics, and …
-
Tianchi Yang, On the maximum number of edges in k-critical graphs
Room B332 IBS (기초과학연구원)In this talk, we will discuss the problem of determining the maximum number of edges in an n-vertex k-critical graph. A graph is considered k-critical if its chromatic number is …
-
-
István Tomon, Configurations of boxes
Room B332 IBS (기초과학연구원)Configurations of axis-parallel boxes in $\mathbb{R}^d$ are extensively studied in combinatorial geometry. Despite their perceived simplicity, there are many problems involving their structure that are not well understood. I will …
-
James Davies, Two structural results for pivot-minors
Room B332 IBS (기초과학연구원)Pivot-minors can be thought of as a dense analogue of graph minors. We shall discuss pivot-minors and two recent results for proper pivot-minor-closed classes of graphs. In particular, that for …