Archive for the ‘2019’ Category

« Older Entries
Newer Entries »

Cory Palmer, A survey of Turán-type subgraph counting problems

Monday, October 14th, 2019

IBS/KAIST Joint Discrete Math Seminar

A survey of Turán-type subgraph counting problems
Cory Palmer
University of Montana, Missoula, MT
2019/09/19 Tue 4:30PM-5:30PM
Let $F$ and $H$ be graphs. The subgraph counting function $\operatorname{ex}(n,H,F)$ is defined as the maximum possible number of subgraphs $H$ in an $n$-vertex $F$-free graph. This function is a direct generalization of the Turán function as $\operatorname{ex}(n,F)=\operatorname{ex}(n,K_2,F)$. The systematic study of $\operatorname{ex}(n,H,F)$ was initiated by Alon and Shikhelman in 2016 who generalized several classical results in extremal graph theory to the subgraph counting setting. Prior to their paper, a number of individual cases were investigated; a well-known example is the question to determine the maximum number of pentagons in a triangle-free graph. In this talk we will survey results on the function $\operatorname{ex}(n,H,F)$ including a number of recent papers. We will also discuss this function’s connection to hypergraph Turán problems.

Tags:
Posted in 2019, KAIST Discrete Math Seminar | Comments Closed

Kevin Hendrey, The minimum connectivity forcing forest minors in large graphs

Monday, October 14th, 2019

IBS/KAIST Joint Discrete Math Seminar

The minimum connectivity forcing forest minors in large graphs
Kevin Hendrey
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.

Tags:
Posted in 2019, KAIST Discrete Math Seminar | Comments Closed

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

Sunday, July 21st, 2019

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

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

July 21 Sunday – August 10 Saturday

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

Schedule

July 22 Monday

10:00-11:00 Introduction

11:00-12:00 Open Problems

July 23 Tuesday

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

July 24 Wednesday

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

July 25 Thursday

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

July 26 Friday

10:00-11:00 O-joung Kwon (권오정), Incheon National University, Korea
The grid theorem for vertex-minors

11:00-12:00 Progress Report

July 27 Saturday

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

July 29 Monday

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

July 30 Tuesday

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

July 31 Wednesday

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

August 1 Thursday

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

August 2 Friday

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

Posted in 2019, KAIST Discrete Math Seminar | Comments Closed

Mihyun Kang (강미현), The genus of a random graph and the fragile genus property

Friday, June 28th, 2019

IBS/KAIST Joint Discrete Math Seminar

The genus of a random graph and the fragile genus property
Mihyun Kang (강미현)
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)

Tags:,
Posted in 2019, KAIST Discrete Math Seminar | Comments Closed

Dabeen Lee, Integrality of set covering polyhedra and clutter minors

Friday, June 28th, 2019

IBS/KAIST Joint Discrete Math Seminar

Integrality of set covering polyhedra and clutter minors
Dabeen Lee (이다빈)
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.

Tags:,
Posted in 2019, KAIST Discrete Math Seminar | Comments Closed

« Older Entries
Newer Entries »