2021 Combinatorics Workshop (2021 조합론 학술대회)

20 Dec 2021, 13:00 → 22 Dec 2021, 15:00 Asia/Seoul

Yangpyeong The Bloomvista

Jeong Ok Choi, Sang-il Oum (Discrete Mathematics Group), Heesung Shin (Inha University)

The annual conference on Combinatorics Workshop (조합론 학술대회) was begun in 2004 by the Yonsei University BK21 Research Group. Since 2013, this workshop has been advised by the committee of discrete mathematics of the Korean Mathematical Society. This year it will take place at The Bloomvista in Yangpyeong on December 20-22, 2021.

The aim of this workshop is to bring together active researchers with different backgrounds to discuss recent and prospective advances in combinatorics and related areas.

Plan

• Starting in the afternoon of Monday and ending in the morning of Wednesday.

• There will be contributed talks.

• Using English is recommended if there are non-Korean participants in the audience.

• It will be an offline meeting.

Invited Speakers

• Dongsu Kim, KAIST
• Joonkyung Lee, Hanyang University
• Hong Liu, University of Warwick, UK
• Suil O, SUNY Korea
• Seonjeong Park, Jeonju University

Contributed Talks

If you are interested in giving a contributed talk at the workshop, then please submit the abstract by November 15 at this website. Each contributed talk will be 25 minutes long.

Registration

The registration deadline: November 21, 2021. Please register at this website.

2021 Combinatorics Workshop --- Website

Monday 20 December

14:00 Registration

Session: Talks 1

1 Eigenvalues and factors in graphs

Let $g, f$ be non-negative integer-valued functions on $V(G)$ such that $g(v) \le f(v) \le d_G(v)$ for all $v \in V(G)$.
A $(g,f)$-factor of $G$ is a spanning subgraph $H$ of $G$ such that for every vertex $v \in V(G)$, $g(v) \le d_H(v) \le f(v)$. For $g$ and $f$ with $g(v) \equiv f(v) (\mod 2)$ for all $v \in V(G)$, a $(g, f)$-parity factor of $G$ is a $(g,f)$-factor $H$ such that $d_H(v) \equiv f(v) (\mod 2)$ for all $v \in V(G)$.
For integers $a$ and $b$, an $[a,b]$-factor of $G$ is a $(g,f)$-factor such that $g(v)=a$ and $f(v)=b$ for all $v \in V(G)$,
and a $k$-factor is a $[k,k]$-factor. For odd (or even, respectively) integers $a$ and $b$, an odd (or even, respectively) $[a,b]$-factor is an $[a,b]$-factor $H$ such that $d_H(v)$ is odd (or even, respectively). The eigenvalues of $G$ are the eigenvalues of its adjacency matrix.

In this talk, we investigate eigenvalue conditions for a certain graph to have a $k$-factor, an (even or odd) $[a,b]$-factor,
a $(g,f)$-parity factor, or a connected (even or odd) factor.

Speaker: Prof. Suil O (SUNY Korea)

2 Isomorphism problem for even-cycle matroids

A signed graph is a pair $(G,\Sigma)$ where $G$ is a graph and $\Sigma$ is a subset of edges of $G$. We say that a cycle $C$ of $G$ is even in $(G,\Sigma)$ if $|C \cap \Sigma|$ is even; otherwise, $C$ is odd. A matroid $M$ is an even-cycle matroid if there exists a signed graph $(G,\Sigma)$ such that the circuits of $M$ precisely correspond to the even cycles or the unions of two odd cycles sharing at most one vertex. Isomorphism problem for even-cycle matroids is the problem of characterizing two signed graphs $(G_1,\Sigma_1)$ and $(G_2, \Sigma_2)$ representing the same even-cycle matroid. In this talk, I will give the structures for solving this problem when $G_1$ and $G_2$ are $4$-connected.
This is joint work with Bertrand Guenin and Irene Pivotto.

Speaker: Cheolwon Heo (SKKU AORC)

Session: Talks 2

3 When all holes in a graph have the same length

We call an induced cycle of length at least four a hole. The parity of a hole is the parity of its length. Forbidding holes of certain types in a graph has deep structural implications. In 2006, Chudnovksy, Seymour, Robertson, and Thomas famously proved that a graph is perfect if and only if it does not contain an odd hole or a complement of an odd hole. In 2002, Conforti, Cornuéjols, Kapoor, and Vušković provided a structural description of the class of even-hole-free graphs. I will describe the structure of all graphs that contain only holes of length $\ell$ for every $\ell \geq 7$ (joint work with Jake Horsfield, Myriam Preissmann, Paul Seymour, Ni Luh Dewi Sintiari, Cléophée Robin, Nicolas Trotignon, and Kristina Vušković.

Speaker: Linda Cook (IBS DIMAG)

4 On 1-subdivision of transitive tournaments

The oriented Ramsey number $\vec{r}(H)$ for an acyclic digraph $H$ is the minimum integer $n$ such that any $n$-vertex tournament contains a copy of $H$ as a subgraph. We prove that the $1$-subdivision of the $k$-vertex transitive tournament $H_k$ satisfies $\vec{r}(H_k)\leq O(k^2\log\log k)$. This is tight up to multiplicative $\log\log k$-term.

We also show that if $T$ is an $n$-vertex tournament with $\Delta^+(T)-\delta^+(T)\leq O(n/k) - k^2$, then $T$ contains a $1$-subdivision of $\vec{K}_k$, a complete $k$-vertex digraph with all possible $k(k-1)$ arcs. This is also tight up to multiplicative constant.

Speaker: Hyunwoo Lee (KAIST)

5 Towards a dichotomy classification for list switch homomorphism problem for signed graphs

The list switch homomorphisms problem $LSwHom(H)$ is for a signed graph $G$ with list if there is a switch homomorphism to $H$ preserving lists. We present towards a structural characterisation of the signed graphs $H$ for which the $LSwHom(H)$ problem is polynomial time solvable. We prove the characterisation in the case that the signed graph is reflexive.

Speaker: Hyobin Kim (Kyungpook National University)

19:00 Banquet

Tuesday 21 December

Session: Talks 3

6 Classical statistics on permutations and inversion sequences

The study of patterns in inversion sequences was initiated by Corteel-Martinez-Savage-Weselcouch and Mansour-Shattuck independently. This talk introduces some investigation on several classical statistics on restricted inversion sequences that are either known or conjectured to be enumerated by Catalan, Large Schröder, Baxter and Euler numbers. This talk is based on joint work with Zhicong Lin [refined restricted inversion sequences, available at https://doi.org/10.1007/s00026-021-00550-7].

Speaker: Prof. Dongsu Kim (KAIST)

7 Combinatorics of Euclidean spaces over finite fields

$q$-analogues of quantities in mathematics involve perturbations of classical quantities using the parameter $q$, and revert to the original quantities when $q$ goes $1$. An important example is the $q$-analogues of binomial coefficients, which give the number of $k$-dimensional subspaces in $\mathbb{F}_{q}^{n}$. When $q$ goes to $1$, this reverts to the binomial coefficients which measure the number of $k$-sets in $\left [ n \right ]$.

In this talk, we describe a formula of the number of quadratic subspaces of Euclidean type in $(\mathbb{F}_{q}^{n},x_{1}^{2}+\cdots+x_{n}^{2})$, which can be described as the form of the analogue of binomial coefficients. The main goal of this talk is to explain this new analogue of binomial coefficients and to study their related combinatorics.

Speaker: Semin Yoo (KIAS)

8 Bounds for the twin-width of graphs

Bonnet, Kim, Thomass\'{e}, and Watrigant (2020) introduced the twin-width of a graph. We show that the twin-width of an $n$-vertex graph is less than $(n+\sqrt{n\ln n}+\sqrt{n}+2\ln n)/2$, and the twin-width of an $m$-edge graph is less than $\sqrt{3m}+ m^{1/4} \sqrt{\ln m} / (4\cdot 3^{1/4}) + 3m^{1/4} / 2$. Conference graphs of order $n$ (when such graphs exist) have twin-width at least $(n-1)/2$, and we show that Paley graphs achieve this lower bound. We also show that the twin-width of the Erd\H{o}s-R\'{e}nyi random graph $G(n,p)$ with $1/n\leq p\leq 1/2$ is larger than $2p(1-p)n - (2\sqrt{2}+\varepsilon)\sqrt{p(1-p)n\ln n}$ asymptotically almost surely for any positive $\varepsilon$. Lastly, we calculate the twin-width of random graphs $G(n,p)$ with $p\leq c/n$ for a constant $c<1$, determining the thresholds at which the twin-width jumps from $0$ to $1$ and from $1$ to $2$.

Speaker: Jungho Ahn (KAIST and IBS DIMAG)

12:00 Lunch

Session: Talks 4

9 $\chi$-boundedness of graphs with no cycles with k chords

A family $\mathcal{H}$ of graphs is said to be $\chi$-bounded, if there is a function $f:\mathbb{N}\rightarrow\mathbb{N}$ such that for every graph $H\in\mathcal{H}$ the chromatic number $\chi(H)$ of $H$ is at most $f(\omega)$, where $\omega$ is the clique number of $H$. We show that the family of graphs that do not have a cycle with exactly $k$ chords is $\chi$-bounded, for every large enough $k$. This proves a conjecture of Aboulker and Bousquet (2015) for sufficiently large $k$. Joint work with Shoham Letzter and Alexey Pokrovskiy.

Speaker: Joonkyung Lee (Hanyang University)

10 Fractional Helly theorem for Cartesian products of convex sets

Helly's theorem and its variants asserts that for a family of convex sets in Euclidean space, local intersection patterns influence global intersection patterns. A classical result of Eckhoff in 1988 provided an optimal fractional Helly theorem for axis-parallel boxes, which are Cartesian products of line segments. Answering a question raised by Barany and Kalai, and independently by Lew, we generalize Eckhoff's result to Cartesian products of convex sets in all dimensions. Namely, we prove that, given $\alpha \in (1-\frac{1}{t^d},1]$ and a finite family of Cartesian products of convex sets $\prod_{i\in[t]}A_i$ in $\mathbb{R}^{td}$ with $A_i \subset \mathbb{R}^d$, if at least $\alpha$-fraction of the $(d+1)$-tuples in $\mathcal{F}$ are intersecting, then at least $(1-(t^d(1-\alpha))^{1/(d+1)})$-fraction of the sets in $\mathcal{F}$ are intersecting.

Speaker: Minki Kim (IBS DIMAG)

11 On multicolor extremal problems

We study a natural generalization of the well-studied Tur\'an problems, known as multicolor Tur\'an problems, which was first introduced and nurtured by Keevash, Saks, Sudakov, and Verstra\"{e}te. A simple $k$-coloring of a multigraph $G$ is a decomposition of the edge multiset as a disjoint sum of $k$ simple graphs which are referred as \emph{colors}. A subgraph $H$ of a multigraph $G$ is called \emph{multicolored} if all of its edges have distinct colors. The multicolor extremal number, $\mathrm{ex}_k(n,H)$, is defined as the maximum number of edges in an $n$-vertex multigraph that has a simple $k$-coloring containing no multicolored copy of $H$.
Two natural constructions for this problem are as follows: When $k < e(H)$, it is clear that the unique extremal construction comes from $k$ copies of the complete graph. Even when $k \ge e(H)$, one can consider the multigraph consisting of $e(H)-1$ copies of the complete graph. A second natural construction is to take the sum of $k$ copies of a fixed extremal $H$-free graph. Keevash, Saks, Sudakov, and Verstra\"{e}te showed that the multicolor extremal problem always admits one of the two natural constructions when $H$ is a complete graph of any fixed order. Moreover, they conjectured the same for every color-critical graphs and proved it for 3-color-critical graphs.
We prove their conjecture for 4-color-critical graphs and for `most' $r$-color-critical graphs when $r > 4$. Moreover, we show that for every non-color-critical non-bipartite graphs, none of the two natural constructions is extremal for certain values of $k$. This answers a question of Keevash, Saks, Sudakov, and Verstra\"{e}te.

Speaker: Jaehyeon Seo (KAIST)

Session: Talks 5

12 Smooth toric Richardson varieties of Catalan type

We define an n-dimensional projective smooth toric variety associated with a triangulation of the (n+2)-gon. Such a toric variety is called of Catalan type. We show that toric varieties of Catalan type are Fano Bott manifolds, and they appear in certain smooth toric Richardson varieties in the flag variety. We also see that toric varieties of Catalan type are classified up to isomorphism in terms of unordered binary trees.

Speaker: Seonjeong Park (Jeonju University)

13 Large clique subdivisions in graphs without small dense subgraphs

What is the largest number $f(d)$ where every graph with average degree at least $d$ contains a subdivision of $K_{f(d)}$? Mader asked this question in 1967 and $f(d) = \Theta(\sqrt{d})$ was proved by Bollob\'as and Thomason and independently by Koml\'os and Szemer\'edi. This is best possible by considering a disjoint union of $K_{d,d}$. However, this example contains a much smaller subgraph with the almost same average degree, for example, one copy of $K_{d,d}$.

In 2017, Liu and Montgomery proposed the study on the parameter $c_{\varepsilon}(G)$ which is the order of the smallest subgraph of $G$ with average degree at least $\varepsilon d(G)$. In fact, they conjectured that for small enough $\varepsilon>0$, every graph $G$ of average degree $d$ contains a clique subdivision of size $\Omega(\min\{d, \sqrt{\frac{c_{\varepsilon}(G)}{\log c_{\varepsilon}(G)}}\})$. We prove that this conjecture holds up to a multiplicative $\min\{(\log\log d)^6,(\log \log c_{\varepsilon}(G))^6\}$-term.

As a corollary, for every graph $F$, we determine the minimum size of the largest clique subdivision in $F$-free graphs with average degree $d$ up to multiplicative polylog$(d)$-term.

This is joint work with Jaehoon Kim, Youngjin Kim, and Hong Liu.

Speaker: Seonghyuk Im (KAIST)

14 On independent domination of cubic graphs without 4-cycles

A dominating set of a graph $G$ is a set $S$ of vertices such that each vertex not in $S$ is adjacent to some vertex in $S$. The independent domination number of a graph $G$, denoted $i(G)$, is the minimum cardinality of a dominating set of $G$ which is also independent. In 2018, Abrishami and Henning showed that $i(G) \leq \frac{4}{11}|V(G)|$ for every cubic graph $G$ with girth at least 6.

In this talk, we present a result on the independent domination number of a cubic graph, which implies the aforementioned result. More precisely, we prove that if $G$ is a cubic graph without 4-cycles, then $i(G) \leq \frac{5}{14}|V(G)|$, and the bound is tight. This is based on joint work with Eun-Kyung Cho, Ilkyoo Choi and Boram Park.

Speaker: Hyemin Kwon (Ajou University)

19:00 Banquet

Wednesday 22 December

Session: Talks 6

15 Exponential decay of intersection volume and applications

When two balls in a metric space has small intersection? We give some natural conditions to guarantee an exponential decay on the volume of such intersections. Our proof is conceptually simple, making use of concentration of measure on a "slice". We will discuss a couple of applications of this volume estimate in coding theory. This is joint work with Jaehoon Kim and Tuan Tran.

Speaker: Hong Liu (University of Warwick)

16 Mathematical Approach to the Pallet Loading Problem

The (manufacturer's) pallet loading problem has been a topic of wide interest for operational research and companies for more than 50 years. It is to find the optimal loading of identical rectangular boxes onto a single rectangular pallet (also allowing for 90 degree rotation).

It was already known that all box layouts in the given pallet are completely determined by the set of efficient partitions of the pallet's width and height in the box dimensions. The main interest of this talk is the enumeration of all efficient partitions.

We review the pallet loading problem and discuss a mathematical approach to this problem.

Speaker: Dr Jin-Hwan CHO (National Institute for Mathematical Sciences)

17 Detecting and Recovering Vote Manipulation on Produce X 101

This talk presents a method for detecting and restoring integer datasets that have been manipulated by operations involving non-integral real-number multiplication and rounding. Detecting and restoring such manipulated integer datasets is not straightforward, nor are there any known solutions. We introduce the manipulation process, which was motivated by an actual case of fraud on the TV program "Pruduce X 101", and survey several areas of literature dealing with the possibility that manipulation may have happened or might occur.

From our mathematical analysis of the manipulation process, we can prove that the non-integral real number a used in the multiplication exists not as a single real number but as an interval containing infinitely many real numbers, any of which could have been used to produce the same manipulation result.

Based on these analytic findings, we provide an algorithm that can detect and restore manipulated integer datasets. To validate our algorithm, we applied it to 40,000 test datasets that were randomly generated using controllable parameters that matched the real fraud case. Our results indicated that the algorithm detected and perfectly restored all datasets for which the value of the non-integral real number was at least 16 and the number of data entries was at least 40.

This is joint work with Taejung Park (Duksung Women's University) and Hyunjoo Song (Soongsil University).

Speaker: Sang June Lee (Kyung Hee University)

12:00 Lunch