Archive for the ‘KAIST Discrete Math Seminar’ Category

« Older Entries
Newer Entries »

Casey Tompkins, Extremal problems for Berge hypergraphs

Monday, October 14th, 2019

IBS/KAIST Joint Discrete Math Seminar

Extremal problems for Berge hypergraphs
Casey Tompkins
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.

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

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

« Older Entries
Newer Entries »