Multiset Colorings of Random Graphs Across Density Regimes

arXiv:2609.23362 · math.CO · Submitted 2026-09-20 · Read on arXiv

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

Where the paper says it

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.

23362#pg2> The multiset chromatic number of G, denoted as χm(G), is shown to be at most 3 with high probability for a random graph G ∼ G(n, 1/2) <ref:2609. p. 1
Where the paper says it

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.

23362#pg6> This result improves the previously known bound of five <ref:2609. p. 1
Where the paper says it

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].

23362#pg5> The three-part bound holds for every fixed p in the interval 0. p. 1
Where the paper says it

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.

185

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

Where the paper says it

In fact, the three-part bound holds for every fixed 0. 185 < p < 0.

509

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

  1. N. Alon and J. H. Spencer, The Probabilistic Method, 4th ed. p. 0

    Where 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, .

    p. 0
    Where 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, 2016

  2. I. Araujo, J. Balogh, and L. p. 2

    Where 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. 2
    Where 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. 0
    Where 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, .

    p. 0
    Where 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–403

  3. G. Chartrand, F. p. 0

    Where 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. 0
    Where 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. 0
    Where 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. 0
    Where 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. 0
    Where 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. 0
    Where 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. 0
    Where 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. 0
    Where 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. 0
    Where 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. 0
    Where 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–209

  4. G. Chartrand, F. Okamoto, and P. p. 0

    Where 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. 0
    Where 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. 0
    Where 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. 0
    Where 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–773

  5. A. Dehghan, M. p. 0

    Where 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. 0
    Where 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. 0
    Where 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. 0
    Where 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. 1
    Where the paper says it

    Ahadi and S. Alipour the name sigma partitioning [5], obtaining results on its computational complexity and on random graphs.

    p. 1
    Where 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. 19

  6. Y. Feng and W. Lin, A proof of a conjecture on multiset coloring the powers of cycles, Inform. p. 0

    Where 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].

    p. 0
    Where 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–682

  7. Y. Feng and W. Lin, On multiset colorings of generalized corona graphs, Math. p. 0

    Where 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].

    p. 0
    Where 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–455

  8. S. Janson, T. Luczak, and A. p. 1

    Where 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. 1
    Where 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. 1
    Where 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. 1
    Where 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, 2000

  9. M. Karo´nski, T. p. 1

    Where 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. 1
    Where 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. 1
    Where 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. 1
    Where 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. 0
    Where 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. 0
    Where 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. 0
    Where 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. 0
    Where 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. 0
    Where 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. 0
    Where 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–157

  10. M. Kalkowski, M. p. 1

    Where 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. 1
    Where 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. 1
    Where 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. 1
    Where 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. 1
    Where 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.

    p. 1
    Where 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–349

  11. R. Keusch, A solution to the 1–2–3 conjecture, J. p. 1

    Where 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.

    p. 1
    Where 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–202

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

Where the paper says it

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 ).

5 gives P(Ie = 1 Z = z) = 1 + o(1) π√3 (1 − p)n, P(If = 1 Z = z) = 1 + o(1) π√3 (1 − p)n Therefore P(Ie = If = 1) = E[P(Ie = 1 Z)P(If = 1 Z)] = 1 + o(1) 3π/2 (1 − p)2)n2 The one-edge estimate gives the same asymptotic for P(Ie = 1)P(If = 1), and hence Cov(Ie, If) = o(n−2) There are O(n4) vertex-disjoint pairs of pairs, so their total contribution is o(n2)

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

  1. N. Alon and J. H. Spencer, The Probabilistic Method, 4th ed., Wiley, 2016

  2. I. Araujo, J. Balogh, and L. Mattos, New lower bounds for essential covers of the cube, Israel J. Math. 266(1) (2025), 383–403

  3. G. Chartrand, F. Okamoto, E. Salehi, and P. Zhang, The multiset chromatic number of a graph, Math. Bohem. 134(2) (2009), 191–209

  4. G. Chartrand, F. Okamoto, and P. Zhang, The sigma chromatic number of a graph, Graphs Combin. 26 (2010), 755–773

  5. A. Dehghan, M.-R. Sadeghi, and A. Ahadi, Sigma partitioning: complexity and random graphs, Discrete Math. Theor. Comput. Sci. 20(2) (2018), Art. 19

  6. 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

  7. Y. Feng and W. Lin, On multiset colorings of generalized corona graphs, Math. Bohem. 141(4) (2016), 431–455

  8. S. Janson, T. Luczak, and A. Ruci´nski, Random Graphs, Wiley, 2000

  9. M. Karo´nski, T. Luczak, and A. Thomason, Edge weights and vertex colours, J. Combin. Theory Ser. B 91(1) (2004), 151–157

  10. 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

  11. 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

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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