The Simple Chromatic Number of $(m, n)$-Mixed Graphs

NEW

Problem: For fixed nonnegative integers $m,n$ with $2m+n\ge 2$, let $G_N$ be the uniformly random labelled $(m,n)$-mixed graph on $N$ vertices: each unordered pair independently receives either no adjacency, one of $n$ undirected edge colours, or one of $2m$ directed arc-colour/orientation types. Prove that

$$\Pr(G_N\text{ is a simple }(m,n)\text{-mixed clique})\to 1 .$$

This is the natural formalization of Conjecture 1.23. If $(0,0)$ were allowed literally, the statement would be false, since all graphs are empty; the standard nontrivial convention is $2m+n\ge1$, and excluding $(0,1)$ gives $2m+n\ge2$.

Result: Let $q=2m+n\ge2$. For vertices $x,y,z$, say $z$ is between $x,y$ when $z$ is adjacent to both $x,y$ and the two adjacency types seen from $z$ are distinct. Then

$$p:=\Pr(z\text{ is between }x,y)=\frac{q(q-1)}{(q+1)^2}>0.$$

Fix a pair $x,y$. Let

$$S_{xy}=\{z\ne x,y: z\text{ is between }x,y\}.$$

Then $|S_{xy}|\sim \mathrm{Bin}(N-2,p)$, so by Chernoff,

$$\Pr(|S_{xy}|<p(N-2)/2)\le e^{-cN}$$

for some $c=c(m,n)>0$. A union bound over $\binom N2$ pairs gives, with high probability, every $S_{xy}$ has size at least $\alpha N$, where $\alpha=p/3>0$.

Now condition on such a large set $S=S_{xy}$. For a vertex $v\notin S\cup\{x,y\}$, $v$ fails to be between every pair of vertices of $S$ only if all nonzero adjacency types from $v$ to $S$ are the same. Hence

$$\Pr(v\text{ is between no pair in }S) \le q\left(\frac{2}{q+1}\right)^{|S|} \le q\left(\frac{2}{q+1}\right)^{\alpha N},$$

which is exponentially small since $q\ge2$. A union bound over all triples $(x,y,v)$ shows that, with high probability, for every pair $x,y$, every remaining vertex $v$ is between two vertices of $S_{xy}$.

Thus, with high probability, the convex hull of every pair $x,y$ is all of $V(G_N)$: first it contains $S_{xy}$, then every other vertex is forced in by being between two vertices already in the hull.

Finally, in any simple colouring, if two vertices receive the same colour, then every vertex in their convex hull must receive that same colour. Since every pair has full convex hull, no two distinct vertices can share a colour in a nontrivial simple colouring. Therefore every simple colouring uses $N$ colours, so

$$\chi_s(G_N)=N,$$

i.e. $G_N$ is a simple $(m,n)$-mixed clique. Hence the conjecture is true under the standard nontrivial convention $2m+n\ge2$.

Citation: The definitions and convex-hull criterion are from Duffy and Pas, “The Simple Chromatic Number of $(m,n)$-Mixed Graphs,” arXiv:1809.04675. The probabilistic proof above is supplied here.