Czy ten polytop „podgrupy” jest integralny?

Niech będzie skończoną grupą abelową, i niech będzie polytopem w zdefiniowanym jako punkty spełniające następujące nierówności:P R Γ$\Gamma$$P$$\mathbb{R}^\Gamma$$x$

gdzie oznacza, że jest podgrupą . Czy integralny? Jeśli tak, to czy możemy scharakteryzować jego wierzchołki?G Γ $G \le \Gamma$$G$$\Gamma$$P$

Moje pytanie pierwotnie powstało z , gdzie niektóre małe przykłady ( ) sugerują, że odpowiedź brzmi „tak” i „może, ale to nie jest proste”. Próbowałem także grupy cyklicznej na elementach 9 i 10, a także , gdzie znowu polytop jest integralny. Polytop nie jest integralny, gdy jest jednym z , i , więc abelianizm jest najwyraźniej niezbędny. n = 2 , 3 F 2 $\Gamma = \mathbb{F}_2^n$$n = 2,3$$\mathbb{F}_3^2$S 3 D 4 D $\Gamma$$S_3$$D_4$$D_5$

Powinienem wspomnieć, że jeśli napiszesz pierwszy zestaw równań jako , to niekoniecznie jest całkowicie niemodularne (co sugerowałoby, że polytop jest integralny). Kiedy , możesz wybrać trzy liniowo niezależne wziąć trzy rozłożone na każdą parę wybranych elementów . Wynikowa submatrix to aż do permutacji, a więc ma wyznacznik .A Γ = F 3 2 g G g [ 0 1 1 1 0 1 1 1 0 ] ± $Ax \ge b$$A$$\Gamma = \mathbb{F}_2^3$$g$$G$$g$

Charakteryzowanie wierzchołków dla grup rzędu pierwszego i obserwowanie, że są integralne, jest łatwe (choć żmudne). Jestem prawie pewien, że można to rozszerzyć na grupy cykliczne z zamówieniem mocy pierwotnej. Nie jestem pewien, co się dzieje podczas przyjmowania produktów.

Ten system bardzo przypomina te, które definiują polimatroidy , ale ograniczenia niż podmodularna funkcja zestawu, ograniczenia są „funkcją podgrupy”, która, jak podejrzewam, jest „podmodularna”, jeśli zostanie to zdefiniowane we właściwy sposób. Mimo to techniki pokazujące, że niektóre polimatroidy są integralne, również tutaj mogą działać, ale nie rozumiem, jak to zrobić.

Również analiza Fouriera może być istotna: gdy , wydaje się, że wierzchołki maksymalizujące są dokładnie punktem z dla wszystkich , a także z gdzie jest -tym znakiem Fouriera (zgodnie ze standardową notacją z analizy funkcji boolowskich), a jest niepusty. (Gdy jest pusty, odpowiadającym mu punktem jest , co również jest wierzchołkiem.) ∑ g x g x g = 1 g x g = 1 - χ S ( g ) χ S S S S x g = $\Gamma = \mathbb{F}_2^n$$\sum_g x_g$$x_g = 1$$g$$x_g = 1 - \chi_S(g)$$\chi_S$$S$$S$$S$$x_g = 0$

Andrew (pytający) i ja rozmawialiśmy o tym przez e-mail, a my wykazaliśmy, że przypuszczenie jest fałszywe. Polytop nie jest integralny dla grup abelowych, nawet dla grup cyklicznych.

Z dobrej strony.

Twierdzenie : Dla grup cyklicznych o rzędzie , gdzie i są liczbami pierwszymi, a , matryca występowania elementów i podgrup jest całkowicie niemodularna.p q k ∈ $p^kq$$p$$q$$k\in \mathbb{N}$

Wynika to z faktu, że rodzina podgrup stanowi połączenie dwóch rodzin laminarnych.

To pokazuje, że najmniejszy kontrprzykład dla grup cyklicznych musi mieć kolejność co najmniej . To właściwie wyjaśnia, dlaczego nie znaleziono żadnego małego kontrprzykładu.$2\times 3\times 5 =30$

Andrew wykonał kilka obliczeń i znalazł kontrprzykład dla cyklicznej grupy rzędu .$30$

Przykład kontrprzykładowy : , , , , a wszędzie indziej. Nie jest trudno sprawdzić, czy punkt jest wykonalny. Przeformułowuję tutaj dowód Andrzeja, że ​​to właściwie wierzchołek. Istnieje ścisłych ograniczeń. Ograniczenie całej grupy, trzy podgrupy wygenerowane odpowiednio przez i oraz ograniczenia nieujemności. Ponieważ mamy zmiennych, jest wierzchołkiem.x 2 = $x_0=1/2$x3=$x_2=\frac{30}{2}-\frac{1}{2}=29/2$x5=$x_3=\frac{30}{3}-\frac{1}{2}=19/2$0 30 2 , 3 5 30 $x_5=\frac{30}{5}-\frac{1}{2}=11/2$$0$$30$$2,3$$5$$30$$x$

Można się zastanawiać, czy polytope dla jest integralne dla wszystkich . Niestety Andrew znalazł również niecałkowitą polytopa dla . n F 4 $\mathbb{F}_2^n$$n$$\mathbb{F}_2^4$