Counting vertices and cubes in median graphs of circular split systems (Q2472839): Difference between revisions

For a given set \(\mathcal S\) (a ``split system'') of bipartitions \(S=\{A,B\}\) (called splits) of \([n]=\{1,2,\dots,n\}\) (where \(A,B\) are non-empty), the associated median graph or Buneman graph [cf. \textit{S. Klavžar, H. M. Mulder} and \textit{R. Škrekovski}, Discrete Math. 187, No. 1--3, 255--258 (1998; Zbl 0957.05031); \textit{A. Dress, M. Hendy, K. Huber} and \textit{V. Moulton}, Ann. Comb. 1, No. 4, 329--337 (1997; Zbl 0927.05077)]) is the subgraph of the \(| {\mathcal S}| \)-dimensional hypergraph with vertex-set consisting of those maps \(\varphi:{\mathcal S}\to2^{[n]}\) which, for all \(S,S^\prime\in{\mathcal S}\), satisfy \(\varphi(S)\in S\), \(\varphi(S)\cap\varphi(S^\prime)\neq\emptyset\); and edge-set consisting of those pairs of vertices \(\{\varphi,\varphi^\prime\}\) with \(| \{S\in{\mathcal S}:\varphi(S)\neq\varphi^\prime(S)\}| =1\). For \(i,j\in[n]\), the metric \(d_{\mathcal S}:[n]\times[n]\to{\mathbb R}_{\geq0}\) is given by \(d_{\mathcal S}(i,j)=| \{S\in{\mathcal S}:i,j\) are in different parts of \(S\}| \); the tight-span associated with \(\mathcal S\) is ``the polytopal complex that is given by the union of the bounded faces of the polytope in \({\mathbb R}^{[n]}\) given by \(P(d_{\mathcal S})=\{f:[n]\to{\mathbb R}| f(i)+f(j)\geq d_{\mathcal S}(i,j)\), for all \(i,j,\in[n]\}\)''. For \(n>2\), the \textit{full circular split system} \({\mathcal S}(n)\) consists of all splits of \([n]\) induced by removing 2 edges from \(C_n\) and taking the split of \([n]\) corresponding to the two connected components; \({\mathcal S}(2)\) consists of the split \(\{\{1\},\{2\}\}\); for \(1\leq m\leq\lfloor\frac n2\rfloor\), \({\mathcal S}(n,m)\) consists of the splits \(S=\{A,B\}\) in \({\mathcal S}(n)\) with \(\min\{| A| ,| B| \}=m\). The authors present formulæ and recursions for the numbers of vertices and the numbers of maximal induced subcubes in the median graphs associated with the circular split systems \({\mathcal S}(n)\) and \({\mathcal S}(n,m)\) [cf. \textit{H.-J. Bandelt} and \textit{A. W. M. Dress}, Adv. Math. 92, No. 1, 47--105 (1992; Zbl 0789.54036)]. They provide an affirmative answer to a question posed by B. Sturmfels concerning tight-spans.