Lutz Warnke
YOU?
Author Swipe
View article: Optimal Hardness of Online Algorithms for Large Independent Sets
Optimal Hardness of Online Algorithms for Large Independent Sets Open
We study the algorithmic problem of finding a large independent set in an Erdös-Rényi random graph $\mathbb{G}(n,p)$. For constant $p$ and $b=1/(1-p)$, the largest independent set has size $2\log_b n$, while a simple greedy algorithm revea…
View article: Local limit of the random degree constrained process
Local limit of the random degree constrained process Open
In this paper we show that the random degree constrained process (a time-evolving random graph model with degree constraints) has a local weak limit, provided that the underlying host graphs are high degree almost regular. We, moreover, id…
View article: On the typical structure of graphs not containing a fixed vertex‐critical subgraph
On the typical structure of graphs not containing a fixed vertex‐critical subgraph Open
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 Osthus, Prömel, and Taraz that addressed the case where is an odd …
View article: The clique chromatic number of sparse random graphs
The clique chromatic number of sparse random graphs Open
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 this paper, we determine the order of magnitude of the clique chromatic number of the random graph …
View article: On the Concentration of the Chromatic Number of Random Graphs
On the Concentration of the Chromatic Number of Random Graphs Open
Shamir and Spencer proved in the 1980s that the chromatic number of the binomial random graph $G_{n,p}$ is concentrated in an interval of length at most $\omega\sqrt{n}$, and in the 1990s Alon showed that an interval of length $\omega\sqrt…
View article: Two-Point Concentration of the Domination Number of Random Graphs
Two-Point Concentration of the Domination Number of Random Graphs Open
We show that the domination number of the binomial random graph G_{n,p} with edge-probability p is concentrated on two values for p \ge n^{-2/3+\eps}, and not concentrated on two values for general p \le n^{-2/3}. This refutes a conjecture…
View article: Extreme local statistics in random graphs: maximum tree extension counts
Extreme local statistics in random graphs: maximum tree extension counts Open
We consider maximum rooted tree extension counts in random graphs, i.e., we consider M_n = \max_v X_v where X_v counts the number of copies of a given tree in G_{n,p} rooted at vertex v. We determine the asymptotics of M_n when the random …
View article: Note on down-set thresholds
Note on down-set thresholds Open
Gunby-He-Narayanan showed that the logarithmic gap predictions of Kahn-Kalai and Talagrand (proved by Park-Pham and Frankston-Kahn-Narayanan-Park) about thresholds of up-sets do not apply to down-sets. In particular, for the down-set of tr…
View article: Lagrange Inversion Formula by Induction
Lagrange Inversion Formula by Induction Open
We present a simple inductive proof of the Lagrange Inversion Formula.
View article: Isomorphisms between dense random graphs
Isomorphisms between dense random graphs Open
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 prove a sharp threshold result for the appearance of G_{n,p_1} …
View article: Bounds on Ramsey games via alterations
Bounds on Ramsey games via alterations Open
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 the binomial random graph does not significantly change the independen…
View article: The jump of the clique chromatic number of random graphs
The jump of the clique chromatic number of random graphs Open
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 Prałat noted that around the clique chromatic number of the random grap…
View article: The degree-restricted random process is far from uniform
The degree-restricted random process is far from uniform Open
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 sequentially adds new random edges so that the degree of each …
View article: Counting extensions revisited
Counting extensions revisited Open
We consider rooted subgraphs in random graphs, that is, extension counts such as (i) the number of triangles containing a given vertex or (ii) the number of paths of length three connecting two given vertices. In 1989, Spencer gave suffici…
View article: On the concentration of the chromatic number of random graphs
On the concentration of the chromatic number of random graphs Open
Shamir and Spencer proved in the 1980s that the chromatic number of the binomial random graph G(n,p) is concentrated in an interval of length at most ω\sqrt{n}, and in the 1990s Alon showed that an interval of length ω\sqrt{n}/\log n suffi…
View article: On the typical structure of graphs not containing a fixed vertex-critical subgraph
On the typical structure of graphs not containing a fixed vertex-critical subgraph Open
This work studies the typical structure of sparse $H$-free graphs, that is, graphs that do not contain a subgraph isomorphic to a given graph $H$. Extending the seminal result of Osthus, Prömel, and Taraz that addressed the case where $H$ …
View article: Preferential attachment without vertex growth: Emergence of the giant component
Preferential attachment without vertex growth: Emergence of the giant component Open
We study the following preferential attachment variant of the classical Erdos-Renyi random graph process. Starting with an empty graph on n vertices, new edges are added one-by-one, and each time an edge is chosen with probability roughly …
View article: The jump of the clique chromatic number of random graphs
The jump of the clique chromatic number of random graphs Open
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 that around p \approx n^{-1/2} the clique chromatic number…
View article: Upper Tail Bounds for Stars
Upper Tail Bounds for Stars Open
For $r \ge 2$, let $X$ be the number of $r$-armed stars $K_{1,r}$ in the binomial random graph $G_{n,p}$. We study the upper tail ${\mathbb P}(X \ge (1+\epsilon){\mathbb E} X)$, and establish exponential bounds which are best possible up t…
View article: Bounds on Ramsey Games via Alterations
Bounds on Ramsey Games via Alterations Open
We present a refinement of the classical alteration method for constructing $H$-free graphs: for suitable edge-probabilities $p$, we show that removing all edges in $H$-copies of the binomial random graph $G_{n,p}$ does not significantly c…
View article: A counterexample to the DeMarco‐Kahn upper tail conjecture
A counterexample to the DeMarco‐Kahn upper tail conjecture Open
Given a fixed graph H , what is the (exponentially small) probability that the number X H of copies of H in the binomial random graph G n , p is at least twice its mean? Studied intensively since the mid 1990s, this so‐called infamous uppe…
View article: On Wormald's differential equation method
On Wormald's differential equation method Open
This note contains a short and simple proof of Wormald's differential equation method (that yields slightly improved approximation guarantees and error probabilities). This powerful method uses differential equations to approximate the tim…
View article: On the critical probability in percolation
On the critical probability in percolation Open
For percolation on finite transitive graphs, Nachmias and Peres suggested a\ncharacterization of the critical probability based on the logarithmic\nderivative of the susceptibility. As a first test-case, we study their\nsuggestion for the …
View article: The phase transition in bounded-size Achlioptas processes
The phase transition in bounded-size Achlioptas processes Open
Perhaps the best understood phase transition is that in the component structure of the uniform random graph process introduced by Erdős and Rényi around 1960. Since the model is so fundamental, it is very interesting to know which features…