IBS/KAIST Joint Discrete Math Seminar

IBS Discrete Mathematics Group, Daejeon

Seminar series on discrete mathematics @ Dept. of Mathematical Sciences, KAIST.

IBS/KAIST Joint Discrete Math Seminar

The minimum connectivity forcing forest minors in large graphs

Kevin Hendrey

IBS Discrete Mathematics Group, Daejeon

IBS Discrete Mathematics Group, Daejeon

2019/09/10 Tue 4:30PM-5:30PM

Given a graph $G$, we define $\textrm{ex}_c(G)$ to be the minimum value of $t$ for which there exists a constant $N(t,G)$ such that every $t$-connected graph with at least $N(t,G)$ vertices contains $G$ as a minor. The value of $\textrm{ex}_c(G)$ is known to be tied to the vertex cover number $\tau(G)$, and in fact $\tau(G)\leq \textrm{ex}_c(G)\leq \frac{31}{2}(\tau(G)+1)$. We give the precise value of $\textrm{ex}_c(G)$ when $G$ is a forest. In particular we find that $\textrm{ex}_c(G)\leq \tau(G)+2$ in this setting, which is tight for infinitely many forests.

2019 IBS Summer Research Program on Algorithms and Complexity in Discrete Structures

Website: https://dimag.ibs.re.kr/event/2019-ibs-summer-research-program/

Room B232, IBS (기초과학연구원)

10:00-11:00 Introduction

11:00-12:00 Open Problems

11:00-10:30 **Stefan Kratsch**, Humboldt-Universität zu Berlin, Germany

*Elimination Distances, Blocking Sets, and Kernels for Vertex Cover*

10:45-11:15 **Benjamin Bergougnoux**, University Clermont Auvergne, France

*More applications of the d-neighbor equivalence*

11:30-12:00 **Yixin Cao**, Hong Kong Polytechnic University, China

*Enumerating Maximal Induced Subgraphs*

(We will go to KAIST for June Huh‘s two talks 15:00-16:00, 16:30-17:30.)

10:00-11:00 **Nick Brettell**, Eindhoven University of Technology, Netherlands

*Recent work on characterising matroids representable over finite fields*

11:30-12:00 **Mamadou M. Kanté**, University Clermont Auvergne, France

*On recognising k-letter graphs*

10:00-11:00 **O-joung Kwon (권오정)**, Incheon National University, Korea

*The grid theorem for vertex-minors*

11:00-12:00 **Progress Report**

8:30 Excursion to Damyang (departure from the accommodation)

10:00-11:00 **Archontia Giannopoulou**, National and Kapodistrian University of Athens, Greece

*The directed flat wall theorem*

11:30-12:00 **Eunjung Kim (김은정)**, LAMSADE-CNRS, France

*Subcubic even-hole-free graphs have a constant treewidth*

10:00-11:00 **Pierre Aboulker**, ENS Ulm, France

*Generalizations of the geometric de Bruijn Erdős Theorem*

11:30-12:00 **Michael Dobbins**, Binghamton University, USA

*Barycenters of points in polytope skeleta*

10:00-11:00 **Magnus Wahlström**, Royal Holloway, University of London, UK

*T.B.A.*

11:30-12:00 **Édouard Bonnet**, ENS Lyon, France

*The FPT/W[1]-hard dichotomy of Max Independent Set in H-free graphs*

10:00-11:00 **Euiwoong Lee (이의웅)**, NYU, USA

* Losing treewidth by separating subsets*

11:30-12:00 **Sang-il Oum (엄상일)**, IBS Discrete Mathematics Group and KAIST, Korea

*Branch-depth: Generalizing tree-depth of graphs*

10:00-11:00 **Dabeen Lee (이다빈)**, IBS Discrete Mathematics Group, Korea

*t-perfect graphs and the stable set problem*

11:00-12:00 **Progress Report**

*August 5-9: Free Discussions / Research Collaborations / Progress Report*

*Tea time: Every weekday 3:30pm*

IBS/KAIST Joint Discrete Math Seminar

The genus of a random graph and the fragile genus property

Mihyun Kang (강미현)

TU Graz

TU Graz

2019/08/20 Tue 4:30PM-5:30PM

In this talk we shall discuss how quickly the genus of the Erdős-Rényi random graph grows as the number of edges increases and how dramatically a small number of random edges can increase the genus of a randomly perturbed graph. (Joint work with Chris Dowden and Michael Krivelevich)

IBS/KAIST Joint Discrete Math Seminar

Integrality of set covering polyhedra and clutter minors

Dabeen Lee (이다빈)

IBS Discrete Mathematics Group

IBS Discrete Mathematics Group

2019/07/16 Tue 4:30PM-5:30PM

Given a finite set of elements $V$ and a family $\mathcal{C}$ of subsets of $V$, the set covering problem is to find a minimum cardinality subset of $V$ intersecting every subset in the family $\mathcal{C}$. The set covering problem, also known as the hitting set problem, admits a simple integer linear programming formulation. The constraint system of the integer linear programming formulation defines a polyhedron, and we call it the set covering polyhedron of $\mathcal{C}$. We say that a set covering polyhedron is integral if every extreme point is an integer lattice point. Although the set covering problem is NP-hard in general, conditions under which the problem becomes polynomially solvable have been studied. If the set covering polyhedron is integral, then it is straightforward that the problem can be solved using a polynomial-time algorithm for linear programming.

In this talk, we will focus on the question of when the set covering polyhedron is integral. We say that the family $\mathcal{C}$ is a clutter if every subset in $\mathcal{C}$ is inclusion-wise minimal. As taking out non-minimal subsets preserves integrality, we may assume that $\mathcal{C}$ is a clutter. We call $\mathcal{C}$ ideal if the set covering polyhedron of it is integral. To understand when a clutter is ideal, the notion of clutter minors is important in that $\mathcal{C}$ is ideal if and only if so is every minor of it. We will study two fundamental classes of non-ideal clutters, namely, deltas and the blockers of extended odd holes. We will characterize when a clutter contains either a delta or the blocker of an extended odd hole as a minor.

This talk is based on joint works with Ahmad Abdi and G\’erard Cornu\’ejols.

IBS/KAIST Joint Discrete Math Seminar

A model theoretical approach to sparsity

Patrice Ossona de Mendez

CNRS, France

CNRS, France

2019/06/25 Tue 4:30PM-5:30PM

We discuss how the model theoretic notion of first-order transduction allows to define a notion of structural sparsity, and give some example of applications, like existence of low shrub-depth decompositions for tranductions of bounded expansion classes, characterization of transductions of classes with bounded pathwidth, decompositions of graphs with bounded rank-width into cographs.