The Gwangju Combinatorics Seminar is a joint seminar series hosted by combinatorics groups in Chonnam National University and GIST, exploring recent research trends and mathematical ideas in various fields such as discrete mathematics, combinatorics, and graph theory.
This is the first talk of Gwangju Combinatorics Seminar. Bijective proof is an essential tool in discrete mathematics. In many instances, finding a suitable bijection is a key step of a proof.This talk introduces combinatorial bijections used to prove some properties of derangements, set partitions and pattern avoiding permutations.
We prove that for any circle graph H with at least one edge and for any positive integer k, there exists an integer t = t(k, H) such that every graph G either has a vertex-minor isomorphic to the disjoint union of k copies of H, or has a t-perturbation with no vertex-minor isomorphic to H.
Using the same techniques, we also prove that for any planar multigraph H, every binary matroid either has a minor isomorphic to the cycle matroid of kH, or is a low-rank perturbation of a binary matroid with no minor isomorphic to the cycle matroid of H.
This is joint work with Rutger Campbell, J. Pascal Gollin, Meike Hatzel, O-joung Kwon, Rose McCarty, and Sebastian Wiederrecht.
In 1981, Füredi and Komlós established an upper bound for the spectral norm of random weighted graphs whose edge weights are independent (though not necessarily identically distributed) real-valued bounded random variables. In 2005, Vu further sharpened this result.
In this work, we obtain analogous upper bounds in the case where the weights are not necessarily bounded, but their s-moments are uniformly bounded for some s > 4. As an application, we show that Brouwer’s conjecture holds for such random weighted graphs.
The rectilinear crossing number is the minimum number of edge crossings in a straight-line drawing of a graph in the plane. Despite its elementary definition, even the case of complete graphs remains poorly understood, and progress over the past several decades has relied on a blend of geometric intuition, combinatorial reasoning, and increasingly sophisticated computational methods.
In this talk, I will present a progress report on an attempt to use artificial intelligence as a new exploratory tool for this classical problem. After briefly surveying the history of the rectilinear crossing number and its known constructions, I will introduce OpenEvolve, an open-source framework inspired by AlphaEvolve, which has recently been applied to the study of mathematical conjectures. I will describe the framework at a high level and explain how it can be adapted to the rectilinear crossing number. I will then discuss results from this ongoing work. OpenEvolve was able to rediscover known optimal constructions for small complete graphs, and for a larger instance it was able to produce drawings whose crossing numbers are within 99.98% of the best known upper bound. I conclude by reflecting on the potential role of AI-assisted exploration in mathematics.
In 1990, Kostochka and Sidorenko introduced the List Color Function, which counts the guaranteed number of list colorings of a given graph, as a counterpart to the classic Chromatic Polynomial, introduced by Birkhoff in 1912, which counts its ordinary colorings. They asked whether the List Color Function asymptotically equals the Chromatic Polynomial when the number of colors is large enough. This was proved by Donner (1992) with several major improvements appearing till now. This phenomenon has been widely studied in the context of generalizations of ordinary colorings. In this talk, we will discuss the history as well as some new results on this theme of Kostochka and Sidorenko: an enumerative function of (a variant of) list colorings equals the corresponding enumerative function of (the same variant of) ordinary colorings, when the number of colors is large enough. Along the way, we will see how combinatorial, algebraic, and analytic thinking comes together in the study of this graph theory problem.
Strongly regular graphs (SRGs) are one of the most interesting objects in spectral graph theory. A graph $G$ is an SRG with parameters $(n,k,\lambda,\mu)$ if it is a $k$-regular graph on $n$ vertices, every two adjacent vertices have exactly $\lambda$ common neighbours, and every two non-adjacent vertices have exactly $\mu$ common neighbours. The smallest example is the pentagon $C_5$, with parameters $(5,2,0,1)$. This symmetric condition means that an SRG always has only three distinct eigenvalues. But even with this simple description, finding new examples of SRGs is still hard, and it seems that more structural information is needed to construct them. This leads us to another matrix of a graph: the distance matrix.
The entries of the distance matrix of a connected graph are defined as the length of a shortest path between each pair of vertices. It has been studied more in applied fields such as chemistry and engineering than in mathematics. For example, it is used in chemistry as the Wiener index, to predict physical properties such as the boiling points of molecules.
In this talk, we discuss graphs whose distance matrix has exactly three distinct eigenvalues.
This is joint work with J. Koolen(USTC), J. Park(KNU) and H. Ge(USTC).
Understanding the intersection patterns of geometric objects is a fundamental topic in discrete geometry. In particular, extensive research has centered around geometric intersection theorems: Helly-type theorems for understanding local-to-global intersection patterns of convex sets, and Tverberg-type theorems for intersecting convex hulls in point partitions.
The original Helly's theorem states that a finite family of convex sets in d-dimensional Euclidean space has a common intersection if every d+1 members have a non-empty intersection. Combinatorially, this has inspired numerous variants and generalizations such as fractional, colorful, and quantitative versions. On the other hand, replacing geometric convexity with abstract convexity naturally leads to topological combinatorics. Specifically, characterizing when Helly-type theorems hold has motivated approaches from algebraic topology based on homology and Betti numbers.
Tverberg's theorem asserts that every sufficiently large point set in d-dimensional Euclidean space can be partitioned so that the convex hulls of the parts intersect. Interestingly, Tverberg's theorem can be obtained from the colorful Helly theorem. However, it has a different topological aspect. Viewing the convex hull as the image under an affine map from a simplex, extending Tverberg's theorem from affine to continuous maps connects directly to combinatorial topology through the Borsuk-Ulam theorem.
In this talk, we provide an overview of research in geometric and topological combinatorics with a focus on intersection patterns.
TBA
TBA
[GIST Math Colloquium]
Sep 26 (Fri), 2025 13:00~14:00 Joonkyung Lee (Yonsei Univ)
Log-concavity in combinatorics
Log-concavity of discrete sequences often translates into intriguing negative correlations in random discrete structures. I will describe various examples that illustrate this phenomenon, ranging from classical to modern ones. If time permits, I will also discuss June E Huh's recent work on Lorentzian polynomials and how it applies to graph colouring problems, in connection with my own work with Jaeseong Oh and Jaehyeon Seo.
Nov 07 (Fri), 2025 13:00~14:00 Jangsoo Kim (SKKU)
Combinatorics of orthogonal polynomials
Orthogonal polynomials are classical objects arising from the study of continued fractions. Due to the long history of orthogonal polynomials, they have now become important objects of study in many areas: classical analysis and PDE, mathematical physics, probability, random matrix theory, and combinatorics. The combinatorial study of orthogonal polynomials was pioneered by Flajolet and Viennot in the 1980s. In this talk, we study fascinating combinatorial properties of orthogonal polynomials.
TBA