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:20260404T094120Z
UID:probabilisticcombinatorics/1
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/proba
 bilisticcombinatorics/1/">Rota's basis conjecture holds asymptotically</a>
 \nby Alexey Pokrovskiy (University College London) as part of Probabilisti
 c Combinatorics Online 2020\n\n\nAbstract\nRota's Basis Conjecture is a we
 ll known problem\, that states that for any collection of $n$ bases in a r
 ank $n$ matroid\, it is possible to decompose all the elements into $n$ di
 sjoint rainbow bases. Here an asymptotic version of this is will be discus
 sed - that it is possible to find $n-o(n)$ disjoint rainbow independent se
 ts of size $n-o(n)$.\n
LOCATION:https://stable.researchseminars.org/talk/probabilisticcombinatori
 cs/1/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Brendan McKay (Australian National University)
DTSTART:20200923T100000Z
DTEND:20200923T105500Z
DTSTAMP:20260404T094120Z
UID:probabilisticcombinatorics/2
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/proba
 bilisticcombinatorics/2/">Some remarks on the method of switchings</a>\nby
  Brendan McKay (Australian National University) as part of Probabilistic C
 ombinatorics Online 2020\n\n\nAbstract\nThe method of switchings has becom
 e a standard tool for combinatorial enumeration and probability problems. 
 We will discuss some old and new applications and techniques. First\, we d
 iscuss how switchings make a very general tool for bounding upper tails of
  distributions. Second\, we illustrate how switchings can be used to study
  subgraphs of random graphs. Finally\, we enumerate linear hypergraphs wit
 h a given number of edges.\n
LOCATION:https://stable.researchseminars.org/talk/probabilisticcombinatori
 cs/2/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Nicholas Wormald (Monash University)
DTSTART:20200923T110000Z
DTEND:20200923T112500Z
DTSTAMP:20260404T094120Z
UID:probabilisticcombinatorics/3
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/proba
 bilisticcombinatorics/3/">Fast uniform generation of regular graphs and co
 ntingency tables</a>\nby Nicholas Wormald (Monash University) as part of P
 robabilistic Combinatorics Online 2020\n\n\nAbstract\nWe present a new tec
 hnique for use in switching-based random generation of graphs with given d
 egrees. For graphs with m edges and maximum degree $D=O(m^4)$\, the `best'
  existing uniform sampler\, given by McKay and Wormald in 1990\, runs in t
 ime $O(m^2D^2)$. Our new one runs in time $O(m)$\, which is effectively op
 timal. For $d$-regular graphs with $d =o(\\sqrt n)$\, the best existing on
 es run in time $O(nd^3)$. This is now improved  to $O(nd+d^4)$. Similar re
 sults are obtained for generating random contingency tables with given mar
 ginals (equivalently\, bipartite multigraphs with given degree sequence) i
 n the sparse case.  \n\nThis is joint work with  Andrii Arman and Jane Gao
 .\n
LOCATION:https://stable.researchseminars.org/talk/probabilisticcombinatori
 cs/3/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Benjamin Sudakov (ETH Zürich)
DTSTART:20200923T130000Z
DTEND:20200923T135500Z
DTSTAMP:20260404T094120Z
UID:probabilisticcombinatorics/4
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/proba
 bilisticcombinatorics/4/">Large independent sets from local considerations
 </a>\nby Benjamin Sudakov (ETH Zürich) as part of Probabilistic Combinato
 rics Online 2020\n\n\nAbstract\nHow  well  can  global  properties  of  a 
  graph  be  inferred  from  observations that  are  purely local?  This  g
 eneral  question  gives  rise  to  numerous  interesting problems. One suc
 h very natural question was raised independently by Erdos-Hajnal and Linia
 l-Rabinovich in the early 90's. How large must the independence number $\\
 alpha(G)$ of a graph $G$ be whose every $m$ vertices contain an independen
 t set of size $r$? In this talk we discuss new methods to attack this prob
 lem which improve many previous results.\n\nJoint work with Matija Bucic\n
LOCATION:https://stable.researchseminars.org/talk/probabilisticcombinatori
 cs/4/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pawel Pralat (Ryerson University)
DTSTART:20200923T140000Z
DTEND:20200923T145500Z
DTSTAMP:20260404T094120Z
UID:probabilisticcombinatorics/5
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/proba
 bilisticcombinatorics/5/">Localization game for random graphs</a>\nby Pawe
 l Pralat (Ryerson University) as part of Probabilistic Combinatorics Onlin
 e 2020\n\n\nAbstract\nWe consider the localization game played on graphs i
 n which a cop tries to determine the exact location of an invisible robber
  by exploiting distance probes. The corresponding graph parameter is calle
 d the localization number. The localization number is related to the metri
 c dimension of a graph\, in a way that is analogous to how the cop number 
 is related to the domination number. Indeed\, the metric dimension of a gr
 aph is the minimum number of probes needed in the localization game so tha
 t the cop can win in one round. We investigate both graph parameters for b
 inomial random graphs.\n
LOCATION:https://stable.researchseminars.org/talk/probabilisticcombinatori
 cs/5/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jane Gao (University of Waterloo)
DTSTART:20200923T160000Z
DTEND:20200923T165500Z
DTSTAMP:20260404T094120Z
UID:probabilisticcombinatorics/6
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/proba
 bilisticcombinatorics/6/">Random graphs with specified degree sequences</a
 >\nby Jane Gao (University of Waterloo) as part of Probabilistic Combinato
 rics Online 2020\n\n\nAbstract\nRandom graphs with specified degree sequen
 ces are popular random graph models not yet well understood\, especially w
 hen the degree sequences are not `nice'. Most problems in random graph the
 ory eventually boil down to estimating subgraph probabilities. We will dis
 cuss the configuration model and the switching method that are tools commo
 nly used to study such random graphs. Then we will discuss some recent res
 ults on subgraph probabilities and distributions\, the chromatic number an
 d the connectivity. Finally we discuss the relation between these random g
 raphs and the well-known Erdos-Renyi graphs\, and show how well the former
  can be approximated by the latter.\n
LOCATION:https://stable.researchseminars.org/talk/probabilisticcombinatori
 cs/6/
END:VEVENT
BEGIN:VEVENT
SUMMARY:David Gamarnik (MIT Sloan School of Management)
DTSTART:20200923T170000Z
DTEND:20200923T175500Z
DTSTAMP:20260404T094120Z
UID:probabilisticcombinatorics/7
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/proba
 bilisticcombinatorics/7/">Low-degree hardness of random optimization probl
 ems</a>\nby David Gamarnik (MIT Sloan School of Management) as part of Pro
 babilistic Combinatorics Online 2020\n\n\nAbstract\nWe consider the proble
 m of finding nearly optimal solutions of optimization problems with random
  objective functions. Two concrete problems we consider are (a) optimizing
  the Hamiltonian of a spherical or Ising p-spin glass model (to be introdu
 ced in the talk)\, and (b) finding a large independent set in a sparse Erd
 os-Renyi graph. We consider the family of algorithms based on low-degree p
 olynomials of the input. This is a general framework that captures methods
  such as approximate message passing and local algorithms on sparse graphs
 \, among others. We show this class of algorithms cannot produce nearly op
 timal solutions with high probability. Our proof uses two ingredients. On 
 the one hand both models exhibit the Overlap Gap Property (OGP) of near-op
 timal solutions. Specifically\, for both models\, every two solutions clos
 e to optimality are either close or far from each other. The second proof 
 ingredient is the stability of the algorithms based on low-degree polynomi
 als: a small perturbation of the input induces a small perturbation of the
  output. By an interpolation argument\, such a stable algorithm cannot ove
 rcome the OGP barrier\, thus leading to the inapproximability. The stabili
 ty property is established using concepts from Gaussian and Boolean Fourie
 r analysis\, including noise sensitivity\, hypercontractivity\, and total 
 influence.\n\nJoint work with Aukosh Jagannath and Alex Wein.\n
LOCATION:https://stable.researchseminars.org/talk/probabilisticcombinatori
 cs/7/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lior Gishboliner (ETH Zürich)
DTSTART:20200924T100000Z
DTEND:20200924T102500Z
DTSTAMP:20260404T094120Z
UID:probabilisticcombinatorics/9
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/proba
 bilisticcombinatorics/9/">Very fast construction of bounded-degree spannin
 g graphs via the semi-random graph process</a>\nby Lior Gishboliner (ETH Z
 ürich) as part of Probabilistic Combinatorics Online 2020\n\n\nAbstract\n
 Semi-random processes involve an adaptive decision-maker\, whose goal is t
 o achieve some predetermined objective in an online randomized environment
 . In this paper\, we consider a recently proposed semi-random graph proces
 s\, defined as follows: we start with an empty graph on $n$ vertices\, and
  in each round\, the decision-maker\, called Builder\, receives a uniforml
 y random vertex $v$\, and must immediately (in an online manner) choose an
 other vertex $u$\, adding the edge $\\{u\,v\\}$ to the graph. Builder's en
 d goal is to make the constructed graph satisfy some predetermined monoton
 e graph property. There are also natural offline and non-adaptive variants
  of this setting.\nIt was asked by N. Alon whether for every bounded-degre
 e (spanning) graph $H$\, Builder can construct a copy of $H$ with high pro
 bability in $O(n)$ rounds. We answer this question positively in a strong 
 sense\, showing that any graph with maximum degree $\\Delta$ can be constr
 ucted with high probability in $(3\\Delta/2+o(\\Delta))n$ rounds\, where t
 he $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 p
 robability in $O(\\log\\Delta)n$ rounds. This is tight up to a multiplicat
 ive constant\, even for the offline setting. Finally\, we show a separatio
 n between adaptive and non-adaptive strategies\, proving a lower bound of 
 $\\Omega(n\\sqrt{\\log n})$ on the number of rounds necessary to eliminate
  all isolated vertices w.h.p. using a non-adaptive strategy. This bound is
  tight\, and in fact there are non-adaptive strategies for constructing a 
 Hamilton 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 Hefe
 tz and Michael Krivelevich\n
LOCATION:https://stable.researchseminars.org/talk/probabilisticcombinatori
 cs/9/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Sergei Kiselev (MIPT)
DTSTART:20200924T103000Z
DTEND:20200924T105500Z
DTSTAMP:20260404T094120Z
UID:probabilisticcombinatorics/10
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/proba
 bilisticcombinatorics/10/">Rainbow matchings in $k$-partite hypergraphs</a
 >\nby Sergei Kiselev (MIPT) as part of Probabilistic Combinatorics Online 
 2020\n\n\nAbstract\nLet $[n]:=\\{1\,\\ldots\,n\\}$. The following conjectu
 re was made by Aharoni and Howard [1]:\n\nLet $n\\ge s$ and $k$ be positiv
 e integers. If $\\mathcal F_1\,\\ldots\,\\mathcal F_s\\subset [n]^k$ satis
 fy $\\min_{i}|\\mathcal F_i|>(s-1)n^{k-1}$ then there exist $F_1\\in\\math
 cal F_1\,\\ldots\, F_s\\in \\mathcal F_s\,$ such that $F_i\\cap F_j = \\em
 ptyset$ for any $1\\leq i<$ $j\\leq n$.\n\nIn their paper\, Aharoni and Ho
 ward proved this conjecture for $k=2\,3$. Then\, Lu and Yu [3] proved it f
 or $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 wit
 h a random matching is highly concentrated around its expectation. This id
 ea 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 Rai
 nbow $r$-Partite Version of the Erdos--Ko--Rado Theorem\, Comb. Probab.  C
 omput.v26 (2017)\, N3\, 321--337.\n\n[2] P. Frankl and A. Kupavskii\, The 
 Erdos Matching Conjecture and Concentration Inequalities\, arXiv:1806.0885
 5.\n\n[3] H. Lu and X. Yu\, On rainbow matchings for hypergraphs\, SIAM J.
  Disrete Math. 32 (2018)\, N1\, 382--393.\n\nJoint work with Andrey Kupavs
 kii\n
LOCATION:https://stable.researchseminars.org/talk/probabilisticcombinatori
 cs/10/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Mihyun Kang (Graz University of Technology)
DTSTART:20200924T130000Z
DTEND:20200924T135500Z
DTSTAMP:20260404T094120Z
UID:probabilisticcombinatorics/11
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/proba
 bilisticcombinatorics/11/">Topological aspects of random graphs</a>\nby Mi
 hyun Kang (Graz University of Technology) as part of Probabilistic Combina
 torics Online 2020\n\n\nAbstract\nIn this talk we will discuss various top
 ological aspects of random graphs. How does the genus of a uniform random 
 graph change as the number of edges increases?  How does a topological con
 straint (such as imposing an upper bound on the genus) influence the struc
 ture of a random graph (such as the order of the largest component\, the l
 ength of the shortest and longest cycles)?\n
LOCATION:https://stable.researchseminars.org/talk/probabilisticcombinatori
 cs/11/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Will Perkins (University of Illinois at Chicago)
DTSTART:20200924T140000Z
DTEND:20200924T142500Z
DTSTAMP:20260404T094120Z
UID:probabilisticcombinatorics/12
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/proba
 bilisticcombinatorics/12/">Finite-size scaling for the random cluster mode
 l on random graphs</a>\nby Will Perkins (University of Illinois at Chicago
 ) as part of Probabilistic Combinatorics Online 2020\n\n\nAbstract\nThe ra
 ndom cluster model is a probability measure on edge sets of a graph given 
 by exponentially tilting edge percolation by the number of connected compo
 nents an edge set induces.  It generalizes the ferromagnetic Potts model\,
  and like the Potts model it exhibits a phase transition as the temperatur
 e changes on many classes of graphs.  Here we study the large q behavior o
 f the random cluster model on random regular graphs and give detailed info
 rmation about the phase transition\, including the distribution of the log
  partition function\, correlation decay\, and local weak convergence.  Our
  technique involves approximating the model by a mixture of abstract polym
 er models with convergent cluster expansions.\n\nJoint work with Tyler Hel
 muth and Matthew Jenssen.\n
LOCATION:https://stable.researchseminars.org/talk/probabilisticcombinatori
 cs/12/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Nikolaos Fountoulakis (University of Birmingham)
DTSTART:20200924T143000Z
DTEND:20200924T145500Z
DTSTAMP:20260404T094120Z
UID:probabilisticcombinatorics/13
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/proba
 bilisticcombinatorics/13/">On the spectral gap and the expansion of random
  simplicial complexes</a>\nby Nikolaos Fountoulakis (University of Birming
 ham) as part of Probabilistic Combinatorics Online 2020\n\n\nAbstract\nIn 
 this talk\, we will discuss the expansion properties and the spectrum of t
 he combinatorial Laplace operator of a d-dimensional Linial-Meshulam rando
 m simplicial 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 ran
 dom walk on such a complex\, which generalises the standard random walk on
  a graph\, and consider its mixing time.\n\nThis is joint work with Micha
 ł Przykucki.\n
LOCATION:https://stable.researchseminars.org/talk/probabilisticcombinatori
 cs/13/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lutz Warnke (Georgia Institute of Technology)
DTSTART:20200924T160000Z
DTEND:20200924T165500Z
DTSTAMP:20260404T094120Z
UID:probabilisticcombinatorics/14
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/proba
 bilisticcombinatorics/14/">Prague dimension of random graphs</a>\nby Lutz 
 Warnke (Georgia Institute of Technology) as part of Probabilistic Combinat
 orics Online 2020\n\n\nAbstract\nVarious notions of dimension are importan
 t in many area of mathematics\, and for graphs the Prague dimension was in
 troduced in the late 1970s Nesetril\, Pultr and Rodl.\nWe show that the Pr
 ague dimension of the binomial random graph $G(n\,p)$ is typically of orde
 r $n/\\log n$ for constant edge-probabilities $p$\; this proves a conjectu
 re of Furedi and Kantor.\nOne key ingredient of our proof is a randomized 
 greedy edge-coloring algorithm\, that allows us to bound the chromatic ind
 ex of random subhypergraphs with large edge-uniformities.\n\nBased on join
 t work with He Guo and Kalen Patton.\n
LOCATION:https://stable.researchseminars.org/talk/probabilisticcombinatori
 cs/14/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Matthew Kwan (Stanford University)
DTSTART:20200924T170000Z
DTEND:20200924T175500Z
DTSTAMP:20260404T094120Z
UID:probabilisticcombinatorics/15
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/proba
 bilisticcombinatorics/15/">Perfect matchings in random hypergraphs</a>\nby
  Matthew 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 existen
 ce of a perfect matching in a $k$-uniform hypergraph. In the graph case (w
 here $k=2$)\, a classical theorem of Dirac says that $m_{1}(2\,n)=\\lceil 
 n/2\\rceil$. 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 t
 o determine or approximate these values. In the first part of this talk\, 
 we discuss a new `transference' theorem for Dirac-type results relative to
  random hypergraphs. Specifically\, we prove that a random $k$-uniform hyp
 ergraph $G$ with $n$ vertices and `not too small' edge probability $p$ typ
 ically has the property that every spanning subgraph with minimum $d$-degr
 ee at least $(1+\\varepsilon)m_{d}(k\,n)p$ has a perfect matching. One int
 eresting aspect of our proof is a `non-constructive' application of the ab
 sorbing method\, which allows us to prove a bound in terms of $m_{d}(k\,n)
 $ without actually knowing its value.\nThe ideas in our work are quite pow
 erful and can be applied to other problems: in the second part of this tal
 k we highlight a recent application of these ideas to random designs\, pro
 ving that a random Steiner triple system typically admits a decomposition 
 of almost all its triples into perfect matchings (that is to say\, it is a
 lmost resolvable).\n\nJoint work with Asaf Ferber.\n
LOCATION:https://stable.researchseminars.org/talk/probabilisticcombinatori
 cs/15/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Persi Diaconis (Stanford University)
DTSTART:20200925T090000Z
DTEND:20200925T095500Z
DTSTAMP:20260404T094120Z
UID:probabilisticcombinatorics/16
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/proba
 bilisticcombinatorics/16/">A course on probabilistic combinatorics</a>\nby
  Persi Diaconis (Stanford University) as part of Probabilistic Combinatori
 cs Online 2020\n\n\nAbstract\nThis past April-June (2020) I gave a graduat
 e course on probabilistic combinatorics at Stanford's departments of mathe
 matics and statistics. This covered the usual topics: Let X be a finite se
 t\, pick x in X uniformly\, 'what does it look like?' With X permutations\
 , graphs\, partitions\, set partitions\, matrices over a finite field. It 
 also covered 'who cares?' That is\, applications in statistics\, computer 
 science and physics/chemistry. Two features were lectures on 'from algorit
 hm to theorem' and 'graph limit theory and its extensions'. the first emph
 asizes the place and usefulness of algorithms to actually pick x uniformly
  (for example\, there are many different ways to sample permutations\, how
  does one efficiently sample partitions or set partitions? say when $n=10^
 6$?) Each such algorithm has an associated set of limit theorems that it '
 makes transparent'. The second topic featured the work of Lovasz and Razbo
 rov and their coworkers. I will review the topics (stopping to be specific
 ) and the course projects\, some of which are turning into publishable pap
 ers.\n
LOCATION:https://stable.researchseminars.org/talk/probabilisticcombinatori
 cs/16/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alexander Semenov (MIPT)
DTSTART:20200925T100000Z
DTEND:20200925T102500Z
DTSTAMP:20260404T094120Z
UID:probabilisticcombinatorics/17
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/proba
 bilisticcombinatorics/17/">Probability thresholds estimates for coloring p
 roperties of random hypergraphs</a>\nby Alexander Semenov (MIPT) as part o
 f Probabilistic Combinatorics Online 2020\n\n\nAbstract\nRecall that for a
 n integer $j$\, a $j$-independent set in a hypergraph $H=(V\,E)$ is a subs
 et $W\\subset V$ such that for every edge $e\\in E: |e\\cap W| \\leq j$. A
  $j$-proper coloring of $H=(V\,E)$ is a partition of the vertex set $V$ of
  $H$ into disjoint union of $j$-independent sets\, so called colors. The $
 j$-chromatic number $\\chi_j(H)$ of $H$ is the minimal number of colors ne
 eded for a $j$-proper coloring of $H$.\n\nWe will talk about our latest re
 sults on colorings of the k-uniform random hypergraph $H(n\,k\,p)$. We are
  interested in asymptotic properties of $H(n\,k\,p)$ to have its $j$-chrom
 atic number 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 constant.\n\nIt can be shown that the previously mentioned property o
 f random hypergraph has a sharp threshold. For the classic case of $(k-1)$
 -chromatic number\, upper and lower bounds for that threshold were investi
 gated by different researchers. It should be also mentioned that the gap b
 etween these bounds in terms of the parameter $c=p{n\\choose k}/n$ has a b
 ounded order $O_k(1)$.\n\nWe are going to present the results from our las
 t series of works where we found very tight bounds for the case of arbitra
 ry $r$ and $1< k-j=o(k^{1/4})$.\n\nThis is joint work with Dmitry Shabanov
 .\n
LOCATION:https://stable.researchseminars.org/talk/probabilisticcombinatori
 cs/17/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jakub Kozik (Jagiellonian University)
DTSTART:20200925T103000Z
DTEND:20200925T105500Z
DTSTAMP:20260404T094120Z
UID:probabilisticcombinatorics/18
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/proba
 bilisticcombinatorics/18/">Bi-uniform property b</a>\nby Jakub Kozik (Jagi
 ellonian University) as part of Probabilistic Combinatorics Online 2020\n\
 n\nAbstract\nHow many edges do we need in order to construct a $k$-uniform
  hypergraph which is not two-colorable?\nThis number\, denoted by $m(k)$\,
  has been intensively studied since its introduction by Erd\\H{o}s and Haj
 nal in 1961.\nAs a result\, the lower bounds have been improved a number o
 f times and nowadays we know that $m(k)=\\Omega(\\sqrt{k/\\log(k)}\\\;2^k)
 $ (Radhakrishnan and Srinivasan 2000).\nThe story of the upper bounds is m
 uch shorter.\nBound $m(k)= O(k^2 \\\;2^k)$\,  obtained by Erd\\H{o}s in 19
 64\, has not been improved since.\nWe are going to discuss what insights c
 an be gained from considering analogous problem for non-uniform hypergraph
 s.\nWe focus on an interesting class of bi-uniform hypergraphs\, i.e. hype
 rgraphs in which there are only two allowed sizes of edges.\nThe class is 
 rich enough to observe the most important coloring obstacles caused by non
 -uniform edges.\nOn the other hand\, having only two sizes of edges elimin
 ates a lot of technical difficulties.\n
LOCATION:https://stable.researchseminars.org/talk/probabilisticcombinatori
 cs/18/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Peleg Michaeli (Tel-Aviv University)
DTSTART:20200925T130000Z
DTEND:20200925T132500Z
DTSTAMP:20260404T094120Z
UID:probabilisticcombinatorics/19
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/proba
 bilisticcombinatorics/19/">Greedy maximal independent sets via local limit
 s</a>\nby Peleg Michaeli (Tel-Aviv University) as part of Probabilistic Co
 mbinatorics Online 2020\n\n\nAbstract\nThe random greedy algorithm for fin
 ding a maximal independent set in a graph has been studied extensively in 
 various settings in combinatorics\, probability\, computer science — and
  even in chemistry.  The algorithm builds a maximal independent set by ins
 pecting the vertices of the graph one at a time according to a random orde
 r\, adding the current vertex to the independent set if it is not connecte
 d to any previously added vertex by an edge.\nIn this talk\, I will presen
 t a natural and general framework for calculating the asymptotics of the p
 roportion of the yielded independent set for sequences of (possibly random
 ) graphs\, involving a useful notion of local convergence. We use this fra
 mework both to give short and simple proofs for results on previously stud
 ied families of graphs\, such as paths and binomial random graphs\, and to
  give new results for other models such as random trees.\n\nThe talk is ba
 sed on joint work with Michael Krivelevich\, Tamás Mészáros and Clara S
 hikhelman.\n
LOCATION:https://stable.researchseminars.org/talk/probabilisticcombinatori
 cs/19/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Felix Joos (Heidelberg University)
DTSTART:20200925T133000Z
DTEND:20200925T135500Z
DTSTAMP:20260404T094120Z
UID:probabilisticcombinatorics/20
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/proba
 bilisticcombinatorics/20/">Dirac-type results for hypergraph decomposition
 s into cycles</a>\nby Felix Joos (Heidelberg University) as part of Probab
 ilistic Combinatorics Online 2020\n\n\nAbstract\nI will discuss recent joi
 nt work with Marcus Kühn and Bjarne Schülke on decompositions of hypergr
 aphs into cycles. One of the results answers a question of Glock\, Kühn a
 nd Osthus and another one is an extension of the well-known result due to 
 Rödl and Rucinski on the minimum degree threshold for Hamilton cycles in 
 k-uniform hypergraphs.\n
LOCATION:https://stable.researchseminars.org/talk/probabilisticcombinatori
 cs/20/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Bhargav Narayanan (Rutgers University)
DTSTART:20200925T140000Z
DTEND:20200925T142500Z
DTSTAMP:20260404T094120Z
UID:probabilisticcombinatorics/21
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/proba
 bilisticcombinatorics/21/">The threshold of the square of the Hamilton cyc
 le</a>\nby Bhargav Narayanan (Rutgers University) as part of Probabilistic
  Combinatorics Online 2020\n\n\nAbstract\nWe show that the threshold for t
 he appearance 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://stable.researchseminars.org/talk/probabilisticcombinatori
 cs/21/
END:VEVENT
BEGIN:VEVENT
SUMMARY:József Balogh (University of Illinois at Urbana-Champaign)
DTSTART:20200925T143000Z
DTEND:20200925T145500Z
DTSTAMP:20260404T094120Z
UID:probabilisticcombinatorics/22
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/proba
 bilisticcombinatorics/22/">Extensions of Mantel’s theorem</a>\nby Józse
 f Balogh (University of Illinois at Urbana-Champaign) as part of Probabili
 stic Combinatorics Online 2020\n\n\nAbstract\nMantel’s theorem is a basi
 c classical theorem of extremal graph theory. There are many different ext
 ensions and generalizations investigated and many open questions remained.
 \nI will talk about four recent results\, including `stability’ and `sup
 ersaturation’ properties.\n\nThe results are partly joined with Clemen\,
  Katona\, Lavrov\, Lidicky\, Linz\, Pfender and Tuza.\n
LOCATION:https://stable.researchseminars.org/talk/probabilisticcombinatori
 cs/22/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Allan Sly (Princeton University)
DTSTART:20200925T160000Z
DTEND:20200925T165500Z
DTSTAMP:20260404T094120Z
UID:probabilisticcombinatorics/23
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/proba
 bilisticcombinatorics/23/">Local functions for the Ising model on the tree
 </a>\nby Allan Sly (Princeton University) as part of Probabilistic Combina
 torics Online 2020\n\n\nAbstract\nThis talk will look at the question of w
 hat processes can or cannot be constructed using local randomness.  Work o
 f Gamarnik and Sudan and later Rahman and Virag showed that local algorith
 ms on random d-regular graphs can only construct independent sets of size 
 approximately half the maximal size when d is large.  Like the optimizatio
 n problem\, a closely related question arising in ergodic theory asks can 
 a particular distribution such as a uniformly random colouring on the tree
  be constructed as a factor of IID\, a type of local functions.   I'll sur
 vey results in this area and describe new work constructing a factor of II
 D for the Ising model on the tree in its intermediate regime.\n\nJoint wor
 k with Danny Nam and Lingfu Zhang.\n
LOCATION:https://stable.researchseminars.org/talk/probabilisticcombinatori
 cs/23/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Xavier Pérez Giménez (University of Nebraska-Lincoln)
DTSTART:20200925T170000Z
DTEND:20200925T175500Z
DTSTAMP:20260404T094120Z
UID:probabilisticcombinatorics/24
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/proba
 bilisticcombinatorics/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
  Probabilistic Combinatorics Online 2020\n\n\nAbstract\nAn $n$-lift of a g
 raph $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 
 chromatic 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\\g
 e 3$ the chromatic number of a random lift of $K_d$ is (asymptotically alm
 ost surely) either $k$ or $k+1$\, where $k$ is the smallest integer satisf
 ying $d < 2k \\log k$. Moreover\, we show that\, for roughly half of the v
 alues of $d$\, the chromatic number is concentrated on $k$. The argument f
 or the upper-bound on the chromatic number uses the small subgraph conditi
 oning method\, 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://stable.researchseminars.org/talk/probabilisticcombinatori
 cs/24/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Michael Krivelevich (Tel Aviv University)
DTSTART:20200924T090000Z
DTEND:20200924T095500Z
DTSTAMP:20260404T094120Z
UID:probabilisticcombinatorics/25
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/proba
 bilisticcombinatorics/25/">Color-biased Hamilton cycles in random graphs</
 a>\nby Michael Krivelevich (Tel Aviv University) as part of Probabilistic 
 Combinatorics Online 2020\n\n\nAbstract\nWe show that a random graph $G(n\
 ,p)$ with the edge probability $p(n)$ above the Hamiltonicity threshold is
  typically such that for any $r$-coloring of its edges\, for a fixed $r\\g
 eq 2$\,  there is a Hamilton cycle with at least $(2/(r+1)-o(1))n$ edges o
 f the same color. This estimate is asymptotically optimal.\n\nA joint work
  with Lior Gishboliner and Peleg Michaeli.\n
LOCATION:https://stable.researchseminars.org/talk/probabilisticcombinatori
 cs/25/
END:VEVENT
END:VCALENDAR