Open Symposium at the Discrete Mathematics Group

On July 13, 2023, the Open Symposium at the Discrete Mathematics Group was held. There were four talks by the members of the Discrete Mathematics Group.

9:40-10:05Obstructions for dense analogs of tree-depthSang-il OUM
10:05-10:20Structural and extremal results for twin-widthKevin HENDREY
10:20-10:35Down-sets in combinatorial posetsRutger CAMPBELL
10:35-10:50Reuniting 𝜒-boundedness with polynomial 𝜒-boundednessLinda COOK

Kevin Hendrey gave a talk on describing a graph as a subgraph of the strong product of a graph of small tree-width and a small complete graph at the Discrete Math Seminar

On July 11, 2022, Kevin Hendrey from IBS Discrete Mathematics Group gave a talk at the Discrete Math Seminar on describing a graph as a subgraph of the strong product of a graph of a small tree-width and a small complete graph. The title of his talk was “Product Structure of Graph Classes with Bounded Treewidth“.

Kevin Hendrey, Product Structure of Graph Classes with Bounded Treewidth

The strong product $G\boxtimes H$ of graphs $G$ and $H$ is the graph on the cartesian product $V(G)\times V(H)$ such that vertices $(v,w)$ and $(x,y)$ are adjacent if and only if $\max\{d_G(v,x),d_H(w,y)\}=1$. Graph product structure theory aims to describe complicated graphs in terms of subgraphs of strong products of simpler graphs. This area of research was initiated by Dujmović, Joret, Micek, Morin, Ueckerdt and Wood, who showed that every planar graph is a subgraph of the strong product of a $H\boxtimes P\boxtimes K_3$ for some path $P$ and some graph $H$ of treewidth at most $3$. In this talk, I will discuss the product structure of various graph classes of bounded treewidth. As an example, we show that there is a function $f:\mathbb{N}\rightarrow \mathbb{N}$ such that every planar graph of treewidth at most $k$ is a subgraph of $H\boxtimes K_{f(k)}$ for some graph $H$ of treewidth at most $3$.

This is based on joint work with Campbell, Clinch, Distel, Gollin, Hickingbotham, Huynh, Illingworth, Tamitegama, Tan and Wood.

Kevin Hendrey gave a talk on a unified Erdős-Pósa theorem for cycles in graphs labeled by multiple abelian groups at the Discrete Math Seminar

On March 7, 2022, Kevin Hendrey from the IBS Discrete Mathematics Group gave a talk at the Discrete Math Seminar on a unified Erdős-Pósa theorem for cycles in graphs labeled by multiple abelian groups at the Discrete Math Seminar. The title of his talk was “A unified Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups (revisited)“.

Kevin Hendrey, A unified Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups (revisited)

This talk follows on from the recent talk of Pascal Gollin in this seminar series, but will aim to be accessible for newcomers.

Erdős and Pósa proved in 1965 that there is a duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. By relaxing `packing’ to `half-integral packing’, Reed obtained an analogous result for odd cycles, and gave a structural characterisation of when the (integral) packing version fails.

We prove some far-reaching generalisations of these theorems. First, we show that if the edges of a graph are labelled by finitely many abelian groups, then the cycles whose values avoid a fixed finite set for each abelian group satisfy the half-integral Erdős-Pósa property. Similarly to Reed, we give a structural characterisation for the failure of the integral Erdős-Pósa property in this setting. This allows us to deduce the full Erdős-Pósa property for many natural classes of cycles.

We will look at applications of these results to graphs embedded on surfaces, and also discuss some possibilities and obstacles for extending these results.

This is joint work with Kevin Hendrey, Ken-ichi Kawarabayashi, O-joung Kwon, Sang-il Oum, and Youngho Yoo.

Kevin Hendrey, Extremal functions for sparse minors

The extremal function $c(H)$ of a graph $H$ is the supremum of densities of graphs not containing $H$ as a minor, where the density of a graph is the ratio of the number of edges to the number of vertices. Myers and Thomason (2005), Norin, Reed, Thomason and Wood (2020), and Thomason and Wales (2019) determined the asymptotic behaviour of $c(H)$ for all polynomially dense graphs $H$, as well as almost all graphs of constant density. We explore the asymptotic behavior of the extremal function in the regime not covered by the above results, where in addition to having constant density the graph $H$ is in a graph class admitting strongly sublinear separators. We establish asymptotically tight bounds in many cases. For example, we prove that for every planar graph $H$, \[c(H) = (1+o(1))\max (v(H)/2, v(H)-\alpha(H)),\] extending recent results of Haslegrave, Kim and Liu (2020). Joint work with Sergey Norin and David R. Wood.

Kevin Hendrey gave a talk on the theorem on the half-integral Erdős-Posa property of cycles in a graph with edge labelling by multiple abelian groups at the Discrete Math Seminar

On March 2, 2021, Kevin Hendrey from the IBS Discrete Mathematics Group presented his recent result with Pascal Gollin, Ken-ichi Kawarabayashi, O-joung Kwon, and Sang-il Oum on the half-integral Erdős-Posa property of cycles in a graph with edge labelling by multiple abelian groups at the Discrete Math Seminar. The title of his talk was “A unified half-integral Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups“.

Kevin Hendrey, A unified half-integral Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups

Erdős and Pósa proved in 1965 that there is a duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. Such a duality does not hold if we restrict to odd cycles.  However, in 1999, Reed proved an analogue for odd cycles by relaxing packing to half-integral packing. We prove a far-reaching generalisation of the theorem of Reed; if the edges of a graph are labelled by finitely many abelian groups, then there is a duality between the maximum size of a half-integral packing of cycles whose values avoid a fixed finite set for each abelian group and the minimum size of a vertex set hitting all such cycles.

A multitude of natural properties of cycles can be encoded in this setting, for example cycles of length at least $\ell$, cycles of length $p$ modulo $q$, cycles intersecting a prescribed set of vertices at least $t$ times, and cycles contained in given $\mathbb{Z}_2$-homology classes in a graph embedded on a fixed surface. Our main result allows us to prove a duality theorem for cycles satisfying a fixed set of finitely many such properties.

This is joint work with J. Pascal Gollin, Ken-ichi Kawarabayashi, O-joung Kwon, and Sang-il Oum.

Kevin Hendrey received Vice-Chancellor’s Commendation for Thesis Excellence from Monash University for his outstanding Ph.D. thesis

Kevin Hendrey

On July 24, 2020, Kevin Hendrey of IBS Discrete Mathematics Group was awarded 2020 Vice-Chancellor’s Commendation for Thesis Excellence from Monash University. This award is to recognize and reward outstanding doctoral and research master’s thesis excellence. Congratulations! Here is the link to the award booklet.

IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.