The triangle-star transformation, intercalate matrices and applications (Q2702041)

This survey work shows the interaction between different parts of mathematics and between mathematics and applications by taking as an example the \(\Delta-Y\) transformations and intercalate matrices. The first part is devoted to the \(\Delta-Y\) transformations in graphs. Besides Truemper's proof of the \(\Delta-Y\) reducibility of planar graphs [J. Graph Theory 13, No. 2, 141-147 (1989; Zbl 0677.05020)] a long list of applications is discussed: shortest paths, maximum flows, electric circuits, etc. In particular, the Ising model, and its generalization to spin models in the context of knot theory is considered. The second part is devoted to intercalate matrices. An \((r,s,n)\)-intercalate matrix is an \(r\times s\) matrix with entries in a set of cardinality \(n\) such that (i) each row and each column has no repeated entries, and (ii) each \(2\times 2\) submatrix has either two or four different entries. It is shown, for instance, how, given \(r\) and \(s\), the problem of finding the minimum \(n\) such that there exists an \((r,s,n)\)-intercalate matrix is related to the combinatorial Nullstellensatz of \textit{N. Alon} [Comb. Probab. Comput. 8, No. 1-2, 7-29 (1999; Zbl 0920.05026)]. Applications such as broadcasting and experimental designs are also linked to intercalate matrices. Nevertheless, the most interesting related question is the sum of squares problem, which is the topic of the last part. An \((r,s,n)\)-formula is an equality \((x_1^2+\cdots+x_r^2)(y_1^2+\cdots+y_s^2)=(z_1^2+\cdots+z_n^2)\) where \(x_i\), \(y_j\) are indeterminates and \(z_k=\sum_{i,j}a_{i,j}^kx_iy_j\) with \(a_{i,j}^k\) integers. The problems considered are: (1) to find the minimum \(n\) such that, given \(r\) and \(s\), an \((r,s,n)\)-formula exists, and (2) to find the maximum \(r\) such that, given \(n\), an \((r,n,n)\)-formula exists. The approach consists in using a correspondence between \((r,s,n)\)-formulae and a class of \((r,s,n)\)-intercalate matrices. The \(\Delta-Y\) transformation appears as an important tool in the discussion.NEWLINENEWLINEFor the entire collection see [Zbl 0948.00009].