login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A300795 Number of vertices of the master corner polyhedron on the cyclic group of order n + 1. 0
1, 2, 3, 5, 7, 10, 16, 19, 31, 32, 55, 53, 89, 89, 147, 128, 232, 191, 356, 301, 491 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

The master corner polyhedron P(G_{n+1},n) on the additive cyclic group G_{n+1} of order n+1 (with addition modulo n+1) is the convex hull of solutions t=(t_1,t_2,..,t_n) in R^n, t_i integer, t_i >= 0, to the equation t_1 + 2*t_2 + ... + n*t_n == n (mod (n+1)).

The master corner polyhedron P(G,g_0) was defined by R. E. Gomory for an arbitrary finite Abelian group G and arbitrary group element g_0. It is of great importance for integer linear programming.

R. E. Gomory computed vertices of P(G,g_0) for all groups G of the order up to 11 and all g_0 in G.

The point t=(0,0,0,0,1,0,0,0,3,0) was erroneously indicated to be a vertex of P(G_11,10).

a(11)-a(21) were computed with the use of the Parma Polyhedra Library [(PPL)]. - Dominic Yang, Oct 04 2018

LINKS

Table of n, a(n) for n=1..21.

R. E. Gomory, source links to R. E. Gomory's papers.

R. E. Gomory, Some polyhedra related to combinatorial problems, Journal of Linear Algebra and Its Applications, 1969. Vol. 2, No. 4, 451-558.

V. A. Shlyk, Master corner polyhedron: vertices, European Journal of Operational Research, 2013. Vol. 226, No. 2, 203-210.

Vladimir A. Shlyk, Number of Vertices of the Polytope of Integer Partitions and Factorization of the Partitioned Number, arXiv:1805.07989 [math.CO], 2018.

EXAMPLE

The 6 integer points in the convex hull of the vertices of P(G_5,4) are (4,0,0,0), (2,1,0,0), (1,0,1,0), (0,2,0,0), (0,0,3,0), (0,0,0,1) but a(4) = 5 since (2,1,0,0) = (1/2)(4,0,0,0) + (1/2)(0,2,0,0).

CROSSREFS

Similar to A203898.

Sequence in context: A116975 A286227 A134792 * A033068 A234368 A052011

Adjacent sequences:  A300792 A300793 A300794 * A300796 A300797 A300798

KEYWORD

nonn,more

AUTHOR

Vladimir A. Shlyk, Mar 13 2018

EXTENSIONS

a(11)-a(21) from Dominic Yang, Oct 04 2018

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 24 01:07 EDT 2021. Contains 345404 sequences. (Running on oeis4.)