seminar Archives - Page 10 of 32 - Discrete Mathematics Group

February 2, 2023July 6, 2024

Benjamin Bergougnoux gave an online talk on proving tight lower bounds for the running time of various problems parameterized by rank-width at the Virtual Discrete Math Colloquium

On February 1, 2023, Benjamin Bergougnoux from the University of Warsaw gave an online talk at the Virtual Discrete Math Colloquium about proving tight lower bounds for the running time of various problems parameterized by rank-width. The title of his talk was “Tight Lower Bounds for Problems Parameterized by Rank-width“.

February 2, 2023July 6, 2024

Abhishek Methuku gave a talk on the resolution of the Erdős-Faber-Lovász conjecture at the Discrete Math Seminar

On January 31, 2023, Abhishek Methuku from ETH Zürich gave a talk at the Discrete Math Seminar on the resolution of the Erdős-Faber-Lovász conjecture for all large instances. The title of his talk was “A proof of the Erdős–Faber–Lovász conjecture“. Abhishek Methuku was a former member of the IBS Discrete Mathematics Group in 2019-2020.

January 21, 2023July 6, 2024

Pedro Montealegre gave an online talk on a proof labeling scheme certifying that the graph has tree-width at most k and satisfies a monadic second-order property with certificates of small size at each vertex at the Virtual Discrete Math Colloquium

On January 19, 2023, Pedro Montealegre from Universidad Adolfo Ibáñez gave an online talk at the Virtual Discrete Math Colloquium on a proof labeling scheme certifying that a graph has tree-width at most k and satisfies a monadic second-order property with a certificate of small size at each vertex. The title of his talk was “A Meta-Theorem for Distributed Certification“.

January 20, 2023July 6, 2024

Noleen Köhler gave a talk on classes of graphs on which the parameterized complexity of the FO model checking on their subclasses can be explained by the twin-width at the Discrete Math Seminar

On January 17, 2023, Noleen Köhler from the LAMSADE, CNRS gave a talk at the Discrete Math Seminar on classes of graphs on which the first order model checking is FPT on its subclass if and only if the twin-width is bounded. The title of her talk was “Twin-Width VIII: Delineation and Win-Wins“.

January 11, 2023July 6, 2024

Mamadou Moustapha Kanté gave a talk on the recognizability and the MSO definability of a class of matroids having the strongly pigeonhole property at the Discrete Math Seminar

On January 10, 2023, Mamadou Moustapha Kanté from the Université Clermont Auvergne gave a talk at the Discrete Math Seminar on the recognizability and the MSO definability for classes of matroids of bounded path-width having the strongly pigeonhole property. The title of his talk was “MSOL-Definable decompositions“.

January 3, 2023July 6, 2024

Youngho Yoo gave a talk on the approximation algorithm for the traveling salesman problem on cubic graphs at the Discrete Math Seminar

On January 3, 2023, Youngho Yoo from Texas A&M University gave a talk at the Discrete Math Seminar on the approximation algorithm for the traveling salesman problem on cubic graphs by showing an upper bound on the length of a shortest closed spanning walk in a simple 2-connected subcubic graph. The title of his talk was “Approximating TSP walks in subcubic graphs“.

January 2, 2023July 6, 2024

Stijn Cambie gave a talk on the number of maximal independent sets at the Discrete Math Seminar

On December 28, 2022, Stijn Cambie from the IBS Extremal Combinatorics and Probability Group gave a talk at the Discrete Math Seminar on various problems on the number of independent sets, including the problem of finding a graph with a given number of independent sets of fixed size. The title of his talk was “The 69-conjecture and more surprises on the number of independent sets“.

December 11, 2022July 6, 2024

Giannos Stamoulis gave a talk on the model checking for first-order logic extended with disjoint paths predicates in H-minor-free graphs at the Discrete Math Seminar

On December 6, 2022, Giannos Stamoulis from Université de Montpellier gave at the Discrete Math Seminar on a fixed-parameter tractable algorithm for the model checking for the first-order logic extended with disjoint paths predicates in H-minor-free graphs. The title of his talk was “Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes“.

November 22, 2022July 6, 2024

Seonghyuk Im (임성혁) gave a talk on the resolution of the Elliott-Rödl conjecture on embedding hypertrees in a Steiner triple system at the Discrete Math Seminar

On November 22, 2022, Seonghyuk Im (임성혁) from KAIST and the IBS Extremal Combinatorics and Probability Group gave a talk at the Discrete Math Seminar on the resolution of the Elliott-Rödl conjecture on embedding hypertrees in a Steiner triple system . The title of his talk was “A proof of the Elliott-Rödl conjecture on hypertrees in Steiner triple systems.”

November 16, 2022July 6, 2024

Sebastian Wiederrecht gave a talk on the structure of graphs without certain matching minors and its applications in counting perfect matchings and computing permanents at the Discrete Math Seminar

On November 15, 2022, Sebastian Wiederrecht from the IBS Discrete Mathematics Group gave a talk at the Discrete Math Seminar on the structure of graphs without certain matching minors and its applications in counting perfect matchings and computing permanent. The title of his talk was “Excluding single-crossing matching minors in bipartite graphs“.

Category: seminar