76 citations · 533 across the 32 of their papers we have counts for
19 papers · 1 filter
Lagrange Inversion Formula by Induction
Erlang Surya, Lutz Warnke
We present a simple inductive proof of the Lagrange Inversion Formula.
Isomorphisms between dense random graphs
Erlang Surya, Lutz Warnke, Emily Zhu
We consider two variants of the induced subgraph isomorphism problem for two independent binomial random graphs with constant edge-probabilities p_1,p_2. In particular, (i) we prov…
The degree-restricted random process is far from uniform
Michael Molloy, Erlang Surya, Lutz Warnke
The degree-restricted random process is a natural algorithmic model for generating graphs with degree sequence D_n=(d_1, \ldots, d_n): starting with an empty n-vertex graph, it seq…
On the typical structure of graphs not containing a fixed vertex-critical subgraph
Oren Engelberg, Wojciech Samotij, Lutz Warnke
This work studies the typical structure of sparse -free graphs, that is, graphs that do not contain a subgraph isomorphic to a given graph . Extending the seminal result of O…
The jump of the clique chromatic number of random graphs
Lyuben Lichev, Dieter Mitsche, Lutz Warnke
The clique chromatic number of a graph is the smallest number of colors in a vertex coloring so that no maximal clique is monochromatic. In 2016 McDiarmid, Mitsche and Pralat noted…
On the power of random greedy algorithms
He Guo, Lutz Warnke
In this paper we solve two problems of Esperet, Kang and Thomasse as well as Li concerning (i) induced bipartite subgraphs in triangle-free graphs and (ii) van der Waerden numbers.…
Prague dimension of random graphs
He Guo, Kalen Patton, Lutz Warnke
The Prague dimension of graphs was introduced by Nesetril, Pultr and Rodl in the 1970s. Proving a conjecture of Furedi and Kantor, we show that the Prague dimension of the binomial…
Note on Sunflowers
Tolson Bell, Suchakree Chueluecha, Lutz Warnke
A sunflower with p petals consists of p sets whose pairwise intersections are identical. The goal of the sunflower problem is to find the smallest r=r(p,k) such that any family of…
Counting extensions revisited
Matas Šileikis, Lutz Warnke
We consider rooted subgraphs in random graphs, i.e., extension counts such as (i) the number of triangles containing a given vertex or (ii) the number of paths of length three conn…
Bounds on Ramsey Games via Alterations
He Guo, Lutz Warnke
We present a refinement of the classical alteration method for constructing -free graphs: for suitable edge-probabilities , we show that removing all edges in -copies of t…
On Wormald's differential equation method
Lutz Warnke
This note contains a short and simple proof of Wormald's differential equation method (that yields slightly improved approximation guarantees and error probabilities). This powerfu…
Large girth approximate Steiner triple systems
Tom Bohman, Lutz Warnke
In 1973 Erdos asked whether there are n-vertex partial Steiner triple systems with arbitrary high girth and quadratically many triples. (Here girth is defined as the smallest integ…
Packing nearly optimal Ramsey R(3,t) graphs
He Guo, Lutz Warnke
In 1995 Kim famously proved the Ramsey bound R(3,t) \ge c t^2/\log t by constructing an n-vertex graph that is triangle-free and has independence number at most C \sqrt{n \log n}.…
Upper tails for arithmetic progressions in random subsets
Lutz Warnke
We study the upper tail of the number of arithmetic progressions of a given length in a random subset of {1,...,n}, establishing exponential bounds which are best possible up to co…
The typical structure of sparse -free graphs
József Balogh, Robert Morris, Wojciech Samotij +1
Two central topics of study in combinatorics are the so-called evolution of random graphs, introduced by the seminal work of Erdős and Rényi, and the family of -free graphs, tha…
On the method of typical bounded differences
Lutz Warnke
Concentration inequalities are fundamental tools in probabilistic combinatorics and theoretical computer science for proving that random functions are near their means. Of particul…
The C_\ell-free process
Lutz Warnke
The C_\ell-free process starts with the empty graph on n vertices and adds edges chosen uniformly at random, one at a time, subject to the condition that no copy of C_\ell is creat…
When does the K_4-free process stop?
Lutz Warnke
The K_4-free process starts with the empty graph on n vertices and at each step adds a new edge chosen uniformly at random from all remaining edges that do not complete a copy of K…
Dense subgraphs in the H-free process
Lutz Warnke
The H-free process starts with the empty graph on n vertices and adds edges chosen uniformly at random, one at a time, subject to the condition that no copy of H is created, where…