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.
[GIST Math Colloquium]
Sep 26 (Fri) 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) 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.