Multiset Colorings of Random Graphs Across Density Regimes
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.
Ada: We're looking at the paper: "Multiset Colorings of Random Graphs Across Density Regimes".
Title and authors: Ada: We're moving into the actual summary of "Multiset Colorings of Random Graphs Across Density Regimes". The authors lay out what they actually proved regarding these bounds and how they connect them to different regimes of graph density.
Emmy: They're essentially taking the existing knowledge about multiset coloring and applying it to random graphs, showing that the structure of random graphs is quite robust regarding this property.
Kolya: I'm interested in the part where they handle these density changes, because that usually tells you something concrete about what happens when you move from sparse to dense structures.
Ada: Exactly. They first prove a three-part bound for fixed densities, and then they extend it to a four-part bound for every fixed edge density between zero and one.
Emmy: And then they get into the near-complete regime, where the graph is polynomially close to being complete, which is where things get really interesting mathematically.
Kolya: When we look at those near-complete graphs, they find that the multiset chromatic number grows in a predictable way based on some parameter beta.
The paper's summary: Ada: So what are the specific improvements they are making here? They aren't just confirming old bounds; they are improving the known results for random graphs.
Emmy: They take the previous best result for G(n, one/two), which was a five-part bound with high probability, and they improve that to a three-part bound by showing that a suitable refinement of an initial two-part partition can be used to make it work <ref:2609.23362#pg1>.
Kolya: That deterministic criterion they mention, where splitting one part into two gives you the multiset coloring, is a big piece of structure for them. They show this holds with high probability in G(n, p).
Ada: And then they connect this to the Linial and Radhakrishnan theory on essential covers of the Boolean cube. That's where the real machinery comes in for proving that criterion holds probabilistically.
Emmy: It seems like they are using this structural idea to bridge the gap between a guaranteed partition and a high-probability coloring result.
The paper's improvements: Ada: So wrapping up, the main results from "Multiset Colorings of Random Graphs Across Density Regimes" are that they establish tighter bounds on the number of parts needed for multiset coloring in random graphs across different density regimes.
Emmy: They show that for fixed densities within a certain range, three parts suffice with high probability, and they also extend this to a four-part bound for all fixed densities.
Kolya: And when the graph is very dense, near complete, they find that the multiset chromatic number behaves like two over some parameter beta plus five, which relates directly to how close the graph is to being fully connected.
Ada: It really shows how random graphs behave differently than complete graphs in this context because of these bounds.
Emmy: This work provides a better understanding of when we can reliably use multiset coloring techniques for large random networks.
Kolya: For me, the part about the growth rate in the near-complete regime is interesting because it gives us a clear picture of how connectivity dictates coloring needs as n gets large.
Ada: That's right, so we can better estimate how complex these structures get when they start looking like a complete graph.
Emmy: We should probably look at what they did with the covariance details next, which explains some of those specific numbers that make the bounds hold.
Conclusion: Ada: So we've seen how they tackle multiset colorings across different densities in random graphs today. The paper is titled "Multiset Colorings of Random Graphs Across Density Regimes."
Emmy: Exactly. They show that for fixed edge densities, you can find a three-part partition with high probability, and then they extend that to a four-part bound for every density between zero and one.
Kolya: And in the near-complete case, where the graph is very dense, they get a growth rate for the multiset chromatic number related to some parameter beta.
Ada: That's right. They use structural ideas like essential covers of the Boolean cube to prove those bounds hold with high probability in random graphs G(n, p).
Emmy: It’s interesting how they connect that deterministic criterion—splitting a part into two—to the probabilistic results, showing it happens with high probability when the edge density is fixed.
Kolya: And when we look at those covariance details for the unresolved edges, they control the variance so that everything behaves predictably as n gets large.
Ada: So what this means for us in general is that we can use these multiset coloring techniques to classify large random networks much faster than before.
Emmy: It suggests a more robust way to find partitions when you're dealing with graphs where the edge density isn't perfectly fixed, but just bounded.
Kolya: The near-complete results are particularly useful because they give us a concrete value for how many parts we might need when the graph is almost completely connected.
Ada: It gives us a strong handle on the complexity of coloring these structures as they grow large.
Emmy: I'm looking forward to seeing how this structural approach connects with their work on symplectic extension graphs next.
Arash Ahadi, Sharareh Alipour
Tehran Institute for Advanced Studies (TeIAS) · Khatam University
math.CO
Submitted: 2026-09-20
Updated: 2026-11-18
License: http://creativecommons.org/licenses/by-sa/4.0/
Importance score: 91/100
The gist: Almost every graph admits a partition of its vertex set into three parts such that no two adjacent vertices have the same number of neighbors in each of the three parts <ref:2609.23362#pg2> The…
Key concepts
- Multiset Chromatic Number ($\chi_m(G)$)
- This is a coloring problem where vertices are assigned colors (parts) such that for any two adjacent vertices, the vector of their neighbor counts in each part is different. Essentially, it ensures that neighbors have distinct 'neighbor profiles' across the partition.
- Fixed-Density Bounds
- This section proves bounds on $\chi_m(G)$ when the edge density $p$ is fixed. It shows that for a specific range of $p$, $\chi_m(G)$ is at most 3 with high probability, relying on structural properties related to essential covers of the Boolean cube.
- Near-Complete Regime Analysis
- This analyzes what happens when a graph is very dense (close to complete). It shows that $\chi_m(G)$ grows proportionally to $2/\beta$, where $\beta$ measures how far the graph is from being complete. This provides a lower bound for the coloring requirement in these highly connected structures.
Terminology
Summary
Almost every graph admits a partition of its vertex set into three parts such that no two adjacent vertices have the same number of neighbors in each of the three parts <ref:2609. p. 0 Multiset Colorings of Random Graphs Across
Density Regimes
Arash Ahadi and Sharareh Alipour
Tehran Institute for Advanced Studies (TeIAS), Khatam University, Iran
Abstract. We show that almost every graph admits a partition of its
vertex set into three parts such that no two adjacent vertices have the
same number of neighbors in each of the three parts. The probabilistic part is reduced to showing that there are only linearly many
residual edges, while every corresponding normal vector has linear support with
a strictly larger constant. Since χm(Kn) = n, it is natural to ask how the multiset chromatic number
grows as a random graph approaches completeness. A landmark intermediate result
of Kalkowski, Karo´nski, and Pfender established the universal bound five [10],
and the conjectured bound three was later proved by Keusch [11]. In our vertexpartition setting, the previously known bound for G(n, 1/2) was likewise five
with high probability [5]. Section 2 proves the fixed-density bounds and Section 3 treats the nearcomplete regime. 2 The Fixed-Density Regime
We first prove the three-part bound for an interval of fixed edge densities and
then the four-part bound for every fixed edge density.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
More generally, for every fixed p ∈ (0, 1), G ∼ G(n, p) satisfies χm(G) ≤ 4 with high probability <ref:2609.23362#pg9>
Fixed-Density Bounds
The paper first proves the three-part bound for an interval of fixed edge densities and then the four-part bound for every fixed edge density Theorem 2.1 states that for a fixed p satisfying 3√3 π/2 p(1 − p)2) Pχm(G) ≤ 3 → 1 (n → ∞) This is achieved by showing that a suitable refinement of a fixed two-part partition can produce a multiset coloring, and that this criterion holds with high probability in G(n, p) The main structural ingredient is the lemma of Linial and Radhakrishnan on essential covers of the Boolean cube
Near-Complete Regime Analysis
The authors determine how χm(G) grows when the graph is polynomially close to complete, finding that for every fixed β ∈ (0, 1) and p = 1 − n−(1−β), with high probability 2β ≤ χm(G) ≤ 2β + 5 This implies that χm(G) = 2/β + O(1) The lower bound is spectral, while the upper bound follows from multinomial anti-concentration and the Lovász Local Lemma
Growth in Near-Complete Graphs
When G ∼ G(n, r) with r = n−(1−β), Theorem 3.1 establishes the lower bound χm(G) ≥ 2/β The proof uses spectral estimates and the symmetric Lovász Local Lemma to show that no multiset coloring with an integer number q of parts less than 2/β exists The upper bound is established by coloring the vertices of H independently and uniformly from [q], where q = floor(2/β) + 5, leading to χm(G) ≤ floor(2/β) + 5
Optimality of Partition Ratio
The ratio A: B = 1: 3 is shown to be optimal within the hyperplane-cover strategy for fixed p This optimality condition is exactly satisfied when the condition 3√3 π/2 p(1 − p)2) > 1 holds, which occurs throughout the interval 0.185 < p < 0. p. 0 In fact,
the three-part bound holds for every fixed 0. 185 < p < 0.Where the paper says it
B Details for Typical Complement Properties
The typical complement properties of H are shown to hold with high probability, including that every degree class has size O(n−β/2) and the clique number is Oβ(1) This allows the upper bound proof to proceed by showing that the probability of a bad event Buv decays exponentially with respect to q < 2/β The dependency graph for bad events is shown to have a maximum degree D = O(n1+3β/2)
Covariance Details for Unresolved-Edge Count
The variance of the number of unresolved edges E(H) is controlled by showing that the diagonal contribution is O(n) and that the covariance contributions from pairs sharing one endpoint or four distinct endpoints are o(n2) This leads to the estimate E(H) = 1/2π√3 (1 − p) + o(1)n with high probability The ratio 1/4: 3/4 is optimal because it maximizes the required inequality for the Linial–Radhakrishnan contradiction
A Technical details for the fixed-density regime
The covariance calculation omitted from Lemma 2.4 shows that P(Iuv = Iuw = 1) is O(n−2), and the total contribution of such pairs to Var(E(H)) is o(n2) This confirms that Chebyshev’s inequality and the estimate for EE(H) yield the required bound The one-edge estimate gives the same asymptotic for P(Ie = 1)P(If = 1), hence Cov(Ie, If) = o(n−2)
B.1 Symmetric Lov´asz Local Lemma
The symmetric form of the Lovász Local Lemma states that if P(Aα) ≤ p for every α ∈ I, and each Aα is independent of all but at most D other events, then if e p(D + 1) ≤ 1, there exists an outcome in which none of the events Aα occurs This lemma is crucial for proving that a coloring exists where no bad event occurs The dependency graph analysis shows that P(Buv)(D + 1) = Oq(n1+β(4−q)/2) This exponent is negative for the chosen q, ensuring the hypothesis of the lemma holds
References
-
N. Alon and J. H. Spencer, The Probabilistic Method, 4th ed. p. 0
p. 0Where the paper says it
The lower bound is spectral, while the upper bound follows from multinomial anti-concentration and the Lov’asz Local Lemma. Keywords: multiset coloring · random graph · Linial–Radhakrishnan theory of essential covers · spectral method 1 Introduction For a graph G = (V, E), let NG(v) denote the open neighborhood of v, and write [r] = {1, .
, Wiley, 2016Where the paper says it
The lower bound is spectral, while the upper bound follows from multinomial anti-concentration and the Lov’asz Local Lemma. Keywords: multiset coloring · random graph · Linial–Radhakrishnan theory of essential covers · spectral method 1 Introduction For a graph G = (V, E), let NG(v) denote the open neighborhood of v, and write [r] = {1, .
-
I. Araujo, J. Balogh, and L. p. 2
p. 2Where the paper says it
a uv w := Auw − Avw (w ∈ B), Suv := |supp(a uv)| = |{w ∈ B : Auw ̸= Avw}|. We shall use the following lemma of Linial and Radhakrishnan [12]; the same statement is recorded explicitly as Lemma 13 in Araujo–Balogh–Mattos [2].
Mattos, New lower bounds for essential covers of the cube, Israel J. p. 0Where the paper says it
a uv w := Auw − Avw (w ∈ B), Suv := |supp(a uv)| = |{w ∈ B : Auw ̸= Avw}|. We shall use the following lemma of Linial and Radhakrishnan [12]; the same statement is recorded explicitly as Lemma 13 in Araujo–Balogh–Mattos [2].
p. 0Where the paper says it
The lower bound is spectral, while the upper bound follows from multinomial anti-concentration and the Lov’asz Local Lemma. Keywords: multiset coloring · random graph · Linial–Radhakrishnan theory of essential covers · spectral method 1 Introduction For a graph G = (V, E), let NG(v) denote the open neighborhood of v, and write [r] = {1, .
Math. 266(1) (2025), 383–403Where the paper says it
The lower bound is spectral, while the upper bound follows from multinomial anti-concentration and the Lov’asz Local Lemma. Keywords: multiset coloring · random graph · Linial–Radhakrishnan theory of essential covers · spectral method 1 Introduction For a graph G = (V, E), let NG(v) denote the open neighborhood of v, and write [r] = {1, .
-
G. Chartrand, F. p. 0
p. 0Where the paper says it
The partition is a multiset coloring if σ(u) ̸= σ(v) for every edge uv ∈ E(G), and the minimum possible number of parts is the multiset chromatic number χm(G) [3]. The notion of multiset coloring was introduced by Chartrand, Okamoto, Salehi, and Zhang [3].
p. 0Where the paper says it
The partition is a multiset coloring if σ(u) ̸= σ(v) for every edge uv ∈ E(G), and the minimum possible number of parts is the multiset chromatic number χm(G) [3]. The notion of multiset coloring was introduced by Chartrand, Okamoto, Salehi, and Zhang [3].
p. 0Where the paper says it
The partition is a multiset coloring if σ(u) ̸= σ(v) for every edge uv ∈ E(G), and the minimum possible number of parts is the multiset chromatic number χm(G) [3]. The notion of multiset coloring was introduced by Chartrand, Okamoto, Salehi, and Zhang [3].
Okamoto, E. p. 0Where the paper says it
The partition is a multiset coloring if σ(u) ̸= σ(v) for every edge uv ∈ E(G), and the minimum possible number of parts is the multiset chromatic number χm(G) [3]. The notion of multiset coloring was introduced by Chartrand, Okamoto, Salehi, and Zhang [3].
p. 0Where the paper says it
The partition is a multiset coloring if σ(u) ̸= σ(v) for every edge uv ∈ E(G), and the minimum possible number of parts is the multiset chromatic number χm(G) [3]. The notion of multiset coloring was introduced by Chartrand, Okamoto, Salehi, and Zhang [3].
Salehi, and P. p. 0Where the paper says it
The partition is a multiset coloring if σ(u) ̸= σ(v) for every edge uv ∈ E(G), and the minimum possible number of parts is the multiset chromatic number χm(G) [3]. The notion of multiset coloring was introduced by Chartrand, Okamoto, Salehi, and Zhang [3].
p. 0Where the paper says it
The partition is a multiset coloring if σ(u) ̸= σ(v) for every edge uv ∈ E(G), and the minimum possible number of parts is the multiset chromatic number χm(G) [3]. The notion of multiset coloring was introduced by Chartrand, Okamoto, Salehi, and Zhang [3].
Zhang, The multiset chromatic number of a graph, Math. p. 0Where the paper says it
The partition is a multiset coloring if σ(u) ̸= σ(v) for every edge uv ∈ E(G), and the minimum possible number of parts is the multiset chromatic number χm(G) [3]. The notion of multiset coloring was introduced by Chartrand, Okamoto, Salehi, and Zhang [3].
p. 0Where the paper says it
The partition is a multiset coloring if σ(u) ̸= σ(v) for every edge uv ∈ E(G), and the minimum possible number of parts is the multiset chromatic number χm(G) [3]. The notion of multiset coloring was introduced by Chartrand, Okamoto, Salehi, and Zhang [3].
Bohem. 134(2) (2009), 191–209Where the paper says it
The partition is a multiset coloring if σ(u) ̸= σ(v) for every edge uv ∈ E(G), and the minimum possible number of parts is the multiset chromatic number χm(G) [3]. The notion of multiset coloring was introduced by Chartrand, Okamoto, Salehi, and Zhang [3].
-
G. Chartrand, F. Okamoto, and P. p. 0
p. 0Where the paper says it
The partition is a multiset coloring if σ(u) ̸= σ(v) for every edge uv ∈ E(G), and the minimum possible number of parts is the multiset chromatic number χm(G) [3]. The notion of multiset coloring was introduced by Chartrand, Okamoto, Salehi, and Zhang [3].
Zhang, The sigma chromatic number of a graph, Graphs Combin. p. 0Where the paper says it
The partition is a multiset coloring if σ(u) ̸= σ(v) for every edge uv ∈ E(G), and the minimum possible number of parts is the multiset chromatic number χm(G) [3]. The notion of multiset coloring was introduced by Chartrand, Okamoto, Salehi, and Zhang [3].
p. 0Where the paper says it
The partition is a multiset coloring if σ(u) ̸= σ(v) for every edge uv ∈ E(G), and the minimum possible number of parts is the multiset chromatic number χm(G) [3]. The notion of multiset coloring was introduced by Chartrand, Okamoto, Salehi, and Zhang [3].
26 (2010), 755–773Where the paper says it
The partition is a multiset coloring if σ(u) ̸= σ(v) for every edge uv ∈ E(G), and the minimum possible number of parts is the multiset chromatic number χm(G) [3]. The notion of multiset coloring was introduced by Chartrand, Okamoto, Salehi, and Zhang [3].
-
A. Dehghan, M. p. 0
p. 0Where the paper says it
Subsequent work treated further graph classes [15], a closely related sum-based variant [4], powers of cycles [6], and generalized corona graphs [7]. Later, Dehghan, Sadeghi, and Ahadi studied the same notion under arXiv:2609.
-R. Sadeghi, and A. p. 0Where the paper says it
Subsequent work treated further graph classes [15], a closely related sum-based variant [4], powers of cycles [6], and generalized corona graphs [7]. Later, Dehghan, Sadeghi, and Ahadi studied the same notion under arXiv:2609.
p. 0Where the paper says it
Subsequent work treated further graph classes [15], a closely related sum-based variant [4], powers of cycles [6], and generalized corona graphs [7]. Later, Dehghan, Sadeghi, and Ahadi studied the same notion under arXiv:2609.
Ahadi, Sigma partitioning: complexity and random graphs, Discrete Math. p. 1Where the paper says it
Subsequent work treated further graph classes [15], a closely related sum-based variant [4], powers of cycles [6], and generalized corona graphs [7]. Later, Dehghan, Sadeghi, and Ahadi studied the same notion under arXiv:2609.
p. 1Where the paper says it
Ahadi and S. Alipour the name sigma partitioning [5], obtaining results on its computational complexity and on random graphs.
Theor. Comput. Sci. 20(2) (2018), Art. 19Where the paper says it
Ahadi and S. Alipour the name sigma partitioning [5], obtaining results on its computational complexity and on random graphs.
-
Y. Feng and W. Lin, A proof of a conjecture on multiset coloring the powers of cycles, Inform. p. 0
p. 0Where the paper says it
The notion of multiset coloring was introduced by Chartrand, Okamoto, Salehi, and Zhang [3]. Subsequent work treated further graph classes [15], a closely related sum-based variant [4], powers of cycles [6], and generalized corona graphs [7].
Process. Lett. 112(17–18) (2012), 678–682Where the paper says it
The notion of multiset coloring was introduced by Chartrand, Okamoto, Salehi, and Zhang [3]. Subsequent work treated further graph classes [15], a closely related sum-based variant [4], powers of cycles [6], and generalized corona graphs [7].
-
Y. Feng and W. Lin, On multiset colorings of generalized corona graphs, Math. p. 0
p. 0Where the paper says it
The notion of multiset coloring was introduced by Chartrand, Okamoto, Salehi, and Zhang [3]. Subsequent work treated further graph classes [15], a closely related sum-based variant [4], powers of cycles [6], and generalized corona graphs [7].
Bohem. 141(4) (2016), 431–455Where the paper says it
The notion of multiset coloring was introduced by Chartrand, Okamoto, Salehi, and Zhang [3]. Subsequent work treated further graph classes [15], a closely related sum-based variant [4], powers of cycles [6], and generalized corona graphs [7].
-
S. Janson, T. Luczak, and A. p. 1
p. 1Where the paper says it
There is a suggestive parallel with the classical 1–2–3 Conjecture for edge-weightings. Karo´nski, Luczak, and Thomason conjectured that weights 1, 2, 3 suffice to distinguish the weighted degrees of adjacent vertices [9].
p. 1Where the paper says it
There is a suggestive parallel with the classical 1–2–3 Conjecture for edge-weightings. Karo´nski, Luczak, and Thomason conjectured that weights 1, 2, 3 suffice to distinguish the weighted degrees of adjacent vertices [9].
p. 1Where the paper says it
There is a suggestive parallel with the classical 1–2–3 Conjecture for edge-weightings. Karo´nski, Luczak, and Thomason conjectured that weights 1, 2, 3 suffice to distinguish the weighted degrees of adjacent vertices [9].
Ruci´nski, Random Graphs, Wiley, 2000Where the paper says it
There is a suggestive parallel with the classical 1–2–3 Conjecture for edge-weightings. Karo´nski, Luczak, and Thomason conjectured that weights 1, 2, 3 suffice to distinguish the weighted degrees of adjacent vertices [9].
-
M. Karo´nski, T. p. 1
p. 1Where the paper says it
There is a suggestive parallel with the classical 1–2–3 Conjecture for edge-weightings. Karo´nski, Luczak, and Thomason conjectured that weights 1, 2, 3 suffice to distinguish the weighted degrees of adjacent vertices [9].
Luczak, and A. Thomason, Edge weights and vertex colours, J. p. 1Where the paper says it
There is a suggestive parallel with the classical 1–2–3 Conjecture for edge-weightings. Karo´nski, Luczak, and Thomason conjectured that weights 1, 2, 3 suffice to distinguish the weighted degrees of adjacent vertices [9].
p. 1Where the paper says it
There is a suggestive parallel with the classical 1–2–3 Conjecture for edge-weightings. Karo´nski, Luczak, and Thomason conjectured that weights 1, 2, 3 suffice to distinguish the weighted degrees of adjacent vertices [9].
Combin. Theory Ser. p. 0Where the paper says it
There is a suggestive parallel with the classical 1–2–3 Conjecture for edge-weightings. Karo´nski, Luczak, and Thomason conjectured that weights 1, 2, 3 suffice to distinguish the weighted degrees of adjacent vertices [9].
p. 0Where the paper says it
More generally, for every fixed p ∈ (0, 1), G ∼ G(n, p) satisfies χm(G) ≤ 4 with high probability. These results are obtained by converting the unresolved edges of a carefully chosen initial partition into hyperplanes of a Boolean cube and applying the Linial–Radhakrishnan theory of essential covers.
p. 0Where the paper says it
More generally, for every fixed p ∈ (0, 1), G ∼ G(n, p) satisfies χm(G) ≤ 4 with high probability. These results are obtained by converting the unresolved edges of a carefully chosen initial partition into hyperplanes of a Boolean cube and applying the Linial–Radhakrishnan theory of essential covers.
p. 0Where the paper says it
More generally, for every fixed p ∈ (0, 1), G ∼ G(n, p) satisfies χm(G) ≤ 4 with high probability. These results are obtained by converting the unresolved edges of a carefully chosen initial partition into hyperplanes of a Boolean cube and applying the Linial–Radhakrishnan theory of essential covers.
p. 0Where the paper says it
More generally, for every fixed p ∈ (0, 1), G ∼ G(n, p) satisfies χm(G) ≤ 4 with high probability. These results are obtained by converting the unresolved edges of a carefully chosen initial partition into hyperplanes of a Boolean cube and applying the Linial–Radhakrishnan theory of essential covers.
p. 0Where the paper says it
More generally, for every fixed p ∈ (0, 1), G ∼ G(n, p) satisfies χm(G) ≤ 4 with high probability. These results are obtained by converting the unresolved edges of a carefully chosen initial partition into hyperplanes of a Boolean cube and applying the Linial–Radhakrishnan theory of essential covers.
B 91(1) (2004), 151–157Where the paper says it
More generally, for every fixed p ∈ (0, 1), G ∼ G(n, p) satisfies χm(G) ≤ 4 with high probability. These results are obtained by converting the unresolved edges of a carefully chosen initial partition into hyperplanes of a Boolean cube and applying the Linial–Radhakrishnan theory of essential covers.
-
M. Kalkowski, M. p. 1
p. 1Where the paper says it
Karo´nski, Luczak, and Thomason conjectured that weights 1, 2, 3 suffice to distinguish the weighted degrees of adjacent vertices [9]. A landmark intermediate result of Kalkowski, Karo´nski, and Pfender established the universal bound five [10], and the conjectured bound three was later proved by Keusch [11].
Karo´nski, and F. p. 1Where the paper says it
Karo´nski, Luczak, and Thomason conjectured that weights 1, 2, 3 suffice to distinguish the weighted degrees of adjacent vertices [9]. A landmark intermediate result of Kalkowski, Karo´nski, and Pfender established the universal bound five [10], and the conjectured bound three was later proved by Keusch [11].
p. 1Where the paper says it
There is a suggestive parallel with the classical 1–2–3 Conjecture for edge-weightings. Karo´nski, Luczak, and Thomason conjectured that weights 1, 2, 3 suffice to distinguish the weighted degrees of adjacent vertices [9].
Pfender, Vertex-coloring edge-weightings: towards the 1–2–3-conjecture, J. p. 1Where the paper says it
There is a suggestive parallel with the classical 1–2–3 Conjecture for edge-weightings. Karo´nski, Luczak, and Thomason conjectured that weights 1, 2, 3 suffice to distinguish the weighted degrees of adjacent vertices [9].
p. 1Where the paper says it
Although complete graphs show that the vertex version admits no universal constant bound, random graphs behave strikingly differently. There is a suggestive parallel with the classical 1–2–3 Conjecture for edge-weightings.
Combin. Theory Ser. B 100(3) (2010), 347–349Where the paper says it
Although complete graphs show that the vertex version admits no universal constant bound, random graphs behave strikingly differently. There is a suggestive parallel with the classical 1–2–3 Conjecture for edge-weightings.
-
R. Keusch, A solution to the 1–2–3 conjecture, J. p. 1
p. 1Where the paper says it
Although complete graphs show that the vertex version admits no universal constant bound, random graphs behave strikingly differently. There is a suggestive parallel with the classical 1–2–3 Conjecture for edge-weightings.
Combin. Theory Ser. B 166 (2024), 183–202Where the paper says it
Although complete graphs show that the vertex version admits no universal constant bound, random graphs behave strikingly differently. There is a suggestive parallel with the classical 1–2–3 Conjecture for edge-weightings.
A Technical details for the fixed-density regime
A.1 Covariance details for the unresolved-edge count
We give here the covariance calculation omitted from the proof of Lemma 2.4 The diagonal contribution is immediate: Var(E(H)) ≤ X e EIe = O(n) Suppose next that two pairs share one endpoint, say e = uv and f = uw After deleting u, v, w, the numbers of neighbors of these three vertices in C − u − v - w are independent Bin(mC, p) variables X, Y, Z with mC = Θ(n) The two required degree equalities become X − Y = r, X − Z = s, where r, s = O(1) Therefore P(X − Y = r, X − Z = s) ≤ sup j P(Y = j) sup j P(Z = j) = O m−1C The A- and B-conditions use disjoint edge variables, so P(Iuv = Iuw = 1) = O(n−2) Since also P(Iuv = 1), P(Iuw = 1) = O(n−1), it follows that Cov(Iuv, Iuw) ≤ P(Iuv = Iuw = 1) + P(Iuv = 1)P(Iuw = 1) There are O(n3) such pairs, so their total covariance contribution is O(n) Finally, let e = uv and f = xy have four distinct endpoints, and expose the four cross edges Z = (Aux, Auy, Avx, Avy) ∈ 014 Conditioned on Z = z, all remaining edge variables used by Ie are disjoint from those used by If, so the two indicators are conditionally independent The exposed edges only change the required degree differences by bounded amounts Hence, uniformly over the sixteen possible values of z, Lemma 2. p. 6 Pairs sharing one endpoint have covariance O(n
−2
) by
conditioning on their three endpoints and using the O(n
−1/2
) maximum binomial
point mass, so their total contribution is O(n). Indeed, after the three endpoints
are exposed, in each of A and B the two required degree equalities involve three
independent binomial variables, and their joint probability is O(n
−1
).Where the paper says it
B Details for the typical complement properties
For every v ∈ V (H), we have dH(v) ∼ Bin(n − 1, r) with mean µ = (n−1)r = (1+o(1))nβ The variables (Xv)v∈L are independent, and Stirling’s formula gives sups P(Xv = s) = O(n−β/2) Hence, for every fixed degree t, Y L t:= lV L t is stochastically dominated by Bin(L, Cn−β/2) For a sufficiently large constant C', Chernoff’s inequality gives, uniformly in t and in the realization of H[L], P Y L t > C'n1−β/2 ≤ exp−omega(n1−β/2) A union bound over all possible t, and the same argument with L and R interchanged, show that every degree class has size O(n1−β/2) with high probability
The symmetric form of the Lovász Local Lemma states that if P(Aα) ≤ p for every α ∈ I, and each Aα is independent of all but at most D other events, then if e p(D + 1) ≤ 1, there exists an outcome in which none of the events Aα occurs This lemma is crucial for proving that a coloring exists where no bad event occurs The dependency graph analysis shows that P(Buv)(D + 1) = Oq(n1+β(4−q)/2) This exponent is negative for the chosen q, ensuring the hypothesis of the lemma holds The final coloring is a multiset coloring of G, proving χm(G) ≤ floor(2/β) + 5
-
N. Alon and J. H. Spencer, The Probabilistic Method, 4th ed., Wiley, 2016
-
I. Araujo, J. Balogh, and L. Mattos, New lower bounds for essential covers of the cube, Israel J. Math. 266(1) (2025), 383–403
-
G. Chartrand, F. Okamoto, E. Salehi, and P. Zhang, The multiset chromatic number of a graph, Math. Bohem. 134(2) (2009), 191–209
-
G. Chartrand, F. Okamoto, and P. Zhang, The sigma chromatic number of a graph, Graphs Combin. 26 (2010), 755–773
-
A. Dehghan, M.-R. Sadeghi, and A. Ahadi, Sigma partitioning: complexity and random graphs, Discrete Math. Theor. Comput. Sci. 20(2) (2018), Art. 19
-
Y. Feng and W. Lin, A proof of a conjecture on multiset coloring the powers of cycles, Inform. Process. Lett. 112(17–18) (2012), 678–682
-
Y. Feng and W. Lin, On multiset colorings of generalized corona graphs, Math. Bohem. 141(4) (2016), 431–455
-
S. Janson, T. Luczak, and A. Ruci´nski, Random Graphs, Wiley, 2000
-
M. Karo´nski, T. Luczak, and A. Thomason, Edge weights and vertex colours, J. Combin. Theory Ser. B 91(1) (2004), 151–157
-
M. Kalkowski, M. Karo´nski, and F. Pfender, Vertex-coloring edge-weightings: towards the 1–2–3-conjecture, J. Combin. Theory Ser. B 100(3) (2010), 347–349
-
R. Keusch, A solution to the 1–2–3 conjecture, J. Combin. Theory Ser.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improve graph partitioning algorithms for massive datasets by leveraging multiset coloring to efficiently group vertices such that adjacent vertices have distinct neighbor count vectors across partitions, improving clustering accuracy beyond standard spectral methods.
-
Develop a high-probability vertex partition strategy for random graphs G(n, p) that guarantees a multiset coloring with at most four parts, enabling faster and more robust classification of large random networks.
-
Create an approximation scheme for determining the multiset chromatic number of sparse random graphs by using the derived upper bound χm(G) <= 4 with high probability, replacing computationally intensive exact methods.
-
Design a scalable algorithm to estimate the growth rate of χm(G) as a graph approaches completeness, allowing real-time assessment of network connectivity and coloring requirements in near-complete structures.
-
Implement a method for constructing valid multiset colorings for graphs with high probability when the edge density is fixed, utilizing the deterministic criterion that
a suitable refinement of a fixed two-part partition by splitting one of its parts into two produces a multiset coloring.
Abstract
We show that almost every graph admits a partition of its vertex set into three parts such that no two adjacent vertices have the same number of neighbors in each of the three parts. Equivalently, for G about G(n,1/2), χ m(G) at most3 with high probability, improving the previously known bound of five. Here χ m(G) denotes the multiset chromatic number of G, the minimum number of parts in a vertex partition whose neighbor-count vectors distinguish every pair of adjacent vertices. In fact, the three-part bound holds for every fixed 0.185<p<0.509. More generally, for every fixed p in(0,1), G about G(n,p) satisfies χ m(G) at most4 with high probability. These results are obtained by converting the unresolved edges of a carefully chosen initial partition into hyperplanes of a Boolean cube and applying the Linial--Radhakrishnan theory of essential covers. We also determine how χ m(G) grows when the graph is polynomially close to complete. For every fixed β in(0,1) and G about G! (n,1-n-(1-β)), with high probability β at most χ m(G) at most β +5. Thus χ m(G)=2/β+O(1). The lower bound is spectral, while the upper bound follows from multinomial anti-concentration and the Lov'asz Local Lemma.
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality