BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Extremal Combinatorics and Probability Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-ORIGINAL-URL:https://www.ibs.re.kr/ecopro
X-WR-CALDESC:Events for Extremal Combinatorics and Probability Group
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:20210101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;VALUE=DATE:20231020
DTEND;VALUE=DATE:20231024
DTSTAMP:20260507T083330
CREATED:20231014T085134Z
LAST-MODIFIED:20231014T085134Z
UID:4208-1697760000-1698105599@www.ibs.re.kr
SUMMARY:3rd Developments in Combinatorics workshop 2023
DESCRIPTION:Please see the workshop homepage for more details: https://www.ibs.re.kr/ecopro/development-in-combinatorics-3rd-workshop-2023/
URL:https://www.ibs.re.kr/ecopro/event/3rd-developments-in-combinatorics-workshop-2023/
CATEGORIES:Workshops and Conferences
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20221128T153000
DTEND;TZID=Asia/Seoul:20221129T190000
DTSTAMP:20260507T083330
CREATED:20221122T133353Z
LAST-MODIFIED:20221122T140741Z
UID:3488-1669649400-1669748400@www.ibs.re.kr
SUMMARY:Online Workshop "Developments in Combinatorics" 2022
DESCRIPTION:The workshop information can be found at: https://www.ibs.re.kr/ecopro/online-workshop-developments-in-combinatorics/
URL:https://www.ibs.re.kr/ecopro/event/online-workshop-developments-in-combinatorics-2022/
LOCATION:Zoom: 346 934 4087 (202209)
CATEGORIES:Workshops and Conferences
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220930T130000
DTEND;TZID=Asia/Seoul:20221001T180000
DTSTAMP:20260507T083330
CREATED:20220927T064159Z
LAST-MODIFIED:20220927T064406Z
UID:3206-1664542800-1664647200@www.ibs.re.kr
SUMMARY:2022 Combinatorics Workshop at GIST
DESCRIPTION:For schedules of invited/contributed talks\, see workshop homepage: https://indico.ibs.re.kr/e/cw2022 \nInvited Speakers\n\nAndeas Holmsen\, KAIST\nSome new results on geometric transversals\nSeog-jin Kim\, Konkuk University\nIntroduction to DP-coloring\nSeung Jin Lee\, Seoul National University\nChromatic quasisymmetric functions and linked rook placements\nHayan Nam\, Duksung Women’s University\nNew connections between numerical semigroups and integer partitions\n\nOrganizing Committee\n\nJeong Ok Choi\, GIST\nMinki Kim\, GIST\nSangwook Kim\, Chonnam National University\nHong Liu\, IBS ECOPRO\n\n 
URL:https://www.ibs.re.kr/ecopro/event/2022-combinatorics-workshop-at-gist/
CATEGORIES:Workshops and Conferences
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220404T191500
DTEND;TZID=Asia/Seoul:20220406T221500
DTSTAMP:20260507T083330
CREATED:20220214T093717Z
LAST-MODIFIED:20220326T062156Z
UID:2081-1649099700-1649283300@www.ibs.re.kr
SUMMARY:IBS ECOPRO Opening Conference
DESCRIPTION: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. \nConference Poster \nInvited Speakers\n\n\n\n\n\n\n\n\n\nNoga AlonPrinceton University \n\n\n\n\n\n\n\n\n\n\n\nJózsef BaloghUniversity of Illinois at Urbana-Champaign \n\n\n\n\n\n\n\n\n\n\n\nJeff KahnRutgers University \n\n\n\n\n\n\n\n\n\n\n\n\n\nMihyun KangGraz University of Technology \n\n\n\n\n\n\n\n\n\n\n\nJeong Han KimKIAS \n\n\n\n\n\n\n\n\n\n\n\nNati LinialHebrew University of Jerusalem \n\n\n\n\n\n\n\n\n\n\n\n\n\nOleg PikhurkoUniversity of Warwick \n\n\n\n\n\n\n\n\n\n\n\nBenny SudakovETH Zürich \n\n\n\n\n\n\n\n\n\n\n\nTibor SzabóFreie Universität Berlin \n\n\n\n\n\n\n\n\n\n\n\n\n\nVan VuYale \n\n\n\n\n\n  \n\n\n\n\n\n  \n\n\n\n\n\nProgram\n\n\n\n\n\nTime in Korea\nMonday\nTuesday\nWednesday\n\n\n\n\n7:15 PM\nKim\n \n \n\n\n8:00 PM\nPikhurko\nKang\nVu\n\n\n8:45 PM\nKahn\nBalogh\nSzabó\n\n\n9:30 PM\nAlon\nSudakov\nLinial\n\n\n\n\n\n  \nTime zone: South Korea/ Central Europe/ New York Abstracts in PDF \nDay 1: April 4 Monday\n\nJeong Han Kim\, 7:15-8:00pm/12:15-1:00pm/6:15-7:00amMajority dynamics on sparse random graphs\nMajority 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$.\nOleg Pikhurko\, 8:00-8:45pm/1:00-1:45pm/7:00-7:45amMoser-Tardos Algorithm with small number of random bits\nWe 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.\nJeff Kahn\, 8:45-9:30pm/1:45-2:30pm/7:45-8:30amLinear cover time is exponentially unlikely\nProving 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.\nNoga Alon\, 9:30-10:15pm/2:30-3:15pm/8:30-9:15am Random processes of graphs and permutations\nThe 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.\nDay 2: April 5 Tuesday\n\nMihyun Kang\, 8:00-8:45pm/1:00-1:45pm/7:00-7:45amRandom subgraphs of the hypercube\nWe 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.\nJózsef Balogh\, 8:45-9:30pm/1:45-2:30pm/7:45-8:30amOn Robustness of The Erdős-Ko-Rado Theorem\nA 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.\nBenny Sudakov\, 9:30-10:15pm/2:30-3:15pm/8:30-9:15amShort proofs of rainbow matching results\nA 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.\nDay 3: April 6 Wednesday\n\nVan Vu\, 8:00-8:45pm/1:00-1:45pm/7:00-7:45amMajority dynamics on a random graph: The power of few\nA 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.\nTibor Szabó\, 8:45-9:30pm/1:45-2:30pm/7:45-8:30amTopology at the North Pole\nIn 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.\nNati Linial\, 9:30-10:15pm/2:30-3:15pm/8:30-9:15amGeodesic Geometry of Graphs\nA 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.\nOrganizers\n\nJaehoon Kim\, KAIST\nHong Liu\, IBS Extremal Combinatorics and Probability Group\nSang-il Oum\, IBS Discrete Mathematics Group / KAIST\nTuan Tran\, IBS Discrete Mathematics Group
URL:https://www.ibs.re.kr/ecopro/event/opening/
LOCATION:Zoom ID: 878 0445 3986 (ibsecopro)
CATEGORIES:Workshops and Conferences
ATTACH;FMTTYPE=image/png:https://www.ibs.re.kr/ecopro/wp-content/uploads/2022/02/opening-conferece-e1648275320377.png
END:VEVENT
END:VCALENDAR