[서울대학교 수리과학부 10-10 집중강연]  2/7 (화), 9 (목), 14 (화), 10:00AM - 12:00PM

 

장소: Zoom 강의실

https://snu-ac-kr.zoom.us/j/99324881376?pwd=NXR2MGZPWGVwbEM4TXgzOGFUb1VRQT09
회의 ID: 993 2488 1376
암호: 120745

 

초록: We will start with a mild introduction to random graph theory, focusing on threshold phenomena of increasing families. In general, for a finite set X, a family F of subsets of X is said to be increasing if any set A that contains B in F is also in F. The p-biased product measure of F increases as p increases from 0 to 1, and often exhibits a drastic change around a specific value, which is called a "threshold." Thresholds of increasing families have been of great historical interest and a central focus of the study of random discrete structures (e.g. random graphs and hypergraphs), with estimation of thresholds for specific properties the subject of some of the most challenging work in the area. In 2006, Jeff Kahn and Gil Kalai conjectured that a natural (and often easy to calculate) lower bound q(F) (which we refer to as the “expectation-threshold”) for the threshold is in fact never far from its actual value. A positive answer to this conjecture enables one to narrow down the location of thresholds for any increasing properties in a tiny window. In particular, this easily implies several previously very difficult results in probabilistic combinatorics such as thresholds for perfect hypergraph matchings (Johansson–Kahn–Vu) and bounded-degree spanning trees (Montgomery). We will discuss fascinating recent progress on this topic.