KAIST Discrete Math Seminar

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

  • Casey Tompkins, Extremal problems for Berge hypergraphs

    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:

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

    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:

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

    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:

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

    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:

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

    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

Monthly Archives