Digraphs with a fixed number of edges and vertices, having a maximal number of walks of length 2
| dc.creator | Snellman, Jan | |
| dc.date | 2008-04-29 | |
| dc.date | 2008-05-29 | |
| dc.date.accessioned | 2026-07-07T09:41:14Z | |
| dc.date.available | 2026-07-07T09:41:14Z | |
| dc.description | Inspired by the work of Backelin on non-commutative correspondences to Macaulay's theorem of the growth of the Hilbert series of affine algebras, we study embedding dimension dependant versions of his degree 2 to degree 3 result. In graph-theoretical terms, we study the following question: what is the maximal number of directed walks of length 2 in a digraph with (k) edges and (n) vertices? The problem can also be formulated as follows: maximize (< λ, λ^T >) when (λ) is a partition of (k), contained in an (n \times n) box. We show that for mild restrictions on (n), optimal digraphs are the ``stars of saturated stars''. | |
| dc.description | Manuscript withdrawn: the author discovered that "A problem in rearrangements of (0,1) matrics", Ron Aharoni, Disc. Math 30 pp 191-201 contains the main results of the manuscript | |
| dc.identifier | https://arxiv.org/abs/0804.4655 | |
| dc.identifier | http://arxiv.org/abs/0804.4655 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/161755 | |
| dc.subject | Combinatorics | |
| dc.subject | Rings and Algebras | |
| dc.title | Digraphs with a fixed number of edges and vertices, having a maximal number of walks of length 2 | |
| dc.type | text |