On the product dimension of clique factors

Noga Alon, Ryan Alweiss

Research output: Contribution to journalArticlepeer-review

Abstract

The product dimension of a graph G is the minimum possible number of proper vertex colorings of G so that for every pair u,v of non-adjacent vertices there is at least one coloring in which u and v have the same color. What is the product dimension Q(s,r) of the vertex disjoint union of r cliques, each of size s? Lovász, Nešetřil and Pultr proved in 1980 that for s=2 it is (1+o(1))log2r and raised the problem of estimating this function for larger values of s. We show that for every fixed s, the answer is still (1+o(1))log2r where the o(1) term tends to 0 as r tends to infinity, but the problem of determining the asymptotic behavior of Q(s,r) when s and r grow together remains open. The proof combines linear algebraic tools with the method of Gargano, Körner, and Vaccaro on Sperner capacities of directed graphs.

Original languageEnglish (US)
Article number103097
JournalEuropean Journal of Combinatorics
Volume86
DOIs
StatePublished - May 2020

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'On the product dimension of clique factors'. Together they form a unique fingerprint.

Cite this