Sperner capacity of small digraphs (Q2268245)

The authors consider the problem of quantifying the Sperner capacity for digraphs. For small graphs the capacity can be computed by brute force, but estimates are already needed for graphs having on the order of 7 nodes. The co-normal product of two directed graphs \(\vec{G}\) and \(\vec{H}\) is the graph whose vertex set consists of all ordered pairs of vertices of \(\vec{G}\) and \(\vec{H}\) and edges \(\{(x_1,y_2),(x_2,y_2)\}\) where \((x_1,x_2)\) is a directed edge of \(\vec{G}\) or \((y_1,y_2)\) is a directed edge of \(H\). A clique is a set of mutually adjacent vertices. If \(\vec{G}^n\) denotes the \(n\)-th co-normal power of the digraph \(\vec{G}\) and \(\omega(\vec{G})\) denotes the maximal size of any clique in \(G\) then, analogously to the case of an undirected graph, the Sperner capacity of \(\vec{G}\) is \(\sup_{n\geq 1} (\omega(\vec{G}^n)^{1/n}\). The authors review several known bounds for the Sperner capacity expressed in terms of local chromatic numbers, fractional local chromatic numbers, and local fractional covers. For example, the local chromatic number is \[ \psi_d(\vec{G})=\min_{c:V(\vec{G})\to\mathbb{N}} \max_{v\in V(G)} |\{c(w):w\in N_G^{+}(v)\}| \] where \(V(\vec{G})\) denotes the vertex set and \(N_G^{+}(v)\) denotes the terminal vertices of edges emanating from \(v\), along with \(v\) itself. The Sperner capacity of \(\vec{G}\) is bounded by \(\psi_d(\vec{G})\). Other related bounds for the Sperner capacity are reviewed. A different type of bound is reviewed in terms of matrices \(M\) having ones along the diagonal and satisfying \(m_{ij}=0\) if \((i,j)\) is an edge of \(\vec{G}\) and otherwise, \(m_{ij}\) is any real number. The Sperner capacity of a digraph is bounded by \(\min_{M}\, \text{rank}(M)\) where the minimum is taken over all \(M\) having the given structure. The remainder of the paper provides a case analysis in which the various theorems reviewed are used to provide effective bounds on most cases of digraphs with a small number of vertices (fewer than 7). For example, in the case of 5 vertex digraphs there are only 8 inequivalent cases for which the Sperner capacity is not identified exactly here, and in these cases the capacity is at least \(\sqrt{5}\) and at most \(5/2\).