Digraphs with a fixed number of edges and vertices, having a maximal number of walks of length 2

Details Digraphs with a fixed number of edges and vertices, having a maximal number of walks of length 2 Digraphs with a fixed number of edges and vertices, having a maximal number of walks of length 2

2008-04-29

arxiv.org/abs/0804.4655v2

Mathematics

Combinatorics

Manuscript withdrawn: the author discovered that "A problem in rearrangements of (0,1) matrics", Ron Aharoni, Disc. Math 30 pp

Scientific paper

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 (< \lambda, \lambda^T >) when (\lambda) 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''.

Affiliated with

Also associated with

No associations

Rating

Digraphs with a fixed number of edges and vertices, having a maximal number of walks of length 2 does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Digraphs with a fixed number of edges and vertices, having a maximal number of walks of length 2, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Digraphs with a fixed number of edges and vertices, having a maximal number of walks of length 2 will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-210214