Springe direkt zu Inhalt

# 2018/2019

Talks normally take place Wednesdays from 16:15 at

Arnimallee 6, 14195 Berlin, room SR 032

DateSpeakerTitle

28.08.2019

Alexandra Wesolek
(Simon Fraser University)

Weak rainbow saturation

14.08.2019

Hiệp Hàn
(University of Santiago de Chile)

Quasi-random words and limits of word sequences

10.06.2019

Hao Huang
(Emory University)

A spectral proof of Kleitman's diametric theorem

03.07.2019

Nina Kamcev
(Monash University)

Asymptotic enumeration of regular hypergraphs

26.06.2019

Mara Nehring
(FU Berlin)

Online Ramsey Numbers

19.06.2019

Tamás Mészáros
(FU Berlin)

Unlabeled compression schemes and corner peelings for ample and maximum classes

13.06.2019

Tibor Szabó
(FU Berlin)

Slow bootstrap percolation

05.06.2019

Anurag Bishnoi
(FU Berlin)

A construction for clique-free pseudorandom graphs

22.05.2019

William T. Trotter
(Georgia Institute of Technology)

Dimension and Maximum Degree

15.05.2019

Piotr Micek
(Jagellonian University Krakow and TU Berlin)

p-centered colorings of planar graphs

08.05.2019

Tuan Tran
(ETH Zürich)

Dense induced bipartite subgraphs in triangle-free graphs

02.05.2019

Joonkyung Lee
(Universität Hamburg)

On the extremal number of subdivisions

24.04.2019

Ander Lamaison
(FU Berlin)

Ramsey upper density of infinite graphs

17.04.2019

Simona Boyadzhiyska
(FU Berlin)

On counting problems related to (mutually) orthogonal Latin squares

10.04.2019

Andrew Treglown
(University of Birmingham)

A degree sequence Komlós theorem

06.03.2019

Tibor Szabó
(FU Berlin)

List Ramsey numbers
21.02.2019

Jan van den Heuvel
(LSE)

Partial solutions to Hadwiger's Conjecture
13.02.2019

Ferdinand Ihringer
(Ghent University)

Rank Bounds on the Independence Number

06.02.2019

David Fabian
(FU Berlin)

Rainbow arithmetic progressions and anti-van der Waerden numbers

30.01.2019

László Kozma
(FU Berlin)

Hamiltonicity below Dirac's condition

23.01.2019

Anurag Bishnoi
(FU Berlin)

Non-intersecting Ryser hypergraphs

16.01.2019

Jan Corsten
(LSE)

Erdős-Rothschild problem for five and six colours

09.01.2019

Péter Pál Pach
(BME)

Polynomial Schur's theorem

19.12.2018

Christoph Spiegel
(UPC)

Intervals in the Hales-Jewett Theorem

12.12.2018

Jozef Skokan
(LSE)

The k-colour Ramsey number of odd cycles via non-linear optimisation

05.12.2018

Alexandra Wesolek
(FU Berlin)

Bootstrap percolation in Ore-type graphs

29.11.2018

Hong Liu
(Warwick)

Enumeration in arithmetic setting

28.11.2018

Andrew Newman
(TU Berlin)

Small simplicial complexes with large torsion in homology

21.11.2018

Sophia Elia
(FU Berlin)

A comparison of Quotient Posets

07.11.2018

Patrick Morris
(FU Berlin)

On the discrepancy of permutation families

31.10.2018

Tamás Mészáros
(FU Berlin)

Sample compression schemes

24.10.2018 Roman Glebov
(Ben Gurion University)

Perfect Matchings in Random Subgraphs of Regular Bipartite Graphs

28.08.2019
Alexandra Wesolek (Simon Fraser University)
Weak rainbow saturation

Abstract: Rainbow saturation asks for the minimum number of edges in a t-edge-coloured graph G such that it does not contain a rainbow copy of some fixed graph H but adding any missing edge in any colour from [t] completes a rainbow copy of H. It is an extension of the uncoloured saturation problem which was first studied by Erdős, Hajnal and Moon in 1964. Surprisingly, if H=Ks, the complete graph on s vertices, and G is a graph on n vertices, the minimum number of edges that we need is Θ(n log n) while in the uncoloured saturation problem we only need a linear number of edges. In this work we investigate weak versions of rainbow saturation. In the usual rainbow saturation problem we can choose an arbitrary ordering of the missing edges and add all the missing edges back to the graph in that order and in arbitrary colours completing a rainbow copy each time we add an edge. Instead of being able to add the edges in any ordering to the graph, in a weaker setting we ask for only one specific ordering in which we need to be able to add them back. Is the behaviour for the minimum sets in this case still Θ(n log n)? In the uncoloured setting the bound for this weakened version is linear, so the answer needs to be between these bounds. Moreover, we investigate how the problem changes if we are allowed to choose a colour for every edge that we add. What if we can choose the colours and an ordering? We give answers to those questions. This represents joint work with Shagnik Das.

14.08.2019
Hiệp Hàn (University of Santiago de Chile)
Quasi-random words and limits of word sequences

Abstract: Words are finite sequences of letters over a finite alphabet and in this talk we address two intimately related topics for this object: quasi-randomness and limit theory.With respect to the first topic we study the notion of uniform distribution of letters over intervals, and in the spirit of the famous Chung-Graham-Wilson theorem we provide a list of word properties which are equivalent to this property. This investigation naturally gives rise to a notion of convergent word sequences, and in the second part of our work we develop a limit theory for such sequences. Via this theory we address several problems such as property testing and finite forcibility and obtain as a byproduct a new model of random word sequences.Joint work with Matias Pavez-Signe and Marcos Kiwi.

10.07.2019
Hao Huang (Emory University)
A spectral proof of Kleitman's diametric theorem

Abstract: A classical theorem of Kleitman in extremal combinatorics states that a collection of binary vectors in {0,1}n with diameter d has cardinality at most that of a Hamming ball of radius d/2.

In this talk, we present a new proof of Kleitman's diametric theorem via spectral methods, and discuss some extensions and generalizations of Kleitman's Theorem, as well as a few other related extremal problems.

Joint work with Oleksiy Klurman (KTH) and Cosmin Pohoata (Caltech).

03.07.2019
Nina Kamcev (Monash University)
Asymptotic enumeration of regular hypergraphs

Abstract: We prove an asymptotic formula for the number of k-uniform hypergraphs with a given degree sequence, for a wide range of parameters. In particular, we can asymptotically enumerate d-regular k-graphs of density O(1/k) for 3 ≤ k< n1/10. This extends the recent results for graphs of Liebenau and Wormald.

It follows that within our scope, the distribution of the degree sequence of a random k-uniform hypergraph can be approximated by a sequence of independent random variables with the appropriate binomial distribution. This is joint work with Anita Liebenau and Nick Wormald.

26.06.2019
Mara Nehring (FU Berlin)
Online Ramsey Numbers

Abstract: The Online Ramsey Game is a game on an unbounded number of vertices played by two players, Builder and Painter. Builder builds an edge between two vertices and Painter paints it immediately red or blue. Builder's goal is to build a monochromatic red copy of Km or a monochromatic blue copy of Kn while Painter tries to delay this for as long as possible. The online Ramsey number is the minimum number of edges Builder needs to guarantee a win regardless of Painter's strategy. We will show new lower and upper bounds for the online Ramsey number.

Work by David Conlon, Jacob Fox, Andrey Ginshpun and Xiaoyu He.

19.06.2019
Tamás Mészáros (FU Berlin)
Unlabeled compression schemes and corner peelings for ample and maximum classes

Abstract: I will be presenting recent work by Chalopin, Chepoi, Moran and Warmuth.

"We examine connections between combinatorial notions that arise in machine learning and topological notions in cubical/simplicial geometry. These connections enable to export results from geometry to machine learning. Our first main result is based on a geometric construction by Tracy Hall (2004) of a partial shelling of the cross polytope which can not be extended. We use it to derive a maximum class of VC dimension 3 that has no corners. This refutes several previous works in machine learning from the past 11 years. In particular, it implies that all previous constructions of optimal unlabeled sample compression schemes for maximum classes are erroneous.
On the positive side we present a new construction of an unlabeled sample compression scheme for maximum classes. We leave as open whether our unlabaled sample compression scheme extends to ample (a.k.a. lopsided or extremal) classes, which represent a natural and far-reaching generalization of maximum classes. Towards resolving this question, we provide a geometric characterization in terms of unique sink orientations of the 1-skeletons of associated cubical complexes."

05.06.2019
Anurag Bishnoi (FU Berlin)
A construction for clique-free pseudorandom graphs

Abstract: A construction of Alon and Krivelevich gives highly pseudorandom Kk-free graphs on n vertices with edge density equal to Θ(n-1/(k-2)). In this talk I will give a construction of an infinite family of highly pseudorandom Kk-free graphs with a higher edge density of Θ(n-1/(k-1)), for all k≥3, using the geometry of quadratic forms over finite fields.

(Joint work with Ferdinand Ihringer and Valentina Pepe.)

13.06.2019
Tibor Szabó (FU Berlin)
Slow bootstrap percolation

Abstract: Graph-bootstrap percolation, also known as weak saturation, was introduced by Bollobás in 1968. In this process, we start with initial "infected" set of edges E0, and infect new edges according to a predetermined rule. Given a graph H and a set of previously infected edges Et ⊆ E(Kn), we infect a non-infected edge e if it completes a new copy of H in G=([n], Et ∪ e). A question raised by Bollobás asks for the maximum time the process can run before it stabilizes.  Bollobás,  Przykucki,  Riordan, and  Sahasrabudhe considered this problem for the most natural case where H=Kr. They answered the question for r ≤ 4 and gave a non-trivial  lower bound for every r ≤ 5. They also conjectured that the maximal running time is o(n2) for every integer r. In a joint work with József Balogh, Gal Kronenberg, and Alexey Pokrovskiy we disprove their conjecture for every r ≥ 6 and we give a better lower bound for the case that r=5 using Behrend's construction of large 3-term arithmetic progression-free sets of integers.

22.05.2019
William T. Trotter (Georgia Institute of Technology)
Dimension and Maximum Degree

Abstract: The maximum degree of a poset is the maximum degree in the associated comparability graph. For an integer k, let f(k) denote the maximum dimension of a poset P with maximum degree k. It was shown in 1991 by Erdős, Kierstead and Trotter that f(k) = Ω(k logk). In 1986, Füredi and Kahn showed that f(k) = O(k log2k). Just in 2018, Scott and Wood made the following subtle but dramatic improvement: f(k) = O(log1+o(1)k). We outline the proof which uses an iterated application of the Lovász Local Lemma.

15.05.2019
Piotr Micek (Jagellonian University Krakow and TU Berlin)
p-centered colorings of planar graphs

Abstract: A p-centered coloring of a graph G is a coloring of its vertices such that for every connected subgraph H of G either H receives more than p colors or there is a color that appears exactly once in H. Very recently, we have shown that every planar graph admits a p-centered coloring with O(plog(p)) colors. This improves an O(p19) bound by Pilipczuk&Siebertz. We also know that some planar graphs require Omega(plog(p)) colors. We have tight bounds for outerplanar graphs, stacked triangulations, and graphs of bounded treewidth.

Ongoing work with Stefan Felsner and Felix Schröder.

08.05.2019
Tuan Tran (ETH Zürich)
Dense induced bipartite subgraphs in triangle-free graphs

Abstract: The problem of finding dense induced bipartite subgraphs in H-free graphs has a long history, and was posed 30 years ago by Erdős, Faudree, Pach and Spencer. We obtain several results in this direction. First we prove that any H-free graph with minimum degree at least d contains an induced bipartite subgraph of minimum degree at least c_H log d/log log d, confirming (asymptotically) several conjectures by Esperet, Kang and Thomassé. Complementing this result, we further obtain optimal bounds for this problem in the case of dense triangle-free graphs, and we also answer a question of Erdős, Janson, Luczak and Spencer.

Joint work with Kwan, Letzter and Sudakov.

02.05.2019
Joonkyung Lee (Universität Hamburg)
On the extremal number of subdivisions

Abstract: The extremal number ex(n, H) is the maximum number of edges in an H-free graph with n vertices. When H has chromatic number at least three, the asymptotic behaviour of the extremal number is well understood, but when H is bipartite, the function remains mysterious. We give new estimates for the extremal numbers of various bipartite graphs H, especially if H can be obtained by subdividing edges of another graph H' in certain ways. Joint work with David Conlon and Oliver Janzer.

24.04.2019
Ander Lamaison (FU Berlin)
Ramsey upper density of infinite graphs

Abstract: Let H be an infinite graph. In a two-coloring of the edges of the complete graph on the natural numbers, what is the densest monochromatic subgraph isomorphic to H that we are guaranteed to find? We measure the density of a subgraph by the upper density of its vertex set. This question, in the particular case of the infinite path, was introduced by Erdős and Galvin. Following a recent result for the infinite path, we present bounds on the maximum density for other choices of H, including exact values for a wide class of bipartite graphs.

17.04.2019
Simona Boyadzhiyska (FU Berlin)
On counting problems related to (mutually) orthogonal Latin squares

Abstract: After the question of existence of a combinatorial structure satisfying given properties, a natural and important problem is to determine how many such objects there are. In this talk, we will consider some counting questions related to (mutually) orthogonal Latin squares. We will prove an upper bound on the number of ways to extend a set of k mutually orthogonal Latin squares to a set of k+1 mutually orthogonal Latin squares and discuss some applications, comparing the resulting bounds to previously known lower and upper bounds.

This talk is based on joint work with Shagnik Das and Tibor Szabó.

10.04.2019
Andrew Treglown (Birmingham)
A degree sequence Komlós theorem

Abstract: A classical topic is graph theory concerns finding minimum degree conditions that force a given spanning subgraph in a graph. There has also been interest in generalising such results via degree sequence conditions. Komlós' theorem determines the minimum degree that forces an H-tiling in a graph G covering a given proportion of the vertices in G. (An H-tiling is simply a collection of vertex-disjoint copies of H in G.) In this talk we will discuss a degree sequence generalisation of this result. This is joint work with Hong Liu and Joseph Hyde.

06.03.2019
Tibor Szabó (FU Berlin)
List Ramsey numbers

Abstract: We introduce the list colouring extension of classical Ramsey numbers, investigate when the two Ramsey numbers are equal, and in general, how far apart they can be from each other. We find graph sequences where the two are equal and where they are far apart. For l-uniform cliques we prove that the list Ramsey number is bounded by an exponential function, while it is well-known that the Ramsey number is super-exponential for uniformity at least 3. This is in great contrast to the graph case where we cannot even decide the question of equality for cliques. Joint work with Noga Alon, Matija Bucic, Tom Kalvari, and Eden Kuperwasser.

21.02.2019
Jan van den Heuvel (LSE)
Partial solutions to Hadwiger's Conjecture

Abstract: Hadwiger's Conjecture (1943) asserts that every graph without the complete graph Kt+1 as a minor has a proper vertex-colouring using at most t colours. Since the conjecture is stubbornly refusing to be proved, we might look at relaxed versions of it. In the talk we discuss some results around the following question: If we are given t colours to colour a graph without Kt+1-minor, what kind of vertex-colourings can we guarantee with those t colours?

13.02.2019
Ferdinand Ihringer (Ghent University)
Rank Bounds on the Independence Number

Abstract: Recently, the breakthrough results by Croot, Lev, and Pach on progression-free sets in ℤ4n and by Ellenberg and Gijswijt on cap sets brought new attention to rank arguments for bounding sets in combinatorial problems. We discuss several traditional applications of rank arguments to bound the independence number of a graph. The examples include the orthogonality graph on {-1,1}n, generalized quadrangles, Hermitian dual polar graphs, and quasisymmetric designs.

06.02.2019
David Fabian (FU Berlin)
Rainbow arithmetic progressions and anti-van der Waerden numbers

Abstract: Given a colouring of a set in an ambient abelian group, a rainbow arithmetic progression is an arithmetic progression whose elements receive pairwise distinct colours. We are going to consider two related problems that have been studied over the last years: First we ask whether any k-colouring of [n] with equally sized colour classes admits a rainbow arithmetic progression of length k. The second problem is to find the smallest positive integer r, for which every r-colouring of [n] contains a rainbow k-AP. We shall also have a look at the analogous problems when [n] is replaced by a finite abelian group.

30.01.2019
László Kozma (FU Berlin)
Hamiltonicity below Dirac's condition

Abstract: Dirac's theorem (1952) is a classical result of graph theory, stating that an n-vertex graph (n≥3) is Hamiltonian if every vertex has degree at least n/2. Both the value n/2 and the requirement for every vertex to have high degree are necessary for the theorem to hold. In this work we give efficient algorithms to determine whether a graph is Hamiltonian when either of the two conditions are relaxed.

Joint work with Bart Jansen and Jesper Nederlof.

23.01.2019
Anurag Bishnoi (FU Berlin)
Non-intersecting Ryser hypergraphs

Abstract: A famous conjecture of Ryser states that every r-partite hypergraph has vertex cover number at most r − 1 times the matching number. In recent years, hypergraphs meeting this conjectured bound, known as r-Ryser hypergraphs, have been studied extensively. It was proved by Haxell, Narins and Szabó that all 3-Ryser hypergraphs with matching number ν > 1 are essentially obtained by taking ν disjoint copies of intersecting 3-Ryser hypergraphs. In this talk we will see new infinite families of r-Ryser hypergraphs, for any given matching number ν > 1, that do not contain two vertex disjoint intersecting r-Ryser subhypergraphs.

16.01.2019
Jan Corsten (LSE)
Erdős-Rothschild problem for five and six colours

Abstract: Given positive integers n,r,k, the Erdős-Rothschild problem asks to determine the largest number of r-edge-colourings without monochromatic k-cliques a graph on n vertices can have. In the case of triangles, i.e. when k=3, the solution is known for r = 2,3,4. We investigate the problem for five and six colours.

09.01.2019
Péter Pál Pach (BME)
Polynomial Schur's theorem

Abstract: We consider the Ramsey problem for the equation x+y=p(z), where p is a polynomial with integer coefficients. Under the assumption that p(1)p(2) is even we show that for any 2-colouring of ℕ the equation x+y=p(z) has infinitely many monochromatic solutions. Indeed, we show that the number of monochromatic solutions with x,y,z∈ {1,2,\dots,n} is at least n2/d^3-o(1), where d=deg p.

On the other hand, when p(1)p(2) is odd, that is, when p attains only odd values, then there might not be any monochromatic solution, e.g., this is the case when we colour the integers according to their parity. We give a characterization of all 2-colourings avoiding monochromatic solutions to x+y=p(z).

This is a joint work with Hong Liu and Csaba Sándor.

19.12.2018
Christoph Spiegel (UPC)
Intervals in the Hales-Jewett Theorem

Abstract:  The Hales–Jewett Theorem states that any r–colouring of [m]n contains a monochromatic combinatorial line if n is large enough. Shelah’s proof of the theorem implies that for m = 3 there always exists a monochromatic combinatorial lines whose set of active coordinates is the union of at most r intervals. I will present some recent findings relating to this observation. This is joint work with Nina Kamcev.

12.12.2018
Jozef Skokan (LSE)
The k-colour Ramsey number of odd cycles via non-linear optimisation

Abstract:  For a graph G, the k-colour Ramsey number Rk(G) is the least integer N such that every k-colouring of the edges of the complete graph KN contains a monochromatic copy of G. Let  Cn denote the cycle on n vertices. We show that for fixed k > 2  and n odd and sufficiently large,

Rk(Cn) = 2k-1(n-1) + 1.

This generalises a result of Kohayakawa, Simonovits and Skokan and resolves a conjecture of Bondy and Erdős for large n. We also establish a surprising correspondence between extremal k-colourings for this problem and perfect matchings in the hypercube Qk. This allows us to in fact prove a stability-type generalisation of the  above. The proof is analytic in nature, the first step of which is to use the Regularity Lemma to relate this problem in Ramsey theory to one in convex optimisation.

This is joint work with Matthew Jenssen.

05.12.2018
Alexandra Wesolek (FU Berlin)
Bootstrap percolation in Ore-type graphs

Abstract: In the r-neighbour bootstrap process on a graph G we start with an initial set of infected vertices A0 ⊆ V(G) and a new vertex gets infected as soon as it has r infected neighbours. We call A0 percolating if an infection of A0 infects all of our graph. Under which conditions on G can we find a small percolating set A0? In general, the denser our graph is the easier it is to infect new vertices as the initially infected vertices share potentially more neighbours. If v(G) ≤ r then we need to infect at least r vertices initially to infect all of our graph otherwise we will not be able to infect any new vertices during the bootstrap process. Gunderson showed that if a graph G on n vertices has minimum degree δ(G) ≤ ⌊ n/2 ⌋ + r - 3 then we can always find a percolating set of size r (if r ≤ 4 and n is big enough). How much can we decrease the minimum degree conditions if we are initially allowed to infect r+k vertices for k ∈ ℕ? What if we consider more general graphs where the sum of the degrees of any two non-adjacent vertices x and y is deg(x) + deg(y) ≤ D? This is more general because if a graph G has δ(G) = D/2 then for any two vertices in G it holds that deg(x) + deg(y) ≤ D. In this talk we give conditions on D=D(r,k) that guarantee a percolating set of size r + k, answering both open questions at once for small enough k=k(r).

29.11.2018
Hong Lius (Warwick)
Enumeration in arithmetic setting

Abstract: I will discuss several recent extremal results on enumerating subsets of integers/groups with various additive and multiplicative constraints.

28.11.2018
Andrew Newman (TU Berlin)
Small simplicial complexes with large torsion in homology

Abstract: From the work of Kalai on ℚ-acyclic complexes it is known that for d ≥ 2 a d-dimensional simplicial complex on n vertices can have enormous torsion, on the order of exp(Θd(nd)), in its (d-1)st homology group. However, explicit constructions of complexes which realize this enormous-torsion phenomenon have been somewhat rare. Therefore, in this talk we consider and affirmatively answer the following inverse question: Given a finite abelian group of order m, can one always construct a d-dimensional simplicial complex on Θd((log m)1/d) vertices which realizes the given group in its (d - 1)st homology group?

21.11.2018
Sophia Elia (FU Berlin)
A comparison of Quotient Posets

Abstract: Given an equivalence relation on the elements of a poset, place a new relation on the equivalence classes of elements. If this new relation is reflexive, antisymmetric, and transitive, then a quotient poset is created. We survey different types of quotient posets and see how they compare. In particular, we look at quotient posets that arise from lattice congruences, order-preserving group actions, and as images of surjective maps. We characterize quotient posets that correspond to a certain relation on equivalence classes by defining a sequence related to transitivity. Then we look at an application of quotient posets arising from order-preserving group actions. Let Hom(P,n) be the set of order-preserving maps from a poset P to a chain with $n$ elements. Stanley showed that |Hom(P,n)| is given by a polynomial in $n$. Given an order-preserving group action on P, there is an induced group action on Hom(P,n). Katharina Jochemko showed that the number of maps in Hom(P,n)up to equivalence under the induced group action is also polynomial in $n$ using quotient posets. We touch on an alternative approach to the proof through the Ehrhart theory of order polytopes.

31.10.2018
Patrick Morris (FU Berlin)
On the discrepancy of permutation families

Abstract: For a set family S⊆ 2n, the discrepancy of S is

disc(S):=minχ:[n]→±1 maxS∈ S |∑x∈χ(x)|.

One can think of this as a colouring problem. Given a set system, we are interested in colouring the ground set red/blue such that in every set the difference between the number of red and number of blue points is as small as possible. Given a set of permutations π1,...,πk on [n], we can define a set family S1,...,πk) by taking all sets that occur as intervals in each of the permutations. Formally,

S1,...,πk):={ {πj(x),πj(x+1),...,πj(y)} : 1≤x≤y≤n, j∈[k] }.

How large can the discrepancy of such a family be?

It turns out that for any n∈ ℕ and two permutations, π,σ on [n], we have that disc(S(π,σ))≤ 2. What about three permutations?  Beck conjectured (around 1987) that this should also be bounded by a constant. In 2009, Matoušek described this as ``one of the most tantalising questions in combinatorial discrepancy". In this talk, we will present the eventual resolution of this conjecture by Newman and Nikolov in 2011. The talk will end with an invitation to an open problem.

31.10.2018
Tamás Mészáros (FU Berlin)
Sample compression schemes

Abstract: In this talk we concentrate on two fundamental concepts of classical machine learning theory: learning and compression. Motivated by the fact that if a concept class admits a small sample compression scheme then it is efficiently learnable (Littlestone and Warmuth), we propose to study the relationship between the size of sample compression schemes and the combinatorial notion of VC dimension. In particular, we propose several directions to tackle the compression scheme conjecture which states that the smallest possible size of a sample compression scheme is linear in the VC dimension of the underlying concept class.

24.10.2018
Roman Glebov (Ben Gurion University)
Perfect Matchings in Random Subgraphs of Regular Bipartite Graphs

Abstract: Consider the random process in which the edges of a graph G are added one by one in a random order. A classical result states that if G is the complete graph K2n or the complete bipartite graph Kn,n, then typically a perfect matching appears at the moment at which the last isolated vertex disappears. We extend this result to arbitrary k-regular bipartite graphs G on 2n vertices for all k=Ω(n). Surprisingly, this is not the case for smaller values of k. We construct sparse bipartite k-regular graphs in which the last isolated vertex disappears long before a perfect matching appears.  Joint work with Zur Luria and Michael Simkin.