×

0-1 matrices whose \(k\)-th powers have bounded entries. (English) Zbl 1455.15008

The authors try to crack the following problem: given positive integers \(n\) and \(k\), denote by \(M_n\{0, 1\}\) the set of 0-1 matrices of order \(n\) and by \(f(A)\) the number of nonzero entries in a 0-1 matrix \(A\). Let \(\Gamma(n, k, t) = \{A\in M_n\{0, 1\}\mid (A^k )_{ij}\leq t\text{ for }1\leq i, j\leq n\}\) and \(\gamma(n, k, t) = \max\{f(A)\mid A\in (n, k, t)\}\), where \((A^k)_{ij}\) is the \((i, j)\)-entry of \(A^k\). Given positive integers \(n\), \(k\), \(t\), determine \(\gamma(n, k, t)\) and the extremal matrices in \((n, k, t)\) that attain \(\gamma (n, k, t)\).
The solution to this problem is the main result of this paper. Let \(t\) be a positive integer. Then for any sufficiently large integers \(n\) and \(k\) such that \(k \geq n-1\), we have \(\gamma(n, k, t) = n(n-1)/2\). Moreover, a matrix \(A\in (n, k, t)\) satisfies \(f(A) = \gamma(n, k, t)\) if and only if \(A\) is a permutation similar to \(T_n\) an upper triangular tournament matrix of order \(n\). The strategy they adopt is to transfer the above problem to an equivalent problem on digraphs and to provide a detailed analysis on the structures of certain digraphs. Given positive integers \(n\), \(k\), \(t\), denote by \(\theta(n, k, t)\) the set of the digraphs of order \(n\) avoiding \(t+1\) walks of length \(k\) with the same initial vertex and terminal vertex. Denote by \(\theta_1(n, k, t)\) the maximum size of digraphs in \(\theta(n, k, t)\).
Then the above mentioned problem is equivalent to the following problem: given positive integers \(n, k, t\), determine \(\theta(n, k, t)\) and characterize the digraphs in \(\theta(n, k, t)\) attaining the size \(\theta_1(n, k, t)\). They solve this equivalent problem and determine \(\theta(n, k, t)\) for \(k\in \{n-2, n-3, n-4\}\) when \(n\) is sufficiently large.
It is a very interesting work as it provides a novel way of cracking a problem in matrix theory by conceiving it as a problem in graph theory.

MSC:

15B34 Boolean and Hadamard matrices
15B36 Matrices of integers
05C35 Extremal problems in graph theory
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C20 Directed graphs (digraphs), tournaments
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Zhan, X.Matrix theory. Providence, RI: American Mathematical Society; 2013 (Graduate studies in mathematics; vol. 147). · Zbl 1275.15001
[2] Wu, H., On the 0-1 matrices whose squares are 0-1 matrices, Linear Algebra Appl, 432, 2909-2924 (2010) · Zbl 1195.05016
[3] Huang, Z.; Zhan, X., Digraphs that have at most one walk of a given length with the same endpoints, Discrete Math, 311, 70-79 (2011) · Zbl 1225.05115
[4] Huang, Z, Lyu, Z, Qiao, P.Turán problems for digraphs avoiding different walks of a given length with the same endpoints, arXiv:1608.06170. · Zbl 1414.05133
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.