TY - JOUR

T1 - On the product dimension of clique factors

AU - Alon, Noga

AU - Alweiss, Ryan

N1 - Publisher Copyright:
© 2020

PY - 2020/5

Y1 - 2020/5

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

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

UR - http://www.scopus.com/inward/record.url?scp=85081673423&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85081673423&partnerID=8YFLogxK

U2 - 10.1016/j.ejc.2020.103097

DO - 10.1016/j.ejc.2020.103097

M3 - Article

AN - SCOPUS:85081673423

SN - 0195-6698

VL - 86

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

M1 - 103097

ER -