2022 Combinatorics Workshop

30 Sept 2022, 13:00 → 1 Oct 2022, 18:00 Asia/Seoul

Hong Liu (IBS Extremal Combinatorics and Probability Group), Jeong Ok Choi, Minki Kim (IBS), Sangwook Kim

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 GIST in Gwangju on September 30 - October 1, 2022.

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 September 30 (Friday) and ending in the afternoon of October 1 (Saturday).

There will be 4 invited talks and 9 contributed talks.

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

It will be an offline meeting.

Invited Speakers

• Andeas Holmsen, KAIST
  • Some new results on geometric transversals
• Seog-jin Kim, Konkuk University
  • Introduction to DP-coloring
• Seung Jin Lee, Seoul National University
  • Chromatic quasisymmetric functions and linked rook placements
• Hayan Nam, Duksung Women's University
  • New connections between numerical semigroups and integer partitions

Contributed Talks

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

Registration

The registration deadline: September 11, 2022. Please register at this website.

Accommodation

We booked rooms at Hotel Hive Inn (http://instagram.com/hotel__hiveinn), which is a new hotel near GIST (30 minutes by walk). Price is at your own expense, but you can stay at the hotel without reservation. If you want to stay at Hotel Hive Inn, please declare it in the registration form. In that case, please complete your registration by August 28, 2022.

(If you miss the deadline but want to stay at Hotel Hive Inn, you have to make a separate reservation. The price may be different.)

 

Here is a list of some other hotels near GIST:

- Noble Stay Hotel (노블스테이호텔 (noblestayhotel.com))

- Duzon Hotel (더존호텔 (duzonhotel.com))

- Empire Tourist Hotel (엠파이어관광호텔 (empirehotel.co.kr))

Venue

광주광역시 북구 첨단과기로 123, 광주과학기술원
(Gwanju Institute of Science and Technology (GIST), 123 Cheomdangwagi-ro, Buk-gu, Gwangju)

• 자가운전 차량(고속도로) 이용 시
  - 호남선 하행: 광주요금소를 지나 4km 지점에서 광산IC(하남.첨단단지)로 우회전하고,우회전 직후 첨단단지 방향으로 다시 우회전한 후, 지하도를 지나 1km 직진하면 좌측에 광주과학기술원 위치 (10분 내외)
  - 호남선 상행: 동광주요금소를 지나 광산IC(하남.첨단단지)로 우회전하고, 우회전 직후 첨단단지 방향으로 다시 우회전한 후, 지하도를 지나 1km 직진하면 좌측에 광주과학기술원 위치 (20분 내외)
• 항공 이용 시
  - 광주 공항 도착 후 출구 앞에서 택시 탑승 (20분 내외)
• 고속버스 이용 시
  - 비아임시하차장: 고속버스 탑승 시, 비아임시하차장에서 하차 가능 여부 확인 필요, 하차 후 택시 탑승 (10분 내외)
  - 광주종합버스터미널(유스퀘어): 택시 이용(30분 내외) 또는 첨단09(급행)-쌍암공원 정류장 하차 / 매월16(간선)-과기원 정류장 하차 / 첨단30(간선)-과기원 정류장 하차 중 택1 (60~90분 내외)
   
• 항공편 또는 고속버스 이용 시 단시간의 버스노선이 없으므로 택시 이용을 추천합니다.
  We recommend taking a taxi from the terminal when using an airplane or express bus. 

Organizing Committee

• Jeong Ok Choi, GIST
• Minki Kim, GIST
• Sangwook Kim, Chonnam National University
• Hong Liu, IBS

Host and Sponsers

• Extremal Combinatorics and Probability Group (ECOPRO), Institute for Basic Science (IBS)
• National Research Foundation or Korea (NRF)

Friday, 30 September

13:00 Registration

13:20 Opening

Session 1

Chair: Seunghyun Seo

1 New connections between numerical semigroups and integer partitions

Numerical semigroups are cofinite additive submonoids of the natural numbers motivated by the study of linear Diophantine equations. Through a simple injection to Young diagrams, researchers have used known results about numerical semigroups to answer questions about core partitions. In this talk, we will explore connection between integer partitions and numerical semigroups with a focus on classifying that appear in the image of the injection from numerical semigroups. This talk is based on joint work with Hannah Burson and Simone Sisneros-Thiry.

Speaker: Hayan Nam (Duksung Women’s University)

2 Intersective sets over abelian groups

Given a finite abelian group $G$ and a subset $J\subset G$ with $0\in J$, let $D_{G}(J,N)$ be the maximum size of $A\subset G^{N}$ such that the difference set $A-A$ and $J^{N}$ have no non-trivial intersection. Recently, this extremal problem has been studied for different groups $G$ and subsets $J$. For example, using the linear algebra methods, Alon showed the upper bound $D_{G}(J,N)\leq (p-1)^{N}$ when $G=\mathbb{F}_{p}$ and $J=\{0,1\}^{N}$. In this talk, I will introduce some improved upper bounds of $D_{G}(J,N)$ for several groups $G$ and subsets $J$.

Speaker: Zixiang Xu (IBS ECOPRO)

3 Reconfiguration of homomorphism extensions

For a graph H the reconfiguration/mixing versions of the extension problem for H asks, of a given graph G with a partial H-colouring p, if one can move between different homomorphisms extending p, by changing the image of one vertex at a time.

We characterise the graphs H for which one can do so for any choice of G and p and any pair of homomorphsims extending p.

We also consider the number of changes one must make, and apply the result to the shortest path reconfiguration problem.

Speaker: Mark Siggers (Kyungpook National University)

15:15 Coffee Break

Session 2

Chair: Sang June Lee

4 Introduction to DP-coloring

Graph coloring is one of the fundamental research topics in graph theory. Graph coloring is closely related with the Four Color Problem, and graph coloring is widely applied in a variety of applications. The aim of graph coloring is to minimize the number of colors used to color the vertices in a graph such that no two adjacent vertices have the same color.

DP-coloring was introduced by Dvo\v{r}\'{a}k and Postle (2015) to study list coloring. DP-coloring of a graph is a generalization of list coloring, and also a generalization of signed coloring of signed graphs. In this talk, we will give an overview of DP-coloring, and introduce online DP-coloring which is a online version of DP-coloring.

Speaker: Seog-Jin Kim (Konkuk University)

5 Reconstruction and Edge Reconstruction of Triangle-free Graphs

A graph is reconstructible if it can be uniquely determined, up to isomorphism, by its multiset of vertex-deleted subgraphs. The Reconstruction Conjecture of Kelly and Ulam states that every graph on $n\geq{3}$ vertices is reconstructible. Ramachandran and Monikandan showed that the Reconstruction Conjecture holds as long as every $2$-connected graph $G$ satisfying either $diam(G)=2$ or $diam(G)=diam(\bar{G})=3$ is reconstructible. Building on their work, we establish that all triangle-free graphs in the following families are reconstructible:

• Graphs with connectivity $3$ and diameter $2$.
• $2$-connected graphs $G$ with $diam(G)=diam(\bar{G})=3$.

We also establish slightly stronger results for the related Edge Reconstruction Conjecture.

Speaker: Alexander Clifton (IBS DIMAG)

6 On Entropy of graphs

Entropy is a concept and physical property that is associated with disorder or randomness. It is used in e.g. chemistry, cosmology, climate change and computer science.
Also in combinatorics, there are multiple types of entropy for graphs.
This light talk will first show that our intuition can guess extremal graphs in some base cases and end with some surprising behaviour for other cases.

This talk is based on joint work with Yanni Dong and Matteo Mazzamurro.

Speaker: Stijn Cambie

7 A unified proof of conjectures on cycle lengths in graphs

We prove a tight minimum degree condition in general graphs for the existence of paths between two given endpoints, whose lengths form a long arithmetic progression with common difference one or two. This allows us to obtain a number of exact and optimal results on cycle lengths in graphs of given minimum degree, connectivity or chromatic number.

This is joint work with Qingyi Huo, Chun-Hung Liu and Jie Ma.

Speaker: Jun Gao (ECOPRO in IBS)

18:00 Banquet

Saturday, 1 October

Session 3

Chair: Heesung Shin

8 Some new results on geometric transversals

The study of geometric transversals deals with generalizations of Helly's theorem. Instead of intersecting convex sets by points, we now wish to intersect convex sets by $k$-dimensional affine flats. The modern development of Helly type theorems (colorful, fractional, $(p,q)$ versions) has given rise to a number of new questions about general geometric transversals. In this talk I will survey some recent results and highlight some of the interesting problems in the area. This is based in part on joint work with Otfried Cheong and Xavier Goaoc.

Speaker: Andreas Holmsen (KAIST)

10:50 Coffee Break

9 Strong Erd\H{o}s-Hajnal property on chordal graphs and its variants

A graph class $\mathcal{G}$ has the strong EH(Erd\H{o}s-Hajnal) property if there is a constant $c=c(\mathcal{G}) > 0$ such that for every member $G$ of $\mathcal{G}$, either $G$ or its complement has $K_{m, m}$ as a subgraph where $m \geq c \left| V(G) \right|$. We prove that the chordal graphs satisfy strong Erd\H{o}s-Hajnal property with constant $c = 2/9$.

On the other hand, a strengthening of strong EH which we call the colorful strong EH property was discussed in geometric settings by Alon, Pach, Pinchasi, Radoi\v{c}i\'c, Sharir in 2005 and by Fox, Gromov, Lafforgue, Naor, Pach in 2012. Inspired by their results, we show that for every pair $\mathcal{F}_1, \mathcal{F}_2$ of subtree families of the same size in a tree with $k$ leaves, there exists subfamilies $\mathcal{F}'_1 \subseteq \mathcal{F}_1$ and $\mathcal{F}'_2 \subseteq \mathcal{F}_2$ of size $\frac{\ln k}{20 k} \left| \mathcal{F}_1 \right|$ such that either every pair of representatives from distinct subfamilies intersect or every such pair do not intersect.

Finally, we propose some questions on the intersection pattern of convex sets in terms of Erd\H{o}s-Hajnal type properties.

Speaker: Minho Cho (KAIST)

10 Stability version of Dirac's theorem and its applications for generalized Turán problems

In 1952, Dirac proved that every $2$-connected $n$-vertex graph with the minimum degree $k+1$ contains a cycle of length at least $\min\{n, 2(k+1)\}$. Here we obtain a stability version of this result by characterizing those graphs with minimum degree $k$ and circumference at most $2k+1$.

We present applications of the above-stated result by obtaining generalized Tur\'an numbers.
In particular, for all $\ell \geq 5$ we determine how many copies of a five-cycle as well as four-cycle are necessary to guarantee that the graph has a circumference larger than $\ell$.
In addition, we give new proof of Luo's Theorem for cliques using our stability result.

Speaker: Nika Salia (IBS Extremal Combinatorics and Probability Group)

12:05 Photo

12:30 Lunch

Session 4

Chair: Sejeong Bang

11 Chromatic quasisymmetric functions and linked rook placements

R. Stanley introduced the chromatic symmetric functions of a graph $G$. This definition was later refined by J. Shareshian and M. Wachs, where a parameter $q$ is introduced in the definition of chromatic uasisymmetric functions. In this talk, we discuss two separate results and their connection: (1) a Hall-Littlewood expansion of the chromatic quasisymmetric functions (2) $e$-positivity of the chromatic quasisymmetric functions when a partition $\lambda$ indexing the elementary symmetric function is a hook shape. To explain both results we introduce "linked" rook placements, where each column and row of a board contain at most one rook and some of rooks are linked. we also discuss other $e$-positivity results and relationship with LLT polynomials. (1) is based on joint work with Meesue Yoo and (2) is with Jeong Hyun Sung.

Speaker: Seung Jin Lee (Seoul National University)

12 $(q,t)$-analogues of $n!$ and $(n+1)^{n-1}$

The numbers $n!$ and $(n+1)^{n-1}$ are ubiquitous in combinatorics. Each number counts number of permutations and parking functions, respectively. I will discuss their $(q,t)$-generalizations and further generalization to symmetric functions, namely the modified Macdonald polynomials $\widetilde{H}_\mu$ and $\nabla e_n$. Then I will discuss a recent conjecture involving these two symmetric functions. Based on joint work with Donghyun Kim and Seung Jin Lee.

Speaker: Jaeseong Oh (Korea Institute for Advanced Study)

13 The proper conflict-free $k$-coloring problem and the odd $k$-coloring problem are NP-complete on bipartite graphs

A proper coloring of a graph is proper conflict-free if every non-isolated vertex $v$ has a neighbor whose color is unique in the neighborhood of $v$.
A proper coloring of a graph is odd if for every non-isolated vertex $v$, there is a color appearing an odd number of times in the neighborhood of $v$.
For an integer $k$, the PCF $k$-Coloring problem asks whether an input graph admits a proper conflict-free $k$-coloring and the Odd $k$-Coloring asks whether an input graph admits an odd $k$-coloring.
We show that for every integer $k\geq3$, both problems are NP-complete, even if the input graph is bipartite.
Furthermore, we show that the PCF $4$-Coloring problem is NP-complete when the input graph is planar.

Speaker: Mr Jungho Ahn (KAIST & IBS DIMAG)

16:00 Closing