Discrete Analysis & Insights Seminar at Yonsei
DAISY (Discrete Analysis & Insights Seminar at Yonsei) is a combinatorics seminar at Yonsei University. It is organized by students in the combinatorics group led by Prof. Joonkyung Lee. The seminar primarily focuses on topics in extremal combinatorics.
For more information, contact Jaehyeon Seo by jaehyeonseo@yonsei.ac.kr.
Upcoming event
(Feb 13, 2026)
Hyoyoon Lee, TBA
(Jan 26) Wonjung Park, On the average size of independent sets in triangle-free graphs
Shearer’s upper bound R(3, t)<=(1+o(1)) t^2 / log t has been a long-standing bound in extremal graph theory. This paper introduces a statistical physics approach, specifically the hard-core model, to analyze independent sets in triangle-free graphs. We discuss the result that the average size of independent sets under a specific fugacity is asymptotically equal to Shearer's bound for the maximum size.
📑 Ewan Davies, Matthew Jenssen, Will Perkins, and Barnaby Roberts, On the average size of independent sets in triangle-free graphs
(Jan 12) Jaehyeon Seo, Hypergraph container method.
We cover basics of hypergraph container method using examples including (1) maximum triangle-free subgraph of G(n,p) and (2) the number of n-vertex triangle-free graphs. We also prove the graph container lemma.
📝 Robert Morris, The method of hypergraph containers
📝 Yufei Zhao, Probabilistic Methods in Combinatorics: Containers
📑 József Balogh, Robert Morris, and Wojciech Samotij, The method of hypergraph containers
(Jan 4) Ingyu Baek, Minimum degree and the graph removal lemma. (paper by Jacob Fox and Yuval Wigderson)
A celebreated graph removal lemma is well-known to have a superpolynomial bound between quantifiers. This paper shows that under certain minimum degree condition, we can actually make the dependency linear. Furthermore, we also show that the prescribed minimum degree condition is tight.
(Dec 5) Ingyu Baek, A Van der Waerden free proof of Rado's theorem. (paper by Mauro Di Nasso and Lorenzo Luperi Baglini)
A well-known proof of the Rado's theorem relies on Van der Waerden theorem. Here we give an elementary proof of the Rado's theorem that does not require van der Waerden theorem in the proof.
(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
(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
(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
Regular Jaehyeon Seo, Jihyo Chae, Ingyu Baek, Jeewon Kim, Wonjung Park, Jae-baek Lee, Hyoyoon Lee, Changyeol Lee
Former Jisun Baek