Discrete Analysis & Insights Seminar at Yonsei
DAISY (Discrete Analysis & Insights Seminar at Yonsei) is a seminar on combinatorics at Yonsei University. The participants are Jaehyeon Seo, Jihyo Chae, Ingyu Baek, Hyoyoon Lee, Changyeol Lee, and Jeewon Kim, most of whom are students of Joonkyung Lee. The seminar primarily focuses on topics in extremal combinatorics.
For more information, contact Jaehyeon by jaehyeonseo@yonsei.ac.kr.
Upcoming event
(KST 4:00 PM, Nov 20, 2025)
Changyeol Lee, Combinatorial discrepancy 2
2025
September–December
(Nov 20) Changyeol Lee, Combinatorial discrepancy 2.
Given a set system, our goal is to color each element red or blue so that the discrepancy—the maximum difference between reds and blues in any set—is minimized. In the last seminar, we achieved the best asymptotic discrepancy for arbitrary set systems using a partial coloring method, improving over random coloring. Today, we present an alternative proof via convex geometry and show how it can be extended to efficiently “find” a good coloring, overcoming a pigeonhole principle.
📕 Nikhil Bansal, Discrepancy theory and related algorithms
📑 Thomas Rothvoss, Constructive Discrepancy Minimization for Convex Sets
(Nov 14) Jeewon Kim, Nullstellensatz, Gröbner Basis, Graph Coloring.
A Gröbner basis is a generating set of a polynomial ideal that allows effective division algorithm and membership testing. We apply this framework to graph coloring by showing that a natural collection of coloring polynomials forms a universal Gröbner basis for the associated ideal. We also examine a basis theorem for graph polynomials of graphs with bounded independence number, which gives an algebraic proof of Turán’s theorem.
📑 Jesús A. de Loera, Gröbner bases and graph colorings
📑 Amir Hashemi and Zahra Ghaeli, A note on Gröbner bases and graph colorings
(Nov 7) Ingyu Baek, Improving R(3,k) in just two bites. (paper by Zion Hefty, Paul Horn, Dylan King, and Florian Pfender)
R(3,k) is the first non trivial Ramsey number. Although the asymptotic of Θ(k²/log k) is known, its coefficient is still unknown. This paper improves lower bound from the previous bound of (1/3+o(1))k²/log k to (1/2+o(1))k²/log k. In particular, this paper provides remarkably simple probabilistic methods compared with the other papers that gave the previously best bounds at the time.
(Oct 31) Jihyo Chae, A sparse canonical van der Waerden theorem and hypergraph container lemma, I.
We investigate the Ramsey-type result on a sparse random subset of [n]. In particular, we review the classical van der Waerden theorem and introduce the proof of showing the same property for p-random sets in [n] of size O(n^{k-1}). Additionally, we discuss the framework of the hypergraph container lemma from a bird's-eye view as an introduction to the next talk.
📑 José D. Alvarado, Yoshiharu Kohayakawa, Patrick Morris, Guilherme O. Mota, and Miquel Ortega, A sparse canonical van der Waerden theorem
(Sep 26) Jeewon Kim, Combinatorial Atlas.
We begin by revisiting Stanley’s proof of the log-concavity of certain sequences via the Alexandrov–Fenchel inequality for mixed volumes. From this perspective, we introduce the notion of a combinatorial atlas and show how it arises naturally in this setting. We then explore fundamental properties of combinatorial atlas and introduce an application to specific log-concave sequences.
📑 Swee Hong Chan and Igor Pak, Introduction to the combinatorial atlas
(Sep 21) Hyoyoon Lee, Erdős–Hajnal property for graphs of bounded VC-dimension.
A class of graphs said to have the Erdős–Hajnal property if there is a constant c such that every graph G in the class has a clique or anticlique of size |V(G)|^c. In 1977, Erdős and Hajnal conjectured that every proper hereditary graph class has the Erdős–Hajnal property. In this seminar, we fully understand the result of Nguyen, Scott, and Seymour, that every graph class of bounded VC-dimension has the Erdős–Hajnal property, which generalizes a wide range of earlier results.
📑 Tung Nguyen, Alex Scott, and Paul Seymour, Induced subgraph density. VI. Bounded VC-dimension
(Sep 11) Ingyu Baek, Sparse graph limits, entropy maximization and transitive graphs. (paper by Balázs Szegedy)
We study an information theoretic homomorphism density, which is a novel idea shown in the paper. Using information theoretic arguments and constructions, we followed the main contribution of this paper, which implies that in order to prove of disprove Sidorenko's conjecture, it is enough to show for the edge-vertex transitive target graphs.
(Sep 7) Jaehyeon Seo, Some log-concavity in combinatorics.
We study basics of the theory of Lorentzian polynomials, and explore one of its applications through a proof of Mason's conjecture. In addition, we briefly examine the combinatorial atlas and highlight its significance from its unique advantages.
📑 Petter Brändén, Unimodality, log-concavity, real-rootedness and beyond
📑 Petter Brändén and June Huh, Lorentzian polynomials
📑 Swee Hong Chan and Igor Pak, Introduction to the combinatorial atlas
January–August
(Aug 29) Changyeol Lee, Combinatorial discrepancy 1.
📕 Bernard Chazelle, The Discrepancy Method: Chapter 1, Combinatorial Discrepancy
📕 Noga Alon and Joel H. Spencer, The Probabilistic Method: Chapter 13, Discrepancy
(Aug 15) Jihyo Chae, Quasi-random subsets of Z_n. (paper by F. R. K. Chung and R. L. Graham)
(Jul 25) Jeewon Kim, Range of Permanent of Matrices.
📝 Jean-Sébastien Sereni and Martin Loebl, Graph Counting: Lecture 4
📑 DeVon Ingram and Alexander Razborov, On the Range of the Permanent of (±1)-Matrices
(Jul 11) Hyoyoon Lee, Ultra-strong regularity lemma for bounded VC-dimension graphs.
📑 Jacob Fox, János Pach, and Andrew Suk, Erdős–Hajnal conjecture for graphs with bounded VC-dimension
(Jul 4) Ingyu Baek, Probablistic coupling method.
📝 Sam Spiro, Methods in Extremal Combinatorics: Chapter 7, Coupling
📑 Oliver Riordan, Random cliques in random graphs and sharp thresholds for F-factors
(Jun 6) Jineon Baek, The Kahn–Kalai conjecture.
📑 Jinyoung Park and Huy Tuan Pham, A proof of the Kahn–Kalai conjecture
(May 23) Jisun Baek, Martingales and tight concentration.
📝 Joshua Erde, Probabilistic Methods in Combinatorics: Chapter 10, Martingales and Strong Concentration
(May 16) Jaehyeon Seo, Absorption method 2: The Rödl nibble.
📕 Noga Alon and Joel H. Spencer, The Probabilistic Method: Chapter 4, The Second Moment
📑 Dong Yeap Kang, Tom Kelly, Daniela Kühn, Abhishek Methuku, and Deryk Osthus, Graph and hypergraph colouring via nibble methods: A survey
(May 9) Changyeol Lee, Lovász Local Lemma.
📝 Yufei Zhao, Probabilistic Methods in Combinatorics: Lovász Local Lemma
(May 2) Jeewon Kim, Exponential Erdős–Szekeres theorem for matrices. (paper by Recep Altar Çiçeksiz, Zhihan Jin, Eero Räty, and István Tomon)
(Apr 11) Ingyu Baek, Equiangular lines with a fixed angle. (paper by Zilin Jiang, Jonathan Tidor, Yuan Yao, Shengtong Zhang, and Yufei Zhao)
(Mar 25) Hyoyoon Lee, The blow-up lemma. (paper by János Komlós, Gábor N. Sárközy, and Endre Szemerédi)
(Mar 21) Jaehyeon Seo, Absorption method 1: Basics and Montgomery’s template.
📑 Matija Bucić and Benny Sudakov, Tight Ramsey bounds for multiple copies of a graph
(Mar 14) Jihyo Chae, Entropy method and Turán's theorem.
📑 Ting-Wei Chao and Hung-Hsun Hans Yu, When entropy meets Turán: new proofs and hypergraph Turán results
(Mar 8) Jisun Baek, On the extremal number of incidence graphs. (paper by herself, David Conlon, and Joonkyung Lee)
(Feb 26) Ingyu Baek, The slice rank polynomial method.
📝 Lisa Sauermann, Algebraic Methods in Extremal Combinatorics (transcribed by Andrew Lin)
(Feb 14–15) Hyoyoon Lee, Applications of dependent random choice on Ramsey problems.
📕 Yusheng Li and Qizhong Lin, Elementary Methods of Graph Ramsey Theory: Chapter 9
(Jan 20, 31) Jihyo Chae and Jaehyeon Seo, On graph norms for complex-valued functions. (paper by Joonkyung Lee and Alexander Sidorenko)
(Jan 7) Jisun Baek, Algebraic methods.
📑 Boris Bukh and Ting-Wei Chao, Sharp density bounds on the finite field Kakeya problem
📑 Zeev Dvir, On the size of Kakeya sets in finite fields
2024
(Dec 30) Ingyu Baek, PRIMES is in P. (paper by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena)
(Nov 13) Jaehyeon Seo, On a conjecture of Marton. (paper by W. T. Gowers, Ben Green, Freddie Manners, and Terence Tao)
(Oct 29, Nov 5) Jihyo Chae and Hyoyoon Lee, Structure of Set Addition.
📕 Yufei Zhao, Graph Theory and Additive Combinatorics: Chapter 7
Former participants Jisun Baek