<p>(Expanding on my comment)</p>
<p>First off: there are two different common phrasings of the SRL in the literature. Both ought to generalize to your <span class="math-container">$m$</span>-color setting, but in a slightly different way, so let me set these up first.</p>
<p>Let <span class="math-container">$G$</span> be a graph, let <span class="math-container">$\Pi$</span> be a vertex partition, and for parts <span class="math-container">$X, Y \in \Pi$</span>, define their &quot;irregularity&quot; as the maximum fluctuation between the number of edges in a cut between these parts vs. the &quot;expected&quot; number of edges based on the edge density between these parts.  That is:
<span class="math-container">$$\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|,$$</span>
where <span class="math-container">$e(A, B)$</span> counts the number of edges with one endpoint in <span class="math-container">$A$</span> and the other in <span class="math-container">$B$</span>, etc.</p>
<ul>
<li><p>The &quot;exceptional set&quot; phrasing of the SRL, which is the one quoted in the wiki article you linked, says: for any <span class="math-container">$n$</span>-node graph and <span class="math-container">$\varepsilon &gt; 0$</span>, there is a vertex partition <span class="math-container">$\Pi$</span> into <span class="math-container">$\text{tower}(\varepsilon^{-C})$</span> parts, plus an exceptional set of size <span class="math-container">$\varepsilon n$</span>, such that all pairs of parts <span class="math-container">$X, Y \in \Pi$</span> have irregularity bounded by <span class="math-container">$\varepsilon|X||Y|$</span>.</p>
</li>
<li><p>The other phasing of the SRL, which I vastly prefer, is: there is a vertex partition <span class="math-container">$\Pi$</span> into <span class="math-container">$\text{tower}(\varepsilon^{-C})$</span> parts (with no exceptional set) such that
<span class="math-container">$$\text{irreg}(\Pi) := \sum_{X, Y \in \Pi} \text{irreg}(X, Y) \le \varepsilon n^2,$$</span>
roughly meaning that the <em>average</em> pair of parts satisfies the irregularity bound from the first phrasing.</p>
</li>
</ul>
<p>You can see the intro of <a href="https://math.mit.edu/%7Efox/paper-regtight.pdf" rel="nofollow noreferrer">this paper</a> 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:</p>
<p><strong>Lemma:</strong> For any graph <span class="math-container">$G$</span>, if vertex partition <span class="math-container">$\Pi_1$</span> is a refinement of vertex partition <span class="math-container">$\Pi_2$</span>, then <span class="math-container">$\text{irreg}(\Pi_1) \le \text{irreg}(\Pi_2)$</span>.</p>
<p>That means you could take the following approach to your <span class="math-container">$m$</span>-colored SRL.  For each of the <span class="math-container">$m$</span> colors, consider the graph that has the edges of color <span class="math-container">$i$</span> and omits the edges of all other colors, and compute an SRL partition (under the second definition).  Let <span class="math-container">$\{\Pi_1, \dots, \Pi_m\}$</span> be your partitions.  Then take the common refinement <span class="math-container">$\Pi^*$</span> of all these partitions, and due to the above lemma, <span class="math-container">$\Pi^*$</span> will satisfy the (second-definition) SRL for all colors simultaneously.  The partition size would be about <span class="math-container">$\text{tower}(\varepsilon^{-C})^m$</span>.</p>
<p>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 <span class="math-container">$\varepsilon/m$</span> 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 <span class="math-container">$\text{tower}((\varepsilon/m)^{-C})$</span>.</p>

CC BY-SA 4.0
2022-08-08T17:09:25.083Z
2022-08-08T17:09:25.083Z
GMB
<p>Is there an analogous to <a href="https://en.wikipedia.org/wiki/Szemer%C3%A9di_regularity_lemma" rel="nofollow noreferrer">Szemerédi regularity lemma</a> in the setting, where I have multi relational graph i.e. I have <span class="math-container">$n$</span> nodes, but instead of having edges to be in <span class="math-container">$\{0,1\}$</span> i.e. there is an edge or not, I have the edges to be in <span class="math-container">$\{c_1,c_2,...,c_m\}$</span> i.e. I have <span class="math-container">$m$</span> colours (you may assume one of the colour to be no edge).</p>

CC BY-SA 4.0
2022-08-04T15:30:11.983Z
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?
GMB
CC BY-SA 4.0
2022-08-04T20:15:25.253Z
@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 :)
SagarM
CC BY-SA 4.0
2022-08-04T22:27:50.897Z
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.
GMB
<graph-theory><graph-algorithms><co.combinatorics><st.statistics><extremal-combinatorics>
Regularity Lemma for Multi-Relational Graphs?
SagarM
# Regularity Lemma for Multi-Relational Graphs?

(Asked by: username_0 on 2022-08-04)

Is there an analogous to [Szemerédi regularity lemma](https://en.wikipedia.org/wiki/Szemer%C3%A9di_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).

**Tags:** graph-theory, graph-algorithms, co.combinatorics, st.statistics, extremal-combinatorics

> **Comments:**
> **username_1**: 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?  
> **username_0**: @username_1 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 :)  
> **username_1**: 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.  

---

## 1 answers

### Answer by username_1 on 2022-08-08. Score: 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](https://math.mit.edu/%7Efox/paper-regtight.pdf) 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})$.


---

