Regularity Lemma for Multi-Relational Graphs?

Question

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

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