Is there an analogous to Szemerédi regularity lemma in the setting, where I have multi relational graph i.e. I have $n$ nodes, but instead of having edges to be in $\{0,1\}$ i.e. there is an edge or not, I have the edges to be in $\{c_1,c_2,...,c_m\}$ i.e. I have $m$ colours (you may assume one of the colour to be no edge).

  • $\begingroup$ There are many analogs for the colorful setting. Can you be more specific about what you're hoping for? Should we think of m as a constant, or does it depend on n? $\endgroup$
    – GMB
    Aug 4 at 15:30
  • $\begingroup$ @GMB To be honest, I am not exactly clear what I am looking for, I am just sure that some problems in probabilistic logic can be ported to this setting, and any result here can lead to a analogous result there, so basically anything would do ! A survey of such results would be great for starters :) $\endgroup$
    – SagarM
    Aug 4 at 20:15
  • 1
    $\begingroup$ I won't have a better reference for you for a bit, but what I had in mind is the lemma that a refinement of a regularity partition is itself a regularity partition. So I think, for example, you can get a partition that works as a regularity partition for all m colors simultaneously by running the SRL on each individually, and then taking the common refinement. $\endgroup$
    – GMB
    Aug 4 at 22:27

1 Answer 1


(Expanding on my comment)

First off: there are two different common phrasings of the SRL in the literature. Both ought to generalize to your $m$-color setting, but in a slightly different way, so let me set these up first.

Let $G$ be a graph, let $\Pi$ be a vertex partition, and for parts $X, Y \in \Pi$, define their "irregularity" as the maximum fluctuation between the number of edges in a cut between these parts vs. the "expected" number of edges based on the edge density between these parts. That is: $$\text{irreg}(X, Y) := \max \limits_{A \subseteq X, B \subseteq Y}\left|e(A, B) - e(X, Y) \cdot \frac{|A||B|}{|X||Y|}\right|,$$ where $e(A, B)$ counts the number of edges with one endpoint in $A$ and the other in $B$, etc.

  • The "exceptional set" phrasing of the SRL, which is the one quoted in the wiki article you linked, says: for any $n$-node graph and $\varepsilon > 0$, there is a vertex partition $\Pi$ into $\text{tower}(\varepsilon^{-C})$ parts, plus an exceptional set of size $\varepsilon n$, such that all pairs of parts $X, Y \in \Pi$ have irregularity bounded by $\varepsilon|X||Y|$.

  • The other phasing of the SRL, which I vastly prefer, is: there is a vertex partition $\Pi$ into $\text{tower}(\varepsilon^{-C})$ parts (with no exceptional set) such that $$\text{irreg}(\Pi) := \sum_{X, Y \in \Pi} \text{irreg}(X, Y) \le \varepsilon n^2,$$ roughly meaning that the average pair of parts satisfies the irregularity bound from the first phrasing.

You can see the intro of this paper an example of the second phrasing used in the wild. These two phrasings of the SRL are totally equivalent; you can get from one to the other by relatively straightforward combinatorial massaging. One of the many reasons it's more convenient to work with the second definition is the following lemma:

Lemma: For any graph $G$, if vertex partition $\Pi_1$ is a refinement of vertex partition $\Pi_2$, then $\text{irreg}(\Pi_1) \le \text{irreg}(\Pi_2)$.

That means you could take the following approach to your $m$-colored SRL. For each of the $m$ colors, consider the graph that has the edges of color $i$ and omits the edges of all other colors, and compute an SRL partition (under the second definition). Let $\{\Pi_1, \dots, \Pi_m\}$ be your partitions. Then take the common refinement $\Pi^*$ of all these partitions, and due to the above lemma, $\Pi^*$ will satisfy the (second-definition) SRL for all colors simultaneously. The partition size would be about $\text{tower}(\varepsilon^{-C})^m$.

If you really want the exceptional set phrasing, then I expect that a similar method would work, but you would have to be careful to put only an $\varepsilon/m$ fraction of the nodes into your exceptional set for each color. I suspect that this would lead to a significantly worse bound on partition size, something like $\text{tower}((\varepsilon/m)^{-C})$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.