IBS/KAIST Joint Discrete Math Seminar

IBS Discrete Mathematics Group

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

IBS/KAIST Joint Discrete Math Seminar

Extremal problems for Berge hypergraphs

Casey Tompkins

IBS Discrete Mathematics Group

IBS Discrete Mathematics Group

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

Given a graph $G$, there are several natural hypergraph families one can define. Among the least restrictive is the family $BG$ of so-called Berge copies of the graph $G$. In this talk, we discuss Turán problems for families $BG$ in $r$-uniform hypergraphs for various graphs $G$. In particular, we are interested in general results in two settings: the case when $r$ is large and $G$ is any graph where this Turán number is shown to be eventually subquadratic, as well as the case when $G$ is a tree where several exact results can be obtained. The results in the first part are joint with Grósz and Methuku, and the second part with Győri, Salia and Zamora.

IBS/KAIST Joint Discrete Math Seminar

A survey of Turán-type subgraph counting problems

Cory Palmer

University of Montana, Missoula, MT

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.

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)