BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Alexey Pokrovskiy (University College London)
DTSTART:20200923T090000Z
DTEND:20200923T095500Z
DTSTAMP:20260422T212709Z
UID:probabilisticcombinatorics/1
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/probabilisti
 ccombinatorics/1/">Rota's basis conjecture holds asymptotically</a>\nby Al
 exey Pokrovskiy (University College London) as part of Probabilistic Combi
 natorics Online 2020\n\n\nAbstract\nRota's Basis Conjecture is a well know
 n problem\, that states that for any collection of $n$ bases in a rank $n$
  matroid\, it is possible to decompose all the elements into $n$ disjoint 
 rainbow bases. Here an asymptotic version of this is will be discussed - t
 hat it is possible to find $n-o(n)$ disjoint rainbow independent sets of s
 ize $n-o(n)$.\n
LOCATION:https://researchseminars.org/talk/probabilisticcombinatorics/1/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Brendan McKay (Australian National University)
DTSTART:20200923T100000Z
DTEND:20200923T105500Z
DTSTAMP:20260422T212709Z
UID:probabilisticcombinatorics/2
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/probabilisti
 ccombinatorics/2/">Some remarks on the method of switchings</a>\nby Brenda
 n McKay (Australian National University) as part of Probabilistic Combinat
 orics Online 2020\n\n\nAbstract\nThe method of switchings has become a sta
 ndard tool for combinatorial enumeration and probability problems. We will
  discuss some old and new applications and techniques. First\, we discuss 
 how switchings make a very general tool for bounding upper tails of distri
 butions. Second\, we illustrate how switchings can be used to study subgra
 phs of random graphs. Finally\, we enumerate linear hypergraphs with a giv
 en number of edges.\n
LOCATION:https://researchseminars.org/talk/probabilisticcombinatorics/2/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Nicholas Wormald (Monash University)
DTSTART:20200923T110000Z
DTEND:20200923T112500Z
DTSTAMP:20260422T212709Z
UID:probabilisticcombinatorics/3
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/probabilisti
 ccombinatorics/3/">Fast uniform generation of regular graphs and contingen
 cy tables</a>\nby Nicholas Wormald (Monash University) as part of Probabil
 istic Combinatorics Online 2020\n\n\nAbstract\nWe present a new technique 
 for use in switching-based random generation of graphs with given degrees.
  For graphs with m edges and maximum degree $D=O(m^4)$\, the `best' existi
 ng uniform sampler\, given by McKay and Wormald in 1990\, runs in time $O(
 m^2D^2)$. Our new one runs in time $O(m)$\, which is effectively optimal. 
 For $d$-regular graphs with $d =o(\\sqrt n)$\, the best existing ones run 
 in time $O(nd^3)$. This is now improved  to $O(nd+d^4)$. Similar results a
 re obtained for generating random contingency tables with given marginals 
 (equivalently\, bipartite multigraphs with given degree sequence) in the s
 parse case.  \n\nThis is joint work with  Andrii Arman and Jane Gao.\n
LOCATION:https://researchseminars.org/talk/probabilisticcombinatorics/3/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Benjamin Sudakov (ETH Zürich)
DTSTART:20200923T130000Z
DTEND:20200923T135500Z
DTSTAMP:20260422T212709Z
UID:probabilisticcombinatorics/4
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/probabilisti
 ccombinatorics/4/">Large independent sets from local considerations</a>\nb
 y Benjamin Sudakov (ETH Zürich) as part of Probabilistic Combinatorics On
 line 2020\n\n\nAbstract\nHow  well  can  global  properties  of  a  graph 
  be  inferred  from  observations that  are  purely local?  This  general 
  question  gives  rise  to  numerous  interesting problems. One such very 
 natural question was raised independently by Erdos-Hajnal and Linial-Rabin
 ovich in the early 90's. How large must the independence number $\\alpha(G
 )$ of a graph $G$ be whose every $m$ vertices contain an independent set o
 f size $r$? In this talk we discuss new methods to attack this problem whi
 ch improve many previous results.\n\nJoint work with Matija Bucic\n
LOCATION:https://researchseminars.org/talk/probabilisticcombinatorics/4/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pawel Pralat (Ryerson University)
DTSTART:20200923T140000Z
DTEND:20200923T145500Z
DTSTAMP:20260422T212709Z
UID:probabilisticcombinatorics/5
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/probabilisti
 ccombinatorics/5/">Localization game for random graphs</a>\nby Pawel Prala
 t (Ryerson University) as part of Probabilistic Combinatorics Online 2020\
 n\n\nAbstract\nWe consider the localization game played on graphs in which
  a cop tries to determine the exact location of an invisible robber by exp
 loiting distance probes. The corresponding graph parameter is called the l
 ocalization number. The localization number is related to the metric dimen
 sion of a graph\, in a way that is analogous to how the cop number is rela
 ted to the domination number. Indeed\, the metric dimension of a graph is 
 the minimum number of probes needed in the localization game so that the c
 op can win in one round. We investigate both graph parameters for binomial
  random graphs.\n
LOCATION:https://researchseminars.org/talk/probabilisticcombinatorics/5/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jane Gao (University of Waterloo)
DTSTART:20200923T160000Z
DTEND:20200923T165500Z
DTSTAMP:20260422T212709Z
UID:probabilisticcombinatorics/6
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/probabilisti
 ccombinatorics/6/">Random graphs with specified degree sequences</a>\nby J
 ane Gao (University of Waterloo) as part of Probabilistic Combinatorics On
 line 2020\n\n\nAbstract\nRandom graphs with specified degree sequences are
  popular random graph models not yet well understood\, especially when the
  degree sequences are not `nice'. Most problems in random graph theory eve
 ntually boil down to estimating subgraph probabilities. We will discuss th
 e configuration model and the switching method that are tools commonly use
 d to study such random graphs. Then we will discuss some recent results on
  subgraph probabilities and distributions\, the chromatic number and the c
 onnectivity. Finally we discuss the relation between these random graphs a
 nd the well-known Erdos-Renyi graphs\, and show how well the former can be
  approximated by the latter.\n
LOCATION:https://researchseminars.org/talk/probabilisticcombinatorics/6/
END:VEVENT
BEGIN:VEVENT
SUMMARY:David Gamarnik (MIT Sloan School of Management)
DTSTART:20200923T170000Z
DTEND:20200923T175500Z
DTSTAMP:20260422T212709Z
UID:probabilisticcombinatorics/7
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/probabilisti
 ccombinatorics/7/">Low-degree hardness of random optimization problems</a>
 \nby David Gamarnik (MIT Sloan School of Management) as part of Probabilis
 tic Combinatorics Online 2020\n\n\nAbstract\nWe consider the problem of fi
 nding nearly optimal solutions of optimization problems with random object
 ive functions. Two concrete problems we consider are (a) optimizing the Ha
 miltonian of a spherical or Ising p-spin glass model (to be introduced in 
 the talk)\, and (b) finding a large independent set in a sparse Erdos-Reny
 i graph. We consider the family of algorithms based on low-degree polynomi
 als of the input. This is a general framework that captures methods such a
 s approximate message passing and local algorithms on sparse graphs\, amon
 g others. We show this class of algorithms cannot produce nearly optimal s
 olutions with high probability. Our proof uses two ingredients. On the one
  hand both models exhibit the Overlap Gap Property (OGP) of near-optimal s
 olutions. Specifically\, for both models\, every two solutions close to op
 timality are either close or far from each other. The second proof ingredi
 ent is the stability of the algorithms based on low-degree polynomials: a 
 small perturbation of the input induces a small perturbation of the output
 . By an interpolation argument\, such a stable algorithm cannot overcome t
 he OGP barrier\, thus leading to the inapproximability. The stability prop
 erty is established using concepts from Gaussian and Boolean Fourier analy
 sis\, including noise sensitivity\, hypercontractivity\, and total influen
 ce.\n\nJoint work with Aukosh Jagannath and Alex Wein.\n
LOCATION:https://researchseminars.org/talk/probabilisticcombinatorics/7/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lior Gishboliner (ETH Zürich)
DTSTART:20200924T100000Z
DTEND:20200924T102500Z
DTSTAMP:20260422T212709Z
UID:probabilisticcombinatorics/9
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/probabilisti
 ccombinatorics/9/">Very fast construction of bounded-degree spanning graph
 s via the semi-random graph process</a>\nby Lior Gishboliner (ETH Zürich)
  as part of Probabilistic Combinatorics Online 2020\n\n\nAbstract\nSemi-ra
 ndom processes involve an adaptive decision-maker\, whose goal is to achie
 ve some predetermined objective in an online randomized environment. In th
 is paper\, we consider a recently proposed semi-random graph process\, def
 ined as follows: we start with an empty graph on $n$ vertices\, and in eac
 h round\, the decision-maker\, called Builder\, receives a uniformly rando
 m vertex $v$\, and must immediately (in an online manner) choose another v
 ertex $u$\, adding the edge $\\{u\,v\\}$ to the graph. Builder's end goal 
 is to make the constructed graph satisfy some predetermined monotone graph
  property. There are also natural offline and non-adaptive variants of thi
 s setting.\nIt was asked by N. Alon whether for every bounded-degree (span
 ning) graph $H$\, Builder can construct a copy of $H$ with high probabilit
 y in $O(n)$ rounds. We answer this question positively in a strong sense\,
  showing that any graph with maximum degree $\\Delta$ can be constructed w
 ith high probability in $(3\\Delta/2+o(\\Delta))n$ rounds\, where the $o(\
 \Delta)$ term tends to zero as $\\Delta$ tends to infinity. This is tight 
 (even for the offline case) up to a multiplicative factor of $3+o_{\\Delta
 }(1)$. Furthermore\, for the special case where $H$ is a forest of maximum
  degree $\\Delta$\, we show that $H$ can be constructed with high probabil
 ity in $O(\\log\\Delta)n$ rounds. This is tight up to a multiplicative con
 stant\, even for the offline setting. Finally\, we show a separation betwe
 en adaptive and non-adaptive strategies\, proving a lower bound of $\\Omeg
 a(n\\sqrt{\\log n})$ on the number of rounds necessary to eliminate all is
 olated vertices w.h.p. using a non-adaptive strategy. This bound is tight\
 , and in fact there are non-adaptive strategies for constructing a Hamilto
 n cycle or a $K_r$-factor\, which are successful w.h.p. within $O(n\\sqrt{
 \\log n})$ rounds.\n\nJoint work with Omri Ben-Eliezer\, Danny Hefetz and 
 Michael Krivelevich\n
LOCATION:https://researchseminars.org/talk/probabilisticcombinatorics/9/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Sergei Kiselev (MIPT)
DTSTART:20200924T103000Z
DTEND:20200924T105500Z
DTSTAMP:20260422T212709Z
UID:probabilisticcombinatorics/10
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/probabilisti
 ccombinatorics/10/">Rainbow matchings in $k$-partite hypergraphs</a>\nby S
 ergei Kiselev (MIPT) as part of Probabilistic Combinatorics Online 2020\n\
 n\nAbstract\nLet $[n]:=\\{1\,\\ldots\,n\\}$. The following conjecture was 
 made by Aharoni and Howard [1]:\n\nLet $n\\ge s$ and $k$ be positive integ
 ers. If $\\mathcal F_1\,\\ldots\,\\mathcal F_s\\subset [n]^k$ satisfy $\\m
 in_{i}|\\mathcal F_i|>(s-1)n^{k-1}$ then there exist $F_1\\in\\mathcal F_1
 \,\\ldots\, F_s\\in \\mathcal F_s\,$ such that $F_i\\cap F_j = \\emptyset$
  for any $1\\leq i<$ $j\\leq n$.\n\nIn their paper\, Aharoni and Howard pr
 oved this conjecture for $k=2\,3$. Then\, Lu and Yu [3] proved it for $n>3
 (s-1)(k-1).$ Our main result is the proof of the conjecture for all $s>s_0
 .$ The proof relies on the idea that intersection of any family with a ran
 dom matching is highly concentrated around its expectation. This idea was 
 introduced by the second author in the paper [2] in the context of the Erd
 \\H os Matching Conjecture.\n\n[1] R. Aharoni and D. Howard\, A Rainbow $r
 $-Partite Version of the Erdos--Ko--Rado Theorem\, Comb. Probab.  Comput.v
 26 (2017)\, N3\, 321--337.\n\n[2] P. Frankl and A. Kupavskii\, The Erdos M
 atching Conjecture and Concentration Inequalities\, arXiv:1806.08855.\n\n[
 3] H. Lu and X. Yu\, On rainbow matchings for hypergraphs\, SIAM J. Disret
 e Math. 32 (2018)\, N1\, 382--393.\n\nJoint work with Andrey Kupavskii\n
LOCATION:https://researchseminars.org/talk/probabilisticcombinatorics/10/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Mihyun Kang (Graz University of Technology)
DTSTART:20200924T130000Z
DTEND:20200924T135500Z
DTSTAMP:20260422T212709Z
UID:probabilisticcombinatorics/11
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/probabilisti
 ccombinatorics/11/">Topological aspects of random graphs</a>\nby Mihyun Ka
 ng (Graz University of Technology) as part of Probabilistic Combinatorics 
 Online 2020\n\n\nAbstract\nIn this talk we will discuss various topologica
 l aspects of random graphs. How does the genus of a uniform random graph c
 hange as the number of edges increases?  How does a topological constraint
  (such as imposing an upper bound on the genus) influence the structure of
  a random graph (such as the order of the largest component\, the length o
 f the shortest and longest cycles)?\n
LOCATION:https://researchseminars.org/talk/probabilisticcombinatorics/11/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Will Perkins (University of Illinois at Chicago)
DTSTART:20200924T140000Z
DTEND:20200924T142500Z
DTSTAMP:20260422T212709Z
UID:probabilisticcombinatorics/12
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/probabilisti
 ccombinatorics/12/">Finite-size scaling for the random cluster model on ra
 ndom graphs</a>\nby Will Perkins (University of Illinois at Chicago) as pa
 rt of Probabilistic Combinatorics Online 2020\n\n\nAbstract\nThe random cl
 uster model is a probability measure on edge sets of a graph given by expo
 nentially tilting edge percolation by the number of connected components a
 n edge set induces.  It generalizes the ferromagnetic Potts model\, and li
 ke the Potts model it exhibits a phase transition as the temperature chang
 es on many classes of graphs.  Here we study the large q behavior of the r
 andom cluster model on random regular graphs and give detailed information
  about the phase transition\, including the distribution of the log partit
 ion function\, correlation decay\, and local weak convergence.  Our techni
 que involves approximating the model by a mixture of abstract polymer mode
 ls with convergent cluster expansions.\n\nJoint work with Tyler Helmuth an
 d Matthew Jenssen.\n
LOCATION:https://researchseminars.org/talk/probabilisticcombinatorics/12/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Nikolaos Fountoulakis (University of Birmingham)
DTSTART:20200924T143000Z
DTEND:20200924T145500Z
DTSTAMP:20260422T212709Z
UID:probabilisticcombinatorics/13
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/probabilisti
 ccombinatorics/13/">On the spectral gap and the expansion of random simpli
 cial complexes</a>\nby Nikolaos Fountoulakis (University of Birmingham) as
  part of Probabilistic Combinatorics Online 2020\n\n\nAbstract\nIn this ta
 lk\, we will discuss the expansion properties and the spectrum of the comb
 inatorial Laplace operator of a d-dimensional Linial-Meshulam random simpl
 icial complex\, above the cohomological connectivity threshold. The focus 
 of our discussion will be the spectral gap of the Laplace operator and the
  Cheeger constant.\nFurthermore\, we will discuss a notion of a random wal
 k on such a complex\, which generalises the standard random walk on a grap
 h\, and consider its mixing time.\n\nThis is joint work with Michał Przyk
 ucki.\n
LOCATION:https://researchseminars.org/talk/probabilisticcombinatorics/13/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lutz Warnke (Georgia Institute of Technology)
DTSTART:20200924T160000Z
DTEND:20200924T165500Z
DTSTAMP:20260422T212709Z
UID:probabilisticcombinatorics/14
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/probabilisti
 ccombinatorics/14/">Prague dimension of random graphs</a>\nby Lutz Warnke 
 (Georgia Institute of Technology) as part of Probabilistic Combinatorics O
 nline 2020\n\n\nAbstract\nVarious notions of dimension are important in ma
 ny area of mathematics\, and for graphs the Prague dimension was introduce
 d in the late 1970s Nesetril\, Pultr and Rodl.\nWe show that the Prague di
 mension of the binomial random graph $G(n\,p)$ is typically of order $n/\\
 log n$ for constant edge-probabilities $p$\; this proves a conjecture of F
 uredi and Kantor.\nOne key ingredient of our proof is a randomized greedy 
 edge-coloring algorithm\, that allows us to bound the chromatic index of r
 andom subhypergraphs with large edge-uniformities.\n\nBased on joint work 
 with He Guo and Kalen Patton.\n
LOCATION:https://researchseminars.org/talk/probabilisticcombinatorics/14/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Matthew Kwan (Stanford University)
DTSTART:20200924T170000Z
DTEND:20200924T175500Z
DTSTAMP:20260422T212709Z
UID:probabilisticcombinatorics/15
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/probabilisti
 ccombinatorics/15/">Perfect matchings in random hypergraphs</a>\nby Matthe
 w Kwan (Stanford University) as part of Probabilistic Combinatorics Online
  2020\n\n\nAbstract\nFor positive integers $d< k$ and $n$ divisible by $k$
 \, let $m_{d}(k\,n)$ be the minimum $d$-degree ensuring the existence of a
  perfect matching in a $k$-uniform hypergraph. In the graph case (where $k
 =2$)\, a classical theorem of Dirac says that $m_{1}(2\,n)=\\lceil n/2\\rc
 eil$. However\, in general\, our understanding of the values of $m_{d}(k\,
 n)$ is still very limited\, and it is an active topic of research to deter
 mine or approximate these values. In the first part of this talk\, we disc
 uss a new `transference' theorem for Dirac-type results relative to random
  hypergraphs. Specifically\, we prove that a random $k$-uniform hypergraph
  $G$ with $n$ vertices and `not too small' edge probability $p$ typically 
 has the property that every spanning subgraph with minimum $d$-degree at l
 east $(1+\\varepsilon)m_{d}(k\,n)p$ has a perfect matching. One interestin
 g aspect of our proof is a `non-constructive' application of the absorbing
  method\, which allows us to prove a bound in terms of $m_{d}(k\,n)$ witho
 ut actually knowing its value.\nThe ideas in our work are quite powerful a
 nd can be applied to other problems: in the second part of this talk we hi
 ghlight a recent application of these ideas to random designs\, proving th
 at a random Steiner triple system typically admits a decomposition of almo
 st all its triples into perfect matchings (that is to say\, it is almost r
 esolvable).\n\nJoint work with Asaf Ferber.\n
LOCATION:https://researchseminars.org/talk/probabilisticcombinatorics/15/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Persi Diaconis (Stanford University)
DTSTART:20200925T090000Z
DTEND:20200925T095500Z
DTSTAMP:20260422T212709Z
UID:probabilisticcombinatorics/16
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/probabilisti
 ccombinatorics/16/">A course on probabilistic combinatorics</a>\nby Persi 
 Diaconis (Stanford University) as part of Probabilistic Combinatorics Onli
 ne 2020\n\n\nAbstract\nThis past April-June (2020) I gave a graduate cours
 e on probabilistic combinatorics at Stanford's departments of mathematics 
 and statistics. This covered the usual topics: Let X be a finite set\, pic
 k x in X uniformly\, 'what does it look like?' With X permutations\, graph
 s\, partitions\, set partitions\, matrices over a finite field. It also co
 vered 'who cares?' That is\, applications in statistics\, computer science
  and physics/chemistry. Two features were lectures on 'from algorithm to t
 heorem' and 'graph limit theory and its extensions'. the first emphasizes 
 the place and usefulness of algorithms to actually pick x uniformly (for e
 xample\, there are many different ways to sample permutations\, how does o
 ne efficiently sample partitions or set partitions? say when $n=10^6$?) Ea
 ch such algorithm has an associated set of limit theorems that it 'makes t
 ransparent'. The second topic featured the work of Lovasz and Razborov and
  their coworkers. I will review the topics (stopping to be specific) and t
 he course projects\, some of which are turning into publishable papers.\n
LOCATION:https://researchseminars.org/talk/probabilisticcombinatorics/16/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alexander Semenov (MIPT)
DTSTART:20200925T100000Z
DTEND:20200925T102500Z
DTSTAMP:20260422T212709Z
UID:probabilisticcombinatorics/17
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/probabilisti
 ccombinatorics/17/">Probability thresholds estimates for coloring properti
 es of random hypergraphs</a>\nby Alexander Semenov (MIPT) as part of Proba
 bilistic Combinatorics Online 2020\n\n\nAbstract\nRecall that for an integ
 er $j$\, a $j$-independent set in a hypergraph $H=(V\,E)$ is a subset $W\\
 subset V$ such that for every edge $e\\in E: |e\\cap W| \\leq j$. A $j$-pr
 oper coloring of $H=(V\,E)$ is a partition of the vertex set $V$ of $H$ in
 to disjoint union of $j$-independent sets\, so called colors. The $j$-chro
 matic number $\\chi_j(H)$ of $H$ is the minimal number of colors needed fo
 r a $j$-proper coloring of $H$.\n\nWe will talk about our latest results o
 n colorings of the k-uniform random hypergraph $H(n\,k\,p)$. We are intere
 sted in asymptotic properties of $H(n\,k\,p)$ to have its $j$-chromatic nu
 mber equal to some fixed number $r$. By asymptotic properties of $H(n\,k\,
 p)$ we consider $n$ as tending to infinity\, while $k$ and $r$ are kept co
 nstant.\n\nIt can be shown that the previously mentioned property of rando
 m hypergraph has a sharp threshold. For the classic case of $(k-1)$-chroma
 tic number\, upper and lower bounds for that threshold were investigated b
 y different researchers. It should be also mentioned that the gap between 
 these bounds in terms of the parameter $c=p{n\\choose k}/n$ has a bounded 
 order $O_k(1)$.\n\nWe are going to present the results from our last serie
 s of works where we found very tight bounds for the case of arbitrary $r$ 
 and $1< k-j=o(k^{1/4})$.\n\nThis is joint work with Dmitry Shabanov.\n
LOCATION:https://researchseminars.org/talk/probabilisticcombinatorics/17/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jakub Kozik (Jagiellonian University)
DTSTART:20200925T103000Z
DTEND:20200925T105500Z
DTSTAMP:20260422T212709Z
UID:probabilisticcombinatorics/18
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/probabilisti
 ccombinatorics/18/">Bi-uniform property b</a>\nby Jakub Kozik (Jagiellonia
 n University) as part of Probabilistic Combinatorics Online 2020\n\n\nAbst
 ract\nHow many edges do we need in order to construct a $k$-uniform hyperg
 raph which is not two-colorable?\nThis number\, denoted by $m(k)$\, has be
 en intensively studied since its introduction by Erd\\H{o}s and Hajnal in 
 1961.\nAs a result\, the lower bounds have been improved a number of times
  and nowadays we know that $m(k)=\\Omega(\\sqrt{k/\\log(k)}\\\;2^k)$ (Radh
 akrishnan and Srinivasan 2000).\nThe story of the upper bounds is much sho
 rter.\nBound $m(k)= O(k^2 \\\;2^k)$\,  obtained by Erd\\H{o}s in 1964\, ha
 s not been improved since.\nWe are going to discuss what insights can be g
 ained from considering analogous problem for non-uniform hypergraphs.\nWe 
 focus on an interesting class of bi-uniform hypergraphs\, i.e. hypergraphs
  in which there are only two allowed sizes of edges.\nThe class is rich en
 ough to observe the most important coloring obstacles caused by non-unifor
 m edges.\nOn the other hand\, having only two sizes of edges eliminates a 
 lot of technical difficulties.\n
LOCATION:https://researchseminars.org/talk/probabilisticcombinatorics/18/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Peleg Michaeli (Tel-Aviv University)
DTSTART:20200925T130000Z
DTEND:20200925T132500Z
DTSTAMP:20260422T212709Z
UID:probabilisticcombinatorics/19
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/probabilisti
 ccombinatorics/19/">Greedy maximal independent sets via local limits</a>\n
 by Peleg Michaeli (Tel-Aviv University) as part of Probabilistic Combinato
 rics Online 2020\n\n\nAbstract\nThe random greedy algorithm for finding a 
 maximal independent set in a graph has been studied extensively in various
  settings in combinatorics\, probability\, computer science — and even i
 n chemistry.  The algorithm builds a maximal independent set by inspecting
  the vertices of the graph one at a time according to a random order\, add
 ing the current vertex to the independent set if it is not connected to an
 y previously added vertex by an edge.\nIn this talk\, I will present a nat
 ural and general framework for calculating the asymptotics of the proporti
 on of the yielded independent set for sequences of (possibly random) graph
 s\, involving a useful notion of local convergence. We use this framework 
 both to give short and simple proofs for results on previously studied fam
 ilies of graphs\, such as paths and binomial random graphs\, and to give n
 ew results for other models such as random trees.\n\nThe talk is based on 
 joint work with Michael Krivelevich\, Tamás Mészáros and Clara Shikhelm
 an.\n
LOCATION:https://researchseminars.org/talk/probabilisticcombinatorics/19/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Felix Joos (Heidelberg University)
DTSTART:20200925T133000Z
DTEND:20200925T135500Z
DTSTAMP:20260422T212709Z
UID:probabilisticcombinatorics/20
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/probabilisti
 ccombinatorics/20/">Dirac-type results for hypergraph decompositions into 
 cycles</a>\nby Felix Joos (Heidelberg University) as part of Probabilistic
  Combinatorics Online 2020\n\n\nAbstract\nI will discuss recent joint work
  with Marcus Kühn and Bjarne Schülke on decompositions of hypergraphs in
 to cycles. One of the results answers a question of Glock\, Kühn and Osth
 us and another one is an extension of the well-known result due to Rödl a
 nd Rucinski on the minimum degree threshold for Hamilton cycles in k-unifo
 rm hypergraphs.\n
LOCATION:https://researchseminars.org/talk/probabilisticcombinatorics/20/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Bhargav Narayanan (Rutgers University)
DTSTART:20200925T140000Z
DTEND:20200925T142500Z
DTSTAMP:20260422T212709Z
UID:probabilisticcombinatorics/21
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/probabilisti
 ccombinatorics/21/">The threshold of the square of the Hamilton cycle</a>\
 nby Bhargav Narayanan (Rutgers University) as part of Probabilistic Combin
 atorics Online 2020\n\n\nAbstract\nWe show that the threshold for the appe
 arance of the square of the Hamilton cycle in $G_{n\,p}$ is $p = 1/\\sqrt{
 n}$.\n\nJoint work with J. Kahn and J. Park.\n
LOCATION:https://researchseminars.org/talk/probabilisticcombinatorics/21/
END:VEVENT
BEGIN:VEVENT
SUMMARY:József Balogh (University of Illinois at Urbana-Champaign)
DTSTART:20200925T143000Z
DTEND:20200925T145500Z
DTSTAMP:20260422T212709Z
UID:probabilisticcombinatorics/22
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/probabilisti
 ccombinatorics/22/">Extensions of Mantel’s theorem</a>\nby József Balog
 h (University of Illinois at Urbana-Champaign) as part of Probabilistic Co
 mbinatorics Online 2020\n\n\nAbstract\nMantel’s theorem is a basic class
 ical theorem of extremal graph theory. There are many different extensions
  and generalizations investigated and many open questions remained.\nI wil
 l talk about four recent results\, including `stability’ and `supersatur
 ation’ properties.\n\nThe results are partly joined with Clemen\, Katona
 \, Lavrov\, Lidicky\, Linz\, Pfender and Tuza.\n
LOCATION:https://researchseminars.org/talk/probabilisticcombinatorics/22/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Allan Sly (Princeton University)
DTSTART:20200925T160000Z
DTEND:20200925T165500Z
DTSTAMP:20260422T212709Z
UID:probabilisticcombinatorics/23
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/probabilisti
 ccombinatorics/23/">Local functions for the Ising model on the tree</a>\nb
 y Allan Sly (Princeton University) as part of Probabilistic Combinatorics 
 Online 2020\n\n\nAbstract\nThis talk will look at the question of what pro
 cesses can or cannot be constructed using local randomness.  Work of Gamar
 nik and Sudan and later Rahman and Virag showed that local algorithms on r
 andom d-regular graphs can only construct independent sets of size approxi
 mately half the maximal size when d is large.  Like the optimization probl
 em\, a closely related question arising in ergodic theory asks can a parti
 cular distribution such as a uniformly random colouring on the tree be con
 structed as a factor of IID\, a type of local functions.   I'll survey res
 ults in this area and describe new work constructing a factor of IID for t
 he Ising model on the tree in its intermediate regime.\n\nJoint work with 
 Danny Nam and Lingfu Zhang.\n
LOCATION:https://researchseminars.org/talk/probabilisticcombinatorics/23/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Xavier Pérez Giménez (University of Nebraska-Lincoln)
DTSTART:20200925T170000Z
DTEND:20200925T175500Z
DTSTAMP:20260422T212709Z
UID:probabilisticcombinatorics/24
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/probabilisti
 ccombinatorics/24/">The chromatic number of a random lift of $K_d$</a>\nby
  Xavier Pérez Giménez (University of Nebraska-Lincoln) as part of Probab
 ilistic Combinatorics Online 2020\n\n\nAbstract\nAn $n$-lift of a graph $G
 $ is a graph from which there is an $n$-to-$1$ covering map onto $G$. Amit
 \, Linial\, and Matousek (2002) raised the question of whether the chromat
 ic number of a random $n$-lift of $K_5$ is concentrated on a single value.
  We consider a more general problem\, and show that for fixed $d\\ge 3$ th
 e chromatic number of a random lift of $K_d$ is (asymptotically almost sur
 ely) either $k$ or $k+1$\, where $k$ is the smallest integer satisfying $d
  < 2k \\log k$. Moreover\, we show that\, for roughly half of the values o
 f $d$\, the chromatic number is concentrated on $k$. The argument for the 
 upper-bound on the chromatic number uses the small subgraph conditioning m
 ethod\, and it can be extended to random $n$-lifts of $G$\, for any fixed 
 $d$-regular graph $G$. \n\nThis is joint work with JD Nir.\n
LOCATION:https://researchseminars.org/talk/probabilisticcombinatorics/24/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Michael Krivelevich (Tel Aviv University)
DTSTART:20200924T090000Z
DTEND:20200924T095500Z
DTSTAMP:20260422T212709Z
UID:probabilisticcombinatorics/25
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/probabilisti
 ccombinatorics/25/">Color-biased Hamilton cycles in random graphs</a>\nby 
 Michael Krivelevich (Tel Aviv University) as part of Probabilistic Combina
 torics Online 2020\n\n\nAbstract\nWe show that a random graph $G(n\,p)$ wi
 th the edge probability $p(n)$ above the Hamiltonicity threshold is typica
 lly such that for any $r$-coloring of its edges\, for a fixed $r\\geq 2$\,
   there is a Hamilton cycle with at least $(2/(r+1)-o(1))n$ edges of the s
 ame color. This estimate is asymptotically optimal.\n\nA joint work with L
 ior Gishboliner and Peleg Michaeli.\n
LOCATION:https://researchseminars.org/talk/probabilisticcombinatorics/25/
END:VEVENT
END:VCALENDAR