A269799 Number of vertices of the fractional perfect matching polytope for the complete graph on n vertices.

0, 1, 1, 3, 22, 25, 717, 1057, 39196, 98829

Offset: 1

Author

Pontus von Brömssen, Mar 05 2016

Keywords

• nonn
• more

Comments

The fractional perfect matching polytope of a graph is the set of nonnegative edge weights such that the sum of the weights of the edges incident with any given vertex equals 1.

Sequence up to n=10 computed with PORTA (see links) by Pontus von Brömssen in December 2010.

a(n) equals the number of facets of the polytope P_n defined in Eickmeyer and Yoshida (2008), at least up to n=10.

Examples

			For n=4 the fractional perfect matching polytope is the convex hull of the 3 perfect matchings of K_4, so a(4)=3. For n=6, in addition to the 15 perfect matchings of K_6, the 10 pairs of disjoint triangles with edge weights 1/2 are vertices of the polytope, so a(6)=25.
		

Links

• Roger E. Behrend, Fractional perfect b-matching polytopes I: General theory, Linear Algebra and its Applications 439 (2013), 3822-3858.
• Thomas Christof, Sebastian Schenker, PORTA, Ruprecht-Karls-Universität Heidelberg.
• K. Eickmeyer and R. Yoshida, The Geometry of the Neighbor-Joining Algorithm for Small Trees, in: Proc. 3rd Int. Conference on Algebraic Biology, 2008, Castle of Hagenberg, Austria, Springer LNCS5147, arXiv:0908.0098 [math.CO], 2009.

Crossrefs

Cf. A123023.