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

Session

Session

20 Dec 2021, 15:00

Yangpyeong The Bloomvista

18. Eigenvalues and factors in graphs

Prof. Suil O (SUNY Korea)

20/12/2021, 15:00

Invited talk

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)(\mathrm{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)...

12. Isomorphism problem for even-cycle matroids

Cheolwon Heo (SKKU AORC)

20/12/2021, 16:00

Contributed talk

A signed graph is a pair $(G,\mathrm{\Sigma })$ where $G$ is a graph and $\mathrm{\Sigma }$ is a subset of edges of $G$. We say that a cycle $C$ of $G$ is even in $(G,\mathrm{\Sigma })$ if $|C\cap \mathrm{\Sigma }|$ is even; otherwise, $C$ is odd. A matroid $M$ is an even-cycle matroid if there exists a signed graph $(G,\mathrm{\Sigma })$ such that the circuits of $M$ precisely correspond to the even cycles or the unions of two odd cycles...

11. When all holes in a graph have the same length

Linda Cook (IBS DIMAG)

20/12/2021, 17:00

Contributed talk

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,...

7. On 1-subdivision of transitive tournaments

Hyunwoo Lee (KAIST)

20/12/2021, 17:30

Contributed talk

The oriented Ramsey number $\overrightarrow{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 $\overrightarrow{r}(H_k)\le 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...

14. Towards a dichotomy classification for list switch homomorphism problem for signed graphs

Hyobin Kim (Kyungpook National University)

20/12/2021, 18:00

Contributed talk

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.

15. Classical statistics on permutations and inversion sequences

Prof. Dongsu Kim (KAIST)

21/12/2021, 09:30

Invited talk

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...

8. Combinatorics of Euclidean spaces over finite fields

Semin Yoo (KIAS)

21/12/2021, 10:30

Contributed talk

$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...

4. Bounds for the twin-width of graphs

Jungho Ahn (KAIST and IBS DIMAG)

21/12/2021, 11:00

Contributed talk

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...

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

Joonkyung Lee (Hanyang University)

21/12/2021, 14:00

Invited talk

A family $\mathcal{H}$ of graphs is said to be $\chi$-bounded, if there is a function $f:\mathbb{N}\to \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...

5. Fractional Helly theorem for Cartesian products of convex sets

Minki Kim (IBS DIMAG)

21/12/2021, 15:00

Contributed talk

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...

6. On multicolor extremal problems

Jaehyeon Seo (KAIST)

21/12/2021, 15:30

Contributed talk

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...

16. Smooth toric Richardson varieties of Catalan type

Seonjeong Park (Jeonju University)

21/12/2021, 16:30

Invited talk

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...

10. Large clique subdivisions in graphs without small dense subgraphs

Seonghyuk Im (KAIST)

21/12/2021, 17:35

Contributed talk

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)=\mathrm{\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...

9. On independent domination of cubic graphs without 4-cycles

Hyemin Kwon (Ajou University)

21/12/2021, 18:00

Contributed talk

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)\le \frac{4}{11}|V(G)|$ for every cubic graph $G$ with girth at least...

19. Exponential decay of intersection volume and applications

Hong Liu (University of Warwick)

22/12/2021, 10:00

Invited talk

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.

13. Mathematical Approach to the Pallet Loading Problem

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

22/12/2021, 11:00

Contributed talk

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...

3. Detecting and Recovering Vote Manipulation on Produce X 101

Sang June Lee (Kyung Hee University)

22/12/2021, 11:30

Contributed talk

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...