기초과학연구원 이산수학그룹
On January 11, 2024, Jinyoung Park (박진영) from NYU gave a talk at the Discrete Math Seminar on the number of antichains of subsets of an n-element set. The title of her talk was “Dedekind’s Problem and beyond“.
The Dedekind’s Problem asks the number of monotone Boolean functions, a(n), on n variables. Equivalently, a(n) is the number of antichains in the n-dimensional Boolean lattice $[2]^n$. While the exact formula for the Dedekind number a(n) is still unknown, its asymptotic formula has been well-studied. Since any subsets of a middle layer of the Boolean lattice is an antichain, the logarithm of a(n) is trivially bounded below by the size of the middle layer. In the 1960’s, Kleitman proved that this trivial lower bound is optimal in the logarithmic scale, and the actual asymptotics was also proved by Korshunov in 1980’s. In this talk, we will discuss recent developments on some variants of Dedekind’s Problem. Based on joint works with Matthew Jenssen, Alex Malekshahian, Michail Sarantis, and Prasad Tetali.
On July 18-19, 2022, Jinyoung Park (박진영) from Stanford University gave two talks on the proof of the Kahn-Kalai conjecture at the Discrete Math Seminar. The title of her talk was “thresholds“.
Thresholds for increasing properties of random structures are a central concern in probabilistic combinatorics and related areas. In 2006, Kahn and Kalai conjectured that for any nontrivial increasing property on a finite set, its threshold is never far from its “expectation-threshold,” which is a natural (and often easy to calculate) lower bound on the threshold.
In the first talk on Monday, I will introduce the Kahn-Kalai Conjecture with some motivating examples and then briefly talk about the recent resolution of the Kahn-Kalai Conjecture due to Huy Pham and myself.
In the second talk on Tuesday, I will discuss our proof of the conjecture in detail.
Thresholds for increasing properties of random structures are a central concern in probabilistic combinatorics and related areas. In 2006, Kahn and Kalai conjectured that for any nontrivial increasing property on a finite set, its threshold is never far from its “expectation-threshold,” which is a natural (and often easy to calculate) lower bound on the threshold.
In the first talk on Monday, I will introduce the Kahn-Kalai Conjecture with some motivating examples and then briefly talk about the recent resolution of the Kahn-Kalai Conjecture due to Huy Pham and myself.
In the second talk on Tuesday, I will discuss our proof of the conjecture in detail.
A special session “Extremal and Probabilistic Combinatorics” at the 2021 KMS Spring Meeting is organized by Tuan Tran.
URL: https://www.kms.or.kr/meetings/spring2021/
All talks are on April 30.
Graph saturation is one of the oldest areas of investigation in extremal combinatorics. A graph G is called F-saturated if G does not contain a subgraph isomorphic to F, but the addition of any edge creates a copy of F. We resolve one of the most fundamental questions of minimizing the number of cliques of size r in a $K_s$-saturated graph for all sufficiently large numbers of vertices, confirming a conjecture of Kritschgau, Methuku, Tait and Timmons. We further prove a corresponding stability result. This talk will be based on joint work with Po-Shen Loh.
The Oberwolfach problem, posed by Ringel in 1967, asks for a decomposition of $K_{2n+1}$ into edge-disjoint copies of a given 2-factor. We show that this can be achieved for all large n. We actually prove a significantly more general result, which allows for decompositions into more general types of factors.
A hypergraph is linear if every pair of two distinct edges shares at most one vertex. A longstanding conjecture by Erdős, Faber, and Lovász in 1972, states that the chromatic index of any linear hypergraph on n vertices is at most n.
In this talk, I will present the ideas to prove the conjecture for all large n. This is joint work with Tom Kelly, Daniela Kühn, Abhishek Methuku, and Deryk Osthus.
Majority dynamics on a graph G is a deterministic process such that every vertex updates its {-1,1}-assignment according to the majority assignment on its neighbor simultaneously at each step. Benjamini, Chan, O’Donnell, Tamuz and Tan conjectured that, in the Erdős-Rényi random graph G(n,p), the random initial {-1,1}-assignment converges to the unanimity with high probability whenever p>> 1/n.
This conjecture was firstly confirmed for $p>Cn^{-1/2}$ for a large constant C>0 by Fountoulakis, Kang and Makai. Although this result has been reproved recently by Tran and Vu and by Berkowitz and Devlin, none of them managed to extend it beyond the barrier $p>Cn^{-1/2}$. We prove the conjecture for sparser random graphs G(n,p), where $Dn^{-3/5}\log n < p < C n^{-1/2}$ with a large constant D>0.
Joint work with Debsoumya Chakraborti, Jeong Han Kim and Tuan Tran.
I will review the history of sublinear expander and present some recent applications, which lead to resolutions of several long-standing problems in sparse graphs embeddings.
We will talk about a recent result of Jeff Kahn, Bhargav Narayanan, and myself stating that the threshold for the random graph G(n,p) to contain the square of a Hamilton cycle is $1/\sqrt n$, resolving a conjecture of Kühn and Osthus from 2012. The proof idea is motivated by the recent work of Frankston and the three aforementioned authors on a conjecture of Talagrand — “a fractional version of Kahn-Kalai expectation threshold conjecture.”
On August 24, Monday, the 2020 Combinatorics Workshop (2020 조합론 학술대회) was held online due to the COVID-19 pandemic. This local workshop series began in 2004 and has been continued to be one of the biggest annual gathering of people in combinatorics located in Korea. Due to the COVID-19 pandemic, it has been reduced to a one-day online conference on Zoom. It was hosted by Kyung Hee University and IBS Discrete Mathematics Group.
The workshop website: https://cw2020.combinatorics.kr
Combinatorics Workshop (조합론 학술대회) is the biggest annual conference in combinatorics in Korea. It was firstly held in 2004 by the Yonsei University BK21 Research Group. It has been advised by the committee of discrete mathematics of the Korean Mathematical Society since 2013. The aim of this workshop is to bring active researchers with different backgrounds to discuss recent and prospective advances in combinatorics and related areas.
Originally, we planned an offline workshop. However, COVID 19 is more spreading and many participants are worried about attending an offline conference. So the schedule and venue are changed as an online workshop with Zoom. I hope that all participants generously understand this sudden change.
More information is available on the website https://cw2020.combinatorics.kr.
On June 3, 2019, Jinyoung Park (박진영) from Rutgers University, USA presented her joint work with Jeff Kahn on the number of maximal independent sets in the hypercube graph at the Discrete Math Seminar. The title of her talk was “The maximal independent sets in the Hamming cube“.
Let $Q_n$ be the $n$-dimensional Hamming cube (hypercube) and $N=2^n$. We prove that the number of maximal independent sets in $Q_n$ is asymptotically $2n2^{N/4}$, as was conjectured by Ilinca and Kahn in connection with a question of Duffus, Frankl and Rödl. The value is a natural lower bound derived from a connection between maximal independent sets and induced matchings. The proof of the upper bound draws on various tools, among them “stability” results for maximal independent set counts and old and new results on isoperimetric behavior in $Q_n$. This is joint work with Jeff Kahn.