2024 Combinatorics Workshop

28 Aug 2024, 13:00 → 30 Aug 2024, 18:00 Asia/Seoul

107 (Bldg. S1-6 (자연대6호관))

Doowon Koh (Chungbuk National University), Eunjeong Lee (Chungbuk National University), Sang-il Oum (IBS Discrete Mathematics Group), Meesue Yoo (Chungbuk National 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 occur at Chungbuk National University in Cheongju from August 28 to August 30, 2024.

This workshop aims to bring together active researchers with different backgrounds to discuss recent and prospective advances in combinatorics and related areas.

 

Main website: https://cw2024.combinatorics.kr/

Plan

Starting in the afternoon of August 28 (Wednesday) and ending in the afternoon of August 30 (Friday).

There will be several invited talks and contributed talks.

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

It will be an offline meeting.

Invited Speakers

• Suyoung Choi (최수영), Ajou University (아주대)
• Donghyun Kim (김동현), SNU (서울대학교)
• Jang Soo Kim (김장수), SKKU (성균관대학교)
• Jeong Han Kim (김정한), KIAS (고등과학원)
• Minki Kim (김민기), GIST (광주과학기술원)

Contributed Talks

If you are interested in giving a contributed talk at the workshop, please submit the abstract by June 20, 2024 at this website. Each contributed talk will be 20-25 minutes long.

How to submit a contributed talk: Click "Call for Abstracts" and then click "Submit new abstract". You may need to create an account on IBS indico. 

Contributed Talk을 신청하려면 왼쪽에서 "Call for Abstracts"을 클릭한 후 나오는 화면에서 "Submit new abstract"를 클릭하여 신청합니다. IBS indico 계정이 없으면 만드셔야 합니다.

Registration

The registration deadline: July 10, 2024. Please register at this website.

Accommodation

글로스터 호텔 (Gloucester Hotel Cheongju)

Approximately 4 km from the hotel to the venue. General participants are responsible for their own accommodation expenses, but if requested at the time of registration, we can reserve a room for you.

We provide all the meals during the entire workshop. If you need support for the accommodation, please let us know.

일반참가자들의 숙박은 본인 부담이지만, 등록할 때 요청하시면 방을 예약해 드릴 수 있습니다.

학회 기간동안 모든 참가자들에게 점심식사와 저녁식사가 제공될 예정입니다. 숙박 지원이 필요한 경우 연락주시기 바랍니다. 

Venue

자연대6호관 (Bldg. S1-6), Room 107

Chungbuk National University (충북대학교)

Cheongju, Korea

Organizing Committee

• Doowon Koh (고두원), Chungbuk National University
• Eunjeong Lee (이은정), Chungbuk National University
• Sang-il Oum (엄상일), IBS Discrete Mathematics Group / KAIST
• Meesue Yoo (류미수), Chungbuk National University

Advisory Committee

• Committee of Discrete Mathematics, The Korean Mathematical Society (Chair: Sang-il Oum, IBS Discrete Mathematics Group / KAIST)

Sponsors

• Discrete Mathematics Group, Institute for Basic Science (IBS)
• National Research Foundation of Korea (NRF)
• Korean Mathematical Society

Wednesday, 28 August

14:00 Opening/Registration

Invited Talk

1 Asymptotic bounds of Ramsey Numbers

Ramsey numbers, denoted as R(s,t), are fundamental in graph theory, representing the smallest number of vertices n such that every graph on n vertices either contains a clique of size s or an independent set of size t. Recent developments in Ramsey theory have focused on finding asymptotic bounds for Ramsey numbers. In this talk, we survey asymptotic bounds of Ramsey Numbers R(3,t) and R(4,t), including significant contributions of Sam Mattheus and Jacques Verstraete on R(4,t).

Speaker: Jeong Han Kim (KIAS)

15:30 Coffee Break

Contributed Talk

2 102-avoiding Inversion Sequences

A sequence $(e_1, e_2, \cdots, e_n)$ is an inversion sequences if $0\leq e_i < i$ for all $i=1, \ldots, n$. We say that an inversion sequences $e=(e_1, e_2, \cdots, e_n)$ \emph{contains} the pattern $102$ if there exist some indices $i < j < k$ such that $e_j < e_i < e_k$. Otherwise, $e$ is said to \emph{avoid} the pattern $102$.

In this talk, we will construct a correspondence between the set of 2-Schröder paths without peaks and valleys ending with a diagonal step and the set of $102$-avoiding inversion sequences.
This is the joint work with JiSun Huh, Sangwook Kim, and Seunghyun Seo.

Speaker: Heesung Shin (Inha University)

3 Random matchings in linear hypergraphs

For a given hypergraph $H$ and a vertex $v\in V(H)$, consider a random matching $M$ chosen uniformly from the set of all matchings in $H$. In 1995, Kahn conjectured that if $H$ is a $d$-regular linear $k$-uniform hypergraph, the probability that $M$ does not cover $v$ is $(1 + o_d(1))d^{-1/k}$ for all vertices $v\in V(H)$. This conjecture was proved for $k = 2$ by Kahn and Kim in 1998.
We disprove this conjecture for all $k \geq 3$. For infinitely many values of $d,$ we construct $d$-regular linear $k$-uniform hypergraph $H$ containing two vertices $v_1$ and $v_2$ such that $\mathcal{P}(v_1 \notin M) = 1 - \frac{(1 + o_d(1))}{d^{k-2}}$ and $\mathcal{P}(v_2 \notin M) = \frac{(1 + o_d(1))}{d+1}$. The gap between $\mathcal{P}(v_1 \notin M)$ and $\mathcal{P}(v_2 \notin M)$ in this $H$ is best possible. In the course of proving this, we also prove a hypergraph analog of Godsil's result on matching polynomials and paths in graphs, which is of independent interest.

Speaker: Hyunwoo Lee (KAIST & IBS ECOPRO)

4 Towards a classification of $1$-homogeneous graphs with positive intersection number $a_1$

Let $\Gamma$ be a graph with diameter at least two. Then $\Gamma$ is said to be $1$-homogeneous (in the sense of Nomura) whenever for every pair of adjacent vertices $x$ and $y$ in $\Gamma$, the distance partition of the vertex set of $\Gamma$ with respect to both $x$ and $y$ is equitable, and the parameters corresponding to equitable partitions are independent of the choice of $x$ and $y$. Assume $\Gamma$ is $1$-homogeneous distance-regular with intersection number $a_1>0$ and diameter $D\geqslant 5$. Define $b=b_1/(\theta_1+1)$, where $b_1$ is the intersection number and $\theta_1$ is the second largest eigenvalue of $\Gamma$. In this talk, we show that if intersection number $c_2\geqslant 2$, then $b\geqslant 1$ and one of the following (i)--(vi) holds: (i) $\Gamma$ is a regular near $2D$-gon, (ii) $\Gamma$ is a Johnson graph $J(2D,D)$, (iii) $\Gamma$ is a halved $\ell$-cube where $\ell \in \{2D,2D+1\}$, (iv) $\Gamma$ is a folded Johnson graph $\bar{J}(4D,2D)$, (v) $\Gamma$ is a folded halved $(4D)$-cube, (vi) the valency of $\Gamma$ is bounded by a function of $b$. Moreover, we characterize $1$-homogeneous graphs with classical parameters and $a_1>0$, as well as tight distance-regular graphs. This is a joint work with J. Koolen, M. Abdullah, B. Gebremichel.

Speaker: Jae-Ho Lee (University of North Florida & POSTECH)

17:30 Dinner

Thursday, 29 August

Invited Talk

5 Extensions of the colorful Helly theorem for d-collapsible and d-Leray complexes

We present extensions of the colorful Helly theorem for d-collapsible and d-Leray complexes, providing a common generalization to the topological colorful Helly theorem by Kalai and Meshulam, the very colorful Helly theorem by Arocha et al., and the semi-intersecting colorful Helly theorem by Karasev and Montejano. As an application, we obtain a strengthened version of Tverberg's theorem. This is joint work with Alan Lew.

Speaker: Minki Kim (GIST)

10:30 Coffee Break

Contributed Talk

6 Transversal Hamilton paths and cycles of arbitrary orientations in tournaments

It is well-known that a tournament always contains a directed Hamilton path. Rosenfeld conjectured that if a tournament is sufficiently large, it contains a Hamilton path of any given orientation. This conjecture was approved by Thomason, and Havet and Thomassé completely resolved it by showing there are exactly three exceptions.

We generalized this result into a transversal setting. Let $\mathbf{T}=\{T_1,\dots,T_{n-1}\}$ be a collection of tournaments on a common vertex set $V$ of size $n$. We showed that if $n$ is sufficiently large, there is a Hamilton path on $V$ of any given orientation which is obtained by collecting exactly one arc from each $T_i$. Such a path is said to be transversal.

It is also a folklore that a strongly connected tournament always contains a directed Hamilton cycle. Rosenfeld made a conjecture for arbitrarily oriented Hamilton cycles in tournaments as well, which was approved by Thomason (for sufficiently large tournaments) and Zein (by specifying all the exceptions). We also showed a transversal version of this result. Together with the aforementioned result, it extends our previous research, which is on transversal generalizations of existence of directed paths and cycles in tournaments.

This is a joint work with Debsoumya Chakraborti, Jaehoon Kim, and Hyunwoo Lee.

Speaker: Jaehyeon Seo (Yonsei University)

11:30 Group Photo / Lunch

Invited Talk

7 Toric Colorability of Graphs of Simplicial $d$-Polytopes with $𝑑+4$ vertices

The 1-skeleton of a convex polytope $P$ is called the graph of $P$.
A graph of a simplicial $d$-polytope is said to be toric colorable if there is a vertex coloring $\lambda \colon V(G) \to \mathbb{Z}^d$ such that $\{v_1, \ldots, v_d\}$ forms a face of $P$ implies that $\{\lambda(v_1), \ldots, \lambda(v_d)\}$ is unimodular.
In this talk, we discuss the toric colorability of graphs of simplicial $d$-polytopes with $d+4$ vertices.

Speaker: Suyoung Choi (Ajou University)

14:30 Coffee Break

Contributed Talk

8 Alternating $\mathcal{B}$-permutations arising from toric topology

In this talk, we focus on the rational Betti numbers of real toric manifolds associated with chordal nestohedra. We introduce an explicit description for the Betti numbers using alternating $\mathcal{B}$-permutations for a chordal building set $\mathcal{B}$. We provide detailed computations for interesting cases of chordal nestohedra, including permutohedra, associahedra, stellohedra, Stanley-Pitman polytopes, and Hochschild polytopes.
This is joint work with Suyoung Choi.

Speaker: Younghan Yoon (Ajou University)

9 Partitions of ordered partitions and Bott manifolds

Bott manifolds are smooth projective toric varieties providing interesting avenues among topology, geometry, representation theory, and combinatorics. They are used to understand the geometric structure of Bott-Samelson-Demazure-Hansen (BSDH) varieties, which provide desingularizations of Schubert varieties. However, not all Bott manifolds originate from BSDH varieties. Those that do are specifically referred to as Bott manifolds of Bott-Samelson-Demazure-Hansen type. In this talk, we explore a relationship between Bott manifolds of BSDH type and partitions of ordered partitions. This talk is based on joint work with Jang Soo Kim and Eunjeong Lee.

Speaker: Junho Jeong (Chungbuk National University)

16:00 Coffee Break

Contributed Talk

10 Homotopy Types of Vietoris-Rips Complexes and Their Connection to Hyperconvexity

The Vietoris-Rips complex, originally introduced by Leopold Vietoris in the early 1900s to develop a homology theory for metric spaces, has since found applications in various areas of mathematics. Eliyahu Rips and Mikhail Gromov further utilized it in their studies of hyperbolic groups. More recently, classifying the homotopy types of Vietoris-Rips complexes has become a significant problem in Topological Data Analysis and Global Metric Geometry. Understanding these complexes can enhance our grasp of the persistence barcode's strength and provide lower bounds for the Gromov-Hausdorff distance between manifolds. In this talk, we will delve into these motivations and introduce the precise connections between Vietoris-Rips complexes, hyperconvex metric spaces, and their homotopy types.

Speaker: Sunhyuk Lim (Sungkyunkwan University)

11 On the extremal number of face-incidence graphs

The $(k,r)$-incidence graph of a regular polytope $\mathcal{P}$ is the bipartite incidence graph between $k$-faces and $r$-faces of $\mathcal{P}$. We obtain a general upper bound and a corresponding supersaturation result for the extremal number of the $(k,r)$-incidence graph of any regular polytope.
This generalises recent results of Janzer and Sudakov, who obtained the same bound for hypercubes and bipartite Kneser graphs, and confirms the conjecture of Conlon and Lee on the extremal number of $K_{d,d}$-free bipartite graphs for certain $(k,r)$-incidence graphs.

Our proof, based on the reflection group method developed by Conlon and Lee, presents the method in a purely algebraic manner.
As a consequence, this puts a number of results, including the Janzer-Sudakov theorem, the Conlon-Lee theorem on weakly norming graphs, and Coregliano's theorem on Sidorenko's conjecture, in the unified framework and simplifies all the proofs.

Joint work with David Conlon and Joonkyung Lee.

Speaker: Jisun Baek (Yonsei University)

17:30 Banquet

Friday, 30 August

Invited Talk

12 Lusztig $q$ weight multiplicities via affine crystals

Lusztig $q$ weight multiplicity is a polynomial in $q$ whose positivity has been verified by linking it to a specific affine Kazhdan-Lusztig polynomial. However, a combinatorial formula beyond type A has not been known until recently.

In 2019, Lee proposed a combinatorial formula for type C using a novel combinatorial concept known as semistandard oscillating tableaux. We will outline the proof of Lee's conjecture and discuss how it can be extended to type B spin weights case.

Based on joint work with Hyeonjae Choi and Seung Jin Lee.

Speaker: Donghyun Kim

10:30 Coffee Break

Contributed Talk

13 Combinatorics of orthogonal polynomials on the unit circle

Orthogonal polynomials on the unit circle (OPUC) are a family of polynomials orthogonal with respect to integration on the unit circle in the complex plane. The values of these integrals can be obtained by calculating moments. Numerous combinatorial studies have explored the moments of various types of orthogonal polynomials, including classical orthogonal polynomials, Laurent biorthogonal polynomials, and orthogonal polynomials of type $R_I$.

In this talk, we first explain how OPUC relate to these other variations. Next, we study the moments of OPUC from a combinatorial perspective, providing three path interpretations: Łukasiewicz paths, gentle Motzkin paths, and Schröder paths. Using these combinatorial interpretations, we derive explicit formulas for the generalized moments of some examples of OPUC, including the circular Jacobi polynomials and the Rogers–Szegő polynomials. Furthermore, we introduce several types of generalized linearization coefficients and provide combinatorial interpretations for each of them.

Speaker: Minho Song (Sungkyunkwan University)

11:30 Coffee Break

Invited Talk

14 Enumeration of multiplex juggling card sequences using generalized $q$-derivatives

In 2019, Butler, Choi, Kim, and Seo introduced a new type of juggling card that represents multiplex juggling patterns in a natural bijective way. They conjectured a formula for the generating function for the number of multiplex juggling cards with capacity.
In this paper we prove their conjecture. More generally, we find an explicit formula for the generating function with any capacity. We also find an expression for the generating function for multiplex juggling card sequences by introducing a generalization of the $q$-derivative operator. As a consequence, we show that this generating function is a rational function.

Speaker: Jang Soo Kim (Sungkyunkwan University)

Contributed Talk

15 Two ways to generalize matroids with coefficients

Dress (1986) introduced matroids with coefficients offering a unified approach to ordinary matroids, representations of matroids over fields, and oriented matroids. Baker and Bowler (2019) extended this theory, whose result includes a partial field representation by Semple and Whittle (1996).

I will present two generalizations of matroids with coefficients. One is about skew-symmetric matrices and even delta-matroids, based on joint work with Tong Jin. We deduce several results on the representability of even delta-matroids as applications. The other concerns symmetric matrices and new matroid-like objects called antisymmetric matroids. It extends old results on the representability of matroids by Tutte (1958) and basis graphs of matroids by Maurer (1973). These two generalizations involve an interesting interplay between Lagrangian orthogonal/symplectic Grassmannians and combinatorics.

Speaker: Donggyu Kim (KAIST & IBS DIMAG)

15:00 Closing