The 2024 Korean Student Combinatorics Workshop (KSCW2024, 2024 조합론 학생 워크샵) was held in Gongju from July 29 to August 2, 2024. Sponsored by the IBS Discrete Mathematics Group, this event aims to provide a platform for Korean graduate students working on combinatorics and related areas to establish a foundation for collaborative research. It was organized by four students of KAIST/IBS: Donggyu Kim (김동규), Seokbeom Kim (김석범), Seonghyuk Im (임성혁), and Hyunwoo Lee (이현우). The workshop featured two invited talks by Semin Yoo (유세민) and Jungho Ahn (안정호), as well as open problem sessions followed by ample time for joint work.
On July 5, 2024, Hyunwoo Lee (이현우) from KAIST and the IBS Extremal Combinatorics and Probability Group gave a talk at the Discrete Math Seminar on disproving Kahn’s conjecture (1995) on matchings in d-regular linear hypergraphs. The title of his talk was “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. In this paper, 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.
On November 28, Hyunwoo Lee (이현우) from KAIST and IBS Extremal Combinatorics and Probability Group gave a talk at the Discrete Math Seminar on the existence of a Steiner triple system in a 3-uniform hypergraph with large minimum codegree. The title of his talk was “Towards a high-dimensional Dirac’s theorem“.
Dirac’s theorem determines the sharp minimum degree threshold for graphs to contain perfect matchings and Hamiltonian cycles. There have been various attempts to generalize this theorem to hypergraphs with larger uniformity by considering hypergraph matchings and Hamiltonian cycles.
We consider another natural generalization of the perfect matchings, Steiner triple systems. As a Steiner triple system can be viewed as a partition of pairs of vertices, it is a natural high-dimensional analogue of a perfect matching in graphs.
We prove that for sufficiently large integer $n$ with $n \equiv 1 \text{ or } 3 \pmod{6},$ any $n$-vertex $3$-uniform hypergraph $H$ with minimum codegree at least $\left(\frac{3 + \sqrt{57}}{12} + o(1) \right)n = (0.879… + o(1))n$ contains a Steiner triple system. In fact, we prove a stronger statement by considering transversal Steiner triple systems in a collection of hypergraphs.
We conjecture that the number $\frac{3 + \sqrt{57}}{12}$ can be replaced with $\frac{3}{4}$ which would provide an asymptotically tight high-dimensional generalization of Dirac’s theorem.
On April 25, 2023, Hyunwoo Lee (이현우) from KAIST and IBS Extremal Combinatorics and Probability Group gave a talk at the Discrete Math Seminar about the minimum degree condition to have a partition of a graph into induced subgraphs each having a subdivision of a fixed graph as a subgraph. The title of his talk was “On perfect subdivision tilings.”
For a given graph $H$, we say that a graph $G$ has a perfect $H$-subdivision tiling if $G$ contains a collection of vertex-disjoint subdivisions of $H$ covering all vertices of $G.$ Let $\delta_{sub}(n, H)$ be the smallest integer $k$ such that any $n$-vertex graph $G$ with minimum degree at least $k$ has a perfect $H$-subdivision tiling. For every graph $H$, we asymptotically determined the value of $\delta_{sub}(n, H)$. More precisely, for every graph $H$ with at least one edge, there is a constant $1 < \xi^*(H)\leq 2$ such that $\delta_{sub}(n, H) = \left(1 - \frac{1}{\xi^*(H)} + o(1) \right)n$ if $H$ has a bipartite subdivision with two parts having different parities. Otherwise, the threshold depends on the parity of $n$.
