The dimension of sums of graphs (Q6343705)

The dimension of a graph G (dim G) is the least natural number n such that G is an induced subgraph of a direct product of n graphs. The author obtains an improvement on the upper bound obtained by \textit{S. Poljak} and \textit{V. Rödl} [Czechosl. Math. J. 30, 475-485 (1980; Zbl 0456.05051)] on the dimension of sums of graphs. The following are the main results: (1) If n is a power of a prime, then, for m,\(\ell \in N\), \(\dim n^{\ell}K_ n\leq 1+\ell (n-1)\) and \(\dim m K_ n\leq 1+(n-1)\lceil \log^ m_ n\rceil\). (2) Let \(G_ 1,G_ 2,...,G_ m\) be arbitrary graphs, and \(d=\max \{\dim G_ i| \quad 1\leq i\leq m\}\) and \(n=\max \{\chi (G_ i)| \quad 1\leq i\leq m\},\) where \(\chi\) is the chromatic number. Then \(\dim \sum^{m}_{i=1}G_ i\leq d+1+(n-1)\lceil \log^ m_{\underline n}\rceil,\) where ṉ is the least (or any) prime power greater than or equal to n. The proof technique employed is a new concept of matrices with covering property which is a sort of generalization of orthogonal Latin squares.