- This event has passed.
IBS ECOPRO Opening Conference
April 4, 2022 @ 7:15 pm - April 6, 2022 @ 10:15 pm
Zoom ID: 878 0445 3986 (ibsecopro)
To celebrate the opening of the IBS ECOPRO (Extremal Combinatorics and Probability) Group, we will organize a 3-day online conference from April 4 to April 6.
Invited Speakers
Noga Alon
Princeton University
József Balogh
University of Illinois at Urbana-Champaign
Jeff Kahn
Rutgers University
Mihyun Kang
Graz University of Technology
Jeong Han Kim
KIAS
Nati Linial
Hebrew University of Jerusalem
Program
| Time in Korea | Monday | Tuesday | Wednesday |
|---|---|---|---|
| 7:15 PM | Kim | ||
| 8:00 PM | Pikhurko | Kang | Vu |
| 8:45 PM | Kahn | Balogh | Szabó |
| 9:30 PM | Alon | Sudakov | Linial |
Time zone: South Korea/ Central Europe/ New York
Abstracts in PDF
Day 1: April 4 Monday
Jeong Han Kim, 7:15-8:00pm/12:15-1:00pm/6:15-7:00am
Majority dynamics on sparse random graphs
Majority dynamics on a graph $G$ is a deterministic process such that every vertex updates its $\pm 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\H{o}s–R\’enyi random graph $G(n,p)$, the random initial $\pm 1$-assignment converges to a $99\%$-agreement with high probability whenever $p=\omega(1/n)$. This conjecture was first confirmed for $p\geq\lambda n^{-1/2}$ for a large constant $\lambda$ by Fountoulakis, Kang and Makai. Although this result has been reproved recently by Tran and Vu and by Berkowitz and Devlin, it was unknown whether the conjecture holds for $p< \lambda n^{-1/2}$. We break this $\Omega(n^{-1/2})$-barrier by proving the conjecture for sparser random graphs $G(n,p)$, where $\lambda’ n^{-3/5}\log n \leq p \leq \lambda n^{-1/2}$ with a large constant $\lambda’>0$.Oleg Pikhurko, 8:00-8:45pm/1:00-1:45pm/7:00-7:45am
Moser-Tardos Algorithm with small number of random bits
We present a variant of the parallel Moser-Tardos Algorithm for the variable version of the Lovász Local Lemma and show that, for a class of problems whose dependency graphs have uniform subexponential growth, the expected number of random bits used by the algorithm is constant. In particular the expected number of used random bits is independent from the total number of variables. This is achieved by using the same random bits to resample variables which are far enough in the dependency graph. Joint work with E.Csoka, L.Grabowski, A.Mathe and K.Tyros.Jeff Kahn, 8:45-9:30pm/1:45-2:30pm/7:45-8:30am
Linear cover time is exponentially unlikely
Proving a 2009 conjecture of Itai Benjamini, we show: For any $C$ there is $c > 0$ so that for any simple random walk on an $n$-vertex graph $G$, the probability that the first $Cn$ steps of the walk see every vertex is less than $\exp(-cn)$. A first ingredient in the proof of this is a similar statement for Markov chains in which all transition probabilities are less than a suitable function of $C$. Joint with Quentin Dubroff.Noga Alon, 9:30-10:15pm/2:30-3:15pm/8:30-9:15am
Random processes of graphs and permutations
The vertex random graph process (with parameter $p=1/2$) is a variant of the random graph process initiated by Erdos and Renyi. This is an infinite sequence of random graphs $G_i$ defined as follows. $G_1$ is the graph with one vertex, and for each $i$, $G_{i+1}$ is obtained from $G_i$ by adding to it a new vertex adjacent to each of the previous ones, randomly and independently, with probability $p=1/2$. This process arises naturally when studying the smallest possible number of vertices of a graph which contains every graph on n vertices as an induced subgraph – a problem first studied by Moon in the 60s, which received a considerable amount of attention over the years. A similar random process exists for permutations and arises in the study of the smallest possible length of a permutation that contains every permutation of size n, as well as in the investigation of additional problems for random permutations. I will discuss these two models and describe several results and problems including a solution of Moon’s problem and a detailed analysis, obtained jointly with Dor Elboim and Allan Sly, of a problem of Georgiou, Katkov and Tsodyks about the random permutation process.Day 2: April 5 Tuesday
Mihyun Kang, 8:00-8:45pm/1:00-1:45pm/7:00-7:45am
Random subgraphs of the hypercube
We consider a random subgraph of the hypercube in the supercritical regime. We derive vertex-expansion properties of the giant component. As a consequence we determine the diameter of the giant component and the mixing time of the lazy random walk on the giant component. We also obtain lower bounds on the circumference and Hadwiger number. This talk is based on joint work with Joshua Erde and Michael Krivelevich.József Balogh, 8:45-9:30pm/1:45-2:30pm/7:45-8:30am
On Robustness of The Erdős-Ko-Rado Theorem
A family of subsets of $[n]$ is intersecting if every pair of its sets intersects. Determining the structure of large intersecting families is a central problem in extremal combinatorics, starting with the well-known Erdos-Ko-Rado Theorem. We consider two extensions of it: Counting variant: Frankl-Kupavskii and Balogh-Das-Liu-Sharifzadeh-Tran showed that for $n\geq 2k + c\sqrt{k\ln k}$, almost all $k$-uniform intersecting families are stars. Improving their result, we show that the same conclusion holds for $n\geq 2k+ 100\ln k$. Random variant: For positive integers $n$ and $k$ with $n\geq 2k+1$, the Kneser graph $K(n,k)$ is the graph with vertex set consisting of all $k$-sets of $\{1,\dots,n\}$, where two $k$-sets are adjacent exactly when they are disjoint. Let $K_p(n,k)$ be a random spanning subgraph of $K(n,k)$ where each edge is included independently with probability $p$. Bollobás, Narayanan, and Raigorodskii asked for what $p$ does $K_p(n,k)$ have the same independence number as $K(n,k)$ with high probability. Building on work of Das and Tran and of Devlin and Kahn, we resolve this question. Our proofs uses, among others, the graph container method and the Das-Tran removal lemma. It is joint work with Lina Li, Ramon Garcia, Adam Wagner; and with Robert Krueger and Haoran Luo.Benny Sudakov, 9:30-10:15pm/2:30-3:15pm/8:30-9:15am
Short proofs of rainbow matching results
A subgraph of an edge-coloured graph is called rainbow if all its edges have distinct colors. The study of rainbow subgraphs goes back to the work of Euler on Latin squares and has been the focus of extensive research ever since. Many conjectures in this area roughly say that “every edge coloured graph of a certain type contains a rainbow matching using every color”. In this talk we describe a versatile “sampling trick”, which allows us to obtain short proofs of old results as well as to solve asymptotically some well known conjectures. This will answer questions by Alspach, Aharoni, Berger and Grinblat. Joint work with D. Munha Correia and A. Pokrovskiy.Day 3: April 6 Wednesday
Van Vu, 8:00-8:45pm/1:00-1:45pm/7:00-7:45am
Majority dynamics on a random graph: The power of few
A community of $n$ individuals splits into two camps, Red and Blue. The individuals are connected by a social network, which influences their colors. Everyday, people can choose to go online to observe some of their friends and alter their affiliations based on their observation. Red (Blue) wins if everyone in the community becomes Red (Blue) at some point. We are going to survey recent results concerning this process when the underlying network is the random Erdős-Renyi graph $G(n, p)$, with a few variants in how individuals observe each other. In particular, we will discuss the “Power of Few” phenomenon, which asserts that in a dense graph, a camp with only few more people already wins with probability close to 1. For instance, 7 people guarantees a win with probability over 90%, as far as $n$ is at least 600.Tibor Szabó, 8:45-9:30pm/1:45-2:30pm/7:45-8:30am
Topology at the North Pole
In the max-min allocation problem a set P of players are to be allocated disjoint subsets of a set R of indivisible resources, such that the minimum utility among all players is maximized. We study the restricted variant, also known as the Santa Claus problem, where each resource has an intrinsic positive value, and each player covets a subset of the resources. Bezakova and Dani showed that this problem is NP-hard to approximate within a factor less than 2, consequently a great deal of work has focused on approximate solutions. The principal approach for obtaining approximation algorithms has been via the Configuration LP (CLP) of Bansal and Sviridenko. Accordingly, there has been much interest in bounding the integrality gap of this CLP. The existing algorithms and integrality gap estimations are all based one way or another on the combinatorial augmenting tree argument of Haxell for finding perfect matchings in certain hypergraphs. Here we introduce the use of topological tools for the restricted max-min allocation problem. This approach yields substantial improvements in the integrality gap of the CLP. In particular we improve the previously best known bound of 3.808 to 3.534. The talk represents joint work with Penny Haxell.Nati Linial, 9:30-10:15pm/2:30-3:15pm/8:30-9:15am
Geodesic Geometry of Graphs
A path system $P$ in a graph $G$ is a collection of paths, one per each pair of vertices in $G$. Such a system is said to be consistent if it is closed under taking subpaths. Namely if the chosen path from $u$ to $v$ goes through the vertex $x$, then it is the concatenation of the chosen $ux$ path and the chosen $xv$ path. There is a simple way to generate a consistent path system in $G$: Assign a positive weight $w(e)$ to every edge $e$ and put in $P$ all the shortest paths. Such a system is said to be metrical. Question: Is every consistent path system metrical? Our main findings: (1) The vast majority of graphs carry nonmetrical consistent path systems, (2) In every outerplanar graph every consistent path system is metrical, (3) There is a polynomial-time algorithm to decide if a given graph carries any non-metrical consistent path system. Joint work with my student Daniel Cizman.Organizers
- Jaehoon Kim, KAIST
- Hong Liu, IBS Extremal Combinatorics and Probability Group
- Sang-il Oum, IBS Discrete Mathematics Group / KAIST
- Tuan Tran, IBS Discrete Mathematics Group