login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A269799 Number of vertices of the fractional perfect matching polytope for the complete graph on n vertices. 0

%I #21 Apr 01 2021 09:41:51

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

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

%C 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.

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

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

%H Roger E. Behrend, <a href="https://doi.org/10.1016/j.laa.2013.10.001">Fractional perfect b-matching polytopes I: General theory</a>, Linear Algebra and its Applications 439 (2013), 3822-3858.

%H Thomas Christof, Sebastian Schenker, <a href="http://comopt.ifi.uni-heidelberg.de/software/PORTA/">PORTA</a>, Ruprecht-Karls-Universität Heidelberg.

%H K. Eickmeyer and R. Yoshida, <a href="http://arxiv.org/abs/0908.0098">The Geometry of the Neighbor-Joining Algorithm for Small Trees</a>, in: Proc. 3rd Int. Conference on Algebraic Biology, 2008, Castle of Hagenberg, Austria, Springer LNCS5147, arXiv:0908.0098 [math.CO], 2009.

%e 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.

%Y Cf. A123023.

%K nonn,more

%O 1,4

%A _Pontus von Brömssen_, Mar 05 2016

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 05:48 EDT 2024. Contains 371265 sequences. (Running on oeis4.)