×

Boolean rank of upset tournament matrices. (English) Zbl 1241.05068

Summary: The Boolean rank of an \(m\times n(0,1)\)-matrix \(M\) is the minimum \(k\) for which matrices \(A\) and \(B\) exist with \(M=AB\), A is \(m\times k\), \(B\) is \(k\times n\), and Boolean arithmetic is used. The intersection number of a directed graph \(D\) is the minimum cardinality of a finite set \(S\) for which each vertex \(v\) of \(D\) can be represented by an ordered pair \((S_{v},T_{v})\) of subsets of \(S\) such that there is an arc from vertex \(u\) to vertex \(v\) in \(D\) if and only if \(S_{u}\cap T_{v}\neq \emptyset \). The intersection number of a digraph is equal to the Boolean rank of its adjacency matrix. Using this fact, we show that the intersection number of an upset tournament, equivalently, the Boolean rank of its adjacency matrix, is equal to the number of maximal subpaths of certain types in its upset path.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
15A18 Eigenvalues, singular values, and eigenvectors
15A23 Factorization of matrices
05C20 Directed graphs (digraphs), tournaments
05C62 Graph representations (geometric and intersection representations, etc.)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Beasley, L. B.; Guterman, A. E., Rank inequalities over semirings, J. Korean Math. Soc., 42, 223-241 (2005) · Zbl 1070.15014
[2] Beasley, L. B.; Kirkland, S. J.; Shader, B. L., Rank comparisons, Linear Algebra Appl., 221, 171-188 (1995) · Zbl 0823.15003
[3] Beasley, L. B.; Pullman, N. J., Semiring rank versus column rank, Linear Algebra Appl., 101, 33-48 (1988) · Zbl 0642.15002
[4] Brown, D. E.; Busch, A. H.; Lundgren, J. R., Interval tournaments, J. Graph Theory, 56, 72-81 (2007) · Zbl 1130.05028
[5] Brualdi, R.; Li, Q., Upsets in round robin tournaments, J. Comb. Theory B, 35, 62-77 (1983) · Zbl 0519.05033
[6] de Caen, D., The ranks of tournament matrices, Am. Math. Mon., 98, 62-77 (1991)
[7] D. de Caen, D. Gregory, N. Pullman, The Boolean rank of zero one matrices, in: Proceedings of the Third Caribbean Conference on Combinatorics and Computing, Barbados, 1981, pp. 169-173.; D. de Caen, D. Gregory, N. Pullman, The Boolean rank of zero one matrices, in: Proceedings of the Third Caribbean Conference on Combinatorics and Computing, Barbados, 1981, pp. 169-173. · Zbl 0496.20052
[8] D. de Caen, D. Gregory, N. Pullman, The Boolean rank of zero one matrices, II, in: Proceedings of the Fifth Caribbean Conference on Combinatorics and Computing, Barbados, 1988, pp. 120-126.; D. de Caen, D. Gregory, N. Pullman, The Boolean rank of zero one matrices, II, in: Proceedings of the Fifth Caribbean Conference on Combinatorics and Computing, Barbados, 1988, pp. 120-126. · Zbl 0496.20052
[9] Erdös, P.; Goodman, A. W.; Pósa, L., The representation of a graph by set intersection, Can. J. Math., 18, 106-112 (1966) · Zbl 0137.43202
[10] Factor, K. A.S.; Kohler, R. M.; Darby, J. M., Local out-tournaments with upset tournament strong components: I. Full and equal \(\{0, 1 \}\)-matrix ranks, Ars Combinatoria, 95, 3-17 (2010) · Zbl 1249.05164
[11] Gregory, D. A.; Pullman, N. J., Semiring rank: Boolean rank and nonnegative rank factorizations, J. Comb. Inf. Syst. Sci., 8, 223-233 (1983) · Zbl 0622.15007
[12] Gregory, D. J.; Jones, K. F.; Lundgren, J. R.; Pullman, N. J., Biclique coverings of regular bigraphs and minimum semiring ranks of regular matrices, J. Comb. Theory B, 51, 73-89 (1991) · Zbl 0733.05064
[13] Hefner, K. A.S.; Lundgren, J. R., Minimum matrix ranks of \(k\)-regular \((0, 1)\)-matrices, Linear Algebra Appl., 133, 43-52 (1990) · Zbl 0701.15009
[14] Maybee, J. S.; Pullman, N. J., Tournament matrices and their generalizations, Linear Multilinear Algebra, 28, 58-70 (1990) · Zbl 0714.05041
[15] Müller, H., Recognizing interval digraphs and interval bigraphs in polynomial time, Discrete Appl. Math., 78, 189-205 (1997) · Zbl 0890.68103
[16] Poet, J. L.; Shader, B. L., Score certificate numbers for upset tournaments, Discrete Appl. Math., 103, 177-189 (2000) · Zbl 0961.05029
[17] Sanyal, B. K.; Sen, M. K., Indifference digraphs: a generalization of indifference graphs and semiorders, SIAM J. Discrete Math., 7, 157-165 (1994) · Zbl 0798.05025
[18] Sen, M.; Das, S.; Roy, A. B.; West, D. B., Interval digraphs: an analogue of interval graphs, J. Graph Theory, 13, 189-202 (1989) · Zbl 0671.05039
[19] B.L. Shader, Biclique Partitions and Tournament Matrices, Ph.D. Thesis, University of Wisconsin-Madison, 1990.; B.L. Shader, Biclique Partitions and Tournament Matrices, Ph.D. Thesis, University of Wisconsin-Madison, 1990.
[20] Watts, V. L., Boolean rank of Kronecker products, Linear Algebra Appl., 336, 261-264 (2001) · Zbl 0993.15002
[21] West, D. B., Short proofs for interval digraphs, Discrete Math., 178, 287-292 (1998) · Zbl 0884.05044
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.