Upper bounds on the size of transitive subtournaments in digraphs. (English) Zbl 1367.05090
Summary: In this paper, we consider upper bounds on the size of transitive subtournaments in a digraph. In particular, we give an upper bound based on linear algebraic techniques similarly to Hoffman’s bound for the size of cocliques in a regular graph. Furthermore, we partially improve the bound for doubly regular tournaments by using the technique of G. Greaves and L. H. Soicher [“On the clique number of a strongly regular graph”, Preprint, arXiv:1604.08299] for strongly regular graphs, which gives a new application of block intersection polynomials.
MSC:
| 05C20 | Directed graphs (digraphs), tournaments |
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 05C31 | Graph polynomials |
Keywords:
transitive subtournament; regular digraph; doubly regular tournament; Paley tournament; Hoffman’s bound; block intersection polynomialReferences:
| [1] | Bachoc, C.; Matolcsi, M.; Ruzsa, I. Z., Squares and difference sets in finite fields, Integers, 13, Article A77 pp. (2013), 5 pp · Zbl 1284.11030 |
| [2] | Cameron, P.; Soicher, L. H., Block intersection polynomials, Bull. Lond. Math. Soc., 39, 559-564 (2007) · Zbl 1131.05014 |
| [3] | Erdős, P.; Moser, L., On the representation of directed graphs as unions of orderings, Magrar Tud. Akad. Mat. Kutató Int. Közl., 9, 125-132 (1964) · Zbl 0136.44901 |
| [4] | Greaves, G.; Soicher, L. H., On the clique number of a strongly regular graph, preprint · Zbl 1398.05150 |
| [5] | Haemers, W. H., Eigenvalue Techniques in Design and Graph Theory, Math. Centre Tract, vol. 121 (1980), Mathematical Centre: Mathematical Centre Amsterdam, Thesis, Technical University Eindhoven, 1979 · Zbl 0429.05013 |
| [6] | Haemers, W. H., Matrix techniques for strongly regular graphs and related geometries, (Lecture Note at the Intensive Course on Finite Geometry and Applications (2000), University of Ghent) |
| [7] | Hoffman, A. J., On eigenvalues and colorings of graphs, (Graph Theory and Its Applications (1970), Acd. Press: Acd. Press New York), 79-91 · Zbl 0227.05105 |
| [8] | Horn, R. A.; Johnson, C. R., Matrix Analysis (2013), Cambridge University Press: Cambridge University Press Cambridge, xviii+643 pp · Zbl 1267.15001 |
| [9] | McKay, B., Combinatorial Data |
| [10] | Moon, J. W., On maximal transitive subtournaments, Proc. Edinb. Math. Soc., 17, 345-349 (1970/1971) · Zbl 0234.05108 |
| [11] | Nozaki, H.; Suda, S., A characterization of skew Hadamard matrices and doubly regular tournaments, Linear Algebra Appl., 437, 1050-1056 (2012) · Zbl 1251.15033 |
| [12] | Reid, K. B.; Parker, E. T., Disproof of a conjecture of Erdős and Moser, J. Combin. Theory, 9, 225-238 (1970) · Zbl 0204.24605 |
| [13] | Sanchez-Flores, A., On tournaments free of large transitive subtournaments, Graphs Combin., 14, 181-200 (1998) · Zbl 0918.05058 |
| [14] | Sanchez-Flores, A., On tournaments and their largest transitive subtournaments, Graphs Combin., 10, 367-376 (1994) · Zbl 0811.05029 |
| [15] | Soicher, L. H., More on block intersection polynomials and new applications to graphs and block designs, J. Combin. Theory Ser. A, 117, 799-809 (2010) · Zbl 1228.05080 |
| [16] | Soicher, L. H., On cliques in edge-regular graphs, J. Algebra, 421, 260-267 (2015) · Zbl 1302.05082 |
| [17] | Tabib, C., About the inequalities of Erdős and Moser on the largest transitive subtournaments of a tournament, (Combinatoire énumérative. Combinatoire énumérative, Lecture Notes in Math., vol. 1234 (1986), Springer: Springer Berlin), 308-320 · Zbl 0609.05042 |
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.
