Showing 1–13 of 13 results for author: Warnke, L

The clique chromatic number of sparse random graphs

Authors: Manuel Fernandez V, Lutz Warnke

Abstract: 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 G_{n,p} for most edge-probabilities p in the range n^{-2/5} \ll p \ll 1. This resolves open problems and questions of Lichev, Mitsche and Warnke as well as Alon… ▽ More 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 G_{n,p} for most edge-probabilities p in the range n^{-2/5} \ll p \ll 1. This resolves open problems and questions of Lichev, Mitsche and Warnke as well as Alon and Krievelevich. One major proof difficulty stems from high-degree vertices, which prevent maximal cliques in their neighborhoods: we deal with these vertices by an intricate union bound argument, that combines the probabilistic method with new degree counting arguments in order to enable Janson's inequality. This way we determine the asymptotics of the clique chromatic number of G_{n,p} in some ranges, and discover a surprising new phenomenon that contradicts earlier predictions for edge-probabilities p close to n^{-2/5}. △ Less

Submitted 5 March, 2024; originally announced March 2024.

Comments: 24 pages

MSC Class: 05C15; 05C80; 60C05

Isomorphisms between dense random graphs

Authors: Erlang Surya, Lutz Warnke, Emily Zhu

Abstract: We consider two variants of the induced subgraph isomorphism problem for two independent binomial random graphs with constant edge-probabilities p_1,p_2. We resolve several open problems of Chatterjee and Diaconis, and also confirm simulation-based predictions of McCreesh, Prosser, Solnon and Trimble: (i) we prove a sharp threshold result for the appearance of G_{n,p_1} as an induced subgraph of G… ▽ More We consider two variants of the induced subgraph isomorphism problem for two independent binomial random graphs with constant edge-probabilities p_1,p_2. We resolve several open problems of Chatterjee and Diaconis, and also confirm simulation-based predictions of McCreesh, Prosser, Solnon and Trimble: (i) we prove a sharp threshold result for the appearance of G_{n,p_1} as an induced subgraph of G_{N,p_2}, (ii) we show two-point concentration of the maximum common induced subgraph of G_{N, p_1} and G_{N,p_2}, and (iii) we show that the number of induced copies of G_{n,p_1} in G_{N,p_2} has an unusual limiting distribution. △ Less

Submitted 8 May, 2023; originally announced May 2023.

Comments: 26 pages, 2 figures

MSC Class: 05C80; 05C60; 60C05

The degree-restricted random process is far from uniform

Authors: Michael Molloy, Erlang Surya, Lutz Warnke

Abstract: 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 vertex v_i remains at most d_i. Wormald conjectured in 1999 that, for d-regular degree sequences D_n, the final graph of this process is similar to a uniform ran… ▽ More 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 vertex v_i remains at most d_i. Wormald conjectured in 1999 that, for d-regular degree sequences D_n, the final graph of this process is similar to a uniform random d-regular graph. In this paper we show that, for degree sequences D_n that are not nearly regular, the final graph of the degree-restricted random process differs substantially from a uniform random graph with degree sequence D_n. The combinatorial proof technique is our main conceptual contribution: we adapt the switching method to the degree-restricted process, demonstrating that this enumeration technique can also be used to analyze stochastic processes (rather than just uniform random models, as before). △ Less

Submitted 1 November, 2022; originally announced November 2022.

Comments: 32 pages, 3 figures

MSC Class: 05C80; 60C05; 68W20; 60G99; 90B15

On the concentration of the chromatic number of random graphs

Authors: Erlang Surya, Lutz Warnke

Abstract: 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 suffices for constant edge-probabilities p \in (0,1). We prove a similar logarithmic improvement of the Shamir-Spencer concentration results for the sparse case p=p(n… ▽ More 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 suffices for constant edge-probabilities p \in (0,1). We prove a similar logarithmic improvement of the Shamir-Spencer concentration results for the sparse case p=p(n) \to 0, and uncover a surprising concentration `jump' of the chromatic number in the very dense case p=p(n) \to 1. △ Less

Submitted 19 December, 2023; v1 submitted 3 January, 2022; originally announced January 2022.

Comments: 11 pages, 1 figure. Minor edits, to appear in The Electronic Journal of Combinatorics

MSC Class: 05C80; 05C15; 60C05

Journal ref: The Electronic Journal of Combinatorics 31 (2024), Paper 1.44, 18pp

The jump of the clique chromatic number of random graphs

Authors: Lyuben Lichev, Dieter Mitsche, Lutz Warnke

Abstract: 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 of the random graph G_{n,p} changes by n^{Ω(1)} when we increase the edge-probability p by n^{o(1)}, but left the details of this surprising phenomenon as an op… ▽ More 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 of the random graph G_{n,p} changes by n^{Ω(1)} when we increase the edge-probability p by n^{o(1)}, but left the details of this surprising phenomenon as an open problem. We settle this problem, i.e., resolve the nature of this polynomial `jump' of the clique chromatic number of the random graph G_{n,p} around edge-probability p \approx n^{-1/2}. Our proof uses a mix of approximation and concentration arguments, which enables us to (i) go beyond Janson's inequality used in previous work and (ii) determine the clique chromatic number of G_{n,p} up to logarithmic factors for any edge-probability p. △ Less

Submitted 25 May, 2021; originally announced May 2021.

Comments: 14 pages

MSC Class: 05C15; 05C80; 60C05

Journal ref: Random Structures and Algorithms, 62 (2023), 1016-1034

On the power of random greedy algorithms

Authors: He Guo, Lutz Warnke

Abstract: 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. Each time random greedy algorithms allow us to go beyond the Lovasz Local Lemma or alteration method used in previous work, illustrating the power of the algorithmic approach to the probabilistic method. 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. Each time random greedy algorithms allow us to go beyond the Lovasz Local Lemma or alteration method used in previous work, illustrating the power of the algorithmic approach to the probabilistic method. △ Less

Submitted 3 April, 2022; v1 submitted 15 April, 2021; originally announced April 2021.

Comments: 14 pages; minor edits; to appear in European Journal of Combinatorics

MSC Class: 05D40; 11B25; 05D10

Journal ref: European Journal of Combinatorics 105 (2022), 103551

Prague dimension of random graphs

Authors: He Guo, Kalen Patton, Lutz Warnke

Abstract: 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 random graph is typically of order n/log n for constant edge-probabilities. The main new proof ingredient is a Pippenger-Spencer type edge-coloring result for random hypergraphs with large uniformities, i.e., edges of s… ▽ More 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 random graph is typically of order n/log n for constant edge-probabilities. The main new proof ingredient is a Pippenger-Spencer type edge-coloring result for random hypergraphs with large uniformities, i.e., edges of size O(log n). △ Less

Submitted 18 November, 2020; originally announced November 2020.

Comments: 20 pages

Journal ref: Combinatorica 43 (2023), 853-884

Note on Sunflowers

Authors: Tolson Bell, Suchakree Chueluecha, Lutz Warnke

Abstract: 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 r^k distinct k-element sets contains a sunflower with p petals. Building upon a breakthrough of Alweiss, Lovett, Wu and Zhang from 2019, Rao proved that r=O(p log(pk)) suffices; this bound was reproved by Tao in 2020. In… ▽ More 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 r^k distinct k-element sets contains a sunflower with p petals. Building upon a breakthrough of Alweiss, Lovett, Wu and Zhang from 2019, Rao proved that r=O(p log(pk)) suffices; this bound was reproved by Tao in 2020. In this short note we record that r=O(p log k) suffices, by using a minor variant of the probabilistic part of these recent proofs. △ Less

Submitted 17 March, 2021; v1 submitted 19 September, 2020; originally announced September 2020.

Comments: 3 pages; based on 2020 REU; minor edits; to appear in Discrete Mathematics

MSC Class: 05D05; 05D40

Journal ref: Discrete Mathematics 344 (2021), 112340

Bounds on Ramsey Games via Alterations

Authors: He Guo, Lutz Warnke

Abstract: 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 change the independence number. This differs from earlier alteration approaches of Erdős and Krivelevich, who obtained similar guarantees by removing one edge fro… ▽ More 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 change the independence number. This differs from earlier alteration approaches of Erdős and Krivelevich, who obtained similar guarantees by removing one edge from each $H$-copy (instead of all of them). We demonstrate the usefulness of our refined alternation method via two applications to online graph Ramsey games, where it enables easier analysis. △ Less

Submitted 23 April, 2023; v1 submitted 5 September, 2019; originally announced September 2019.

Comments: 10 pages; minor edits; to appear in the Journal of Graph Theory

MSC Class: 05C55; 05C80; 05D10; 05D40

Journal ref: Journal of Graph Theory 104 (2023), 470-484

On Wormald's differential equation method

Authors: Lutz Warnke

Abstract: 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 time-evolution/dynamics of random processes and algorithms. 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 time-evolution/dynamics of random processes and algorithms. △ Less

Submitted 15 June, 2019; v1 submitted 21 May, 2019; originally announced May 2019.

Comments: 7 pages; minor corrections

MSC Class: 60C05; 68W20; 60J10; 68Q87

Preferential attachment without vertex growth: emergence of the giant component

Authors: Svante Janson, Lutz Warnke

Abstract: 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 proportional to the product of the current degrees of its endpoints (note that the vertex set is fixed). We determine the asymptotic size of the giant component… ▽ More 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 proportional to the product of the current degrees of its endpoints (note that the vertex set is fixed). We determine the asymptotic size of the giant component in the supercritical phase, confirming a conjecture of Pittel from 2010. Our proof uses a simple method: we condition on the vertex degrees (of a multigraph variant), and use known results for the configuration model. △ Less

Submitted 26 April, 2019; originally announced April 2019.

Comments: 20 pages

MSC Class: 05C80; 60C05; 90B15

Journal ref: Annals of Applied Probability 31 (2021), 1523-1547

Packing nearly optimal Ramsey R(3,t) graphs

Authors: He Guo, Lutz Warnke

Abstract: 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}. We extend this celebrated result, which is best possible up to the value of the constants, by approximately decomposing the complete graph K_n into a packing of such nearly optimal Ramsey R(3,t) graphs. More precisely,… ▽ More 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}. We extend this celebrated result, which is best possible up to the value of the constants, by approximately decomposing the complete graph K_n into a packing of such nearly optimal Ramsey R(3,t) graphs. More precisely, for any ε>0 we find an edge-disjoint collection (G_i)_i of n-vertex graphs G_i \subseteq K_n such that (a) each G_i is triangle-free and has independence number at most C_ε\sqrt{n \log n}, and (b) the union of all the G_i contains at least (1-ε)\binom{n}{2} edges. Our algorithmic proof proceeds by sequentially choosing the graphs G_i via a semi-random (i.e., Rodl nibble type) variation of the triangle-free process. As an application, we prove a conjecture in Ramsey theory by Fox, Grinshpun, Liebenau, Person, and Szabo (concerning a Ramsey-type parameter introduced by Burr, Erdos, Lovasz in 1976). Namely, denoting by s_r(H) the smallest minimum degree of r-Ramsey minimal graphs for H, we close the existing logarithmic gap for H=K_3 and establish that s_r(K_3) = Θ(r^2 \log r). △ Less

Submitted 15 November, 2017; originally announced November 2017.

Comments: 22 pages

MSC Class: 05C55; 05C80; 05D10; 60C05

Journal ref: Combinatorica 40 (2020), 63-103

On the method of typical bounded differences

Authors: Lutz Warnke

Abstract: Concentration inequalities are fundamental tools in probabilistic combinatorics and theoretical computer science for proving that random functions are near their means. Of particular importance is the case where f(X) is a function of independent random variables X=(X_1, ..., X_n). Here the well known bounded differences inequality (also called McDiarmid's or Hoeffding-Azuma inequality) establishes… ▽ More Concentration inequalities are fundamental tools in probabilistic combinatorics and theoretical computer science for proving that random functions are near their means. Of particular importance is the case where f(X) is a function of independent random variables X=(X_1, ..., X_n). Here the well known bounded differences inequality (also called McDiarmid's or Hoeffding-Azuma inequality) establishes sharp concentration if the function f does not depend too much on any of the variables. One attractive feature is that it relies on a very simple Lipschitz condition (L): it suffices to show that |f(X)-f(X')| \leq c_k whenever X,X' differ only in X_k. While this is easy to check, the main disadvantage is that it considers worst-case changes c_k, which often makes the resulting bounds too weak to be useful. In this paper we prove a variant of the bounded differences inequality which can be used to establish concentration of functions f(X) where (i) the typical changes are small although (ii) the worst case changes might be very large. One key aspect of this inequality is that it relies on a simple condition that (a) is easy to check and (b) coincides with heuristic considerations why concentration should hold. Indeed, given an event Γthat holds with very high probability, we essentially relax the Lipschitz condition (L) to situations where Γoccurs. The point is that the resulting typical changes c_k are often much smaller than the worst case ones. To illustrate its application we consider the reverse H-free process, where H is 2-balanced. We prove that the final number of edges in this process is concentrated, and also determine its likely value up to constant factors. This answers a question of Bollobás and Erdős. △ Less

Submitted 23 December, 2012; originally announced December 2012.

Comments: 25 pages

MSC Class: 60C05 (Primary) 60F10; 60B99 (Secondary)

Journal ref: Combinator. Probab. Comp. 25 (2016) 269-299