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: $\Gamma$ $P$ $\mathbb{R}^\Gamma$ $x$

\begin{array}{cl} \sum_{g \in G} x_{g} \leq | G | & \forall G \leq Γ \\ x_{g} \geq 0 & \forall g \in Γ \end{array}

$\begin{array}{cl} \sum_{g\in G} x_g \le |G| & \forall G \le \Gamma \\ x_g \ge 0 & \forall g \in \Gamma \end{array}$

gdzie oznacza, że jest podgrupą . Czy integralny? Jeśli tak, to czy możemy scharakteryzować jego wierzchołki? $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. $\Gamma = \mathbb{F}_2^n$ $n = 2,3$ $\mathbb{F}_3^2$ $\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 . $Ax \ge b$ $A$ $\Gamma = \mathbb{F}_2^3$ $g$ $G$ $g$

[\begin{matrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{matrix}]

$\begin{bmatrix}0&1&1\\1&0&1\\1&1&0\end{bmatrix}$

\pm 2

$\pm 2$

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.) $\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$

gr.group-theory fourier-analysis convex-geometry

— Andrew Morgan
źródło

Naprawdę ciekawe pytanie! W przypadku możesz być w stanie uzyskać przebieg z analizy, zauważając, że grupa automorfizmów działa tranzytowo na elementy nieidentyfikacyjne (w sensie „n-przejściowo ", w tym sensie, że wysyła dowolny n-krotność liniowo niezależnych elementów grupy do dowolnego innego takiego n-krotka). Na początek możesz założyć WLOG, że jest największym spośród elementów nieidentyfikujących, a jest drugim co do wielkości ...

F_{2}^{n}

$\mathbb{F}_2^n$

x_{1000 \dots 0}

$x_{1000\dotsc 0}$

x_{e_{2}}

$x_{e_2}$

— Joshua Grochow

@JoshuaGrochow Thanks! Nie jestem pewien, czy posortowanie współrzędnych jest właściwym rozwiązaniem, ale symetrie są prawie zawsze przydatne. Innym miejscem do ich wykorzystania są ograniczenia - w końcu automorfizmy wysyłają podgrupy do podgrup. Coś, co wydaje się przydatne, jest, dla dowolnego punktu , uśrednianie go dla wszystkich automorfizmów, które naprawiają zestaw ograniczeń ściśle na . Nie wiem jednak, jak sprawić, by ta ilość była możliwa do zarządzania.

x

$x$

x

$x$

— Andrew Morgan,

Tak, to bardzo interesujące i ciekawe pytanie. (Jeśli nie masz nic przeciwko dzieleniu się) Czy była motywacja, aby spojrzeć na te konkretne polytopy? A może coś, na co wpadł przypadek?

— John Machacek,

@JohnMachacek Próbowałem scharakteryzować rozkłady na które wynikają z wyboru liniowej podprzestrzeni z arbitralnego rozkładu, a następnie równomiernego losowego wyboru elementu podprzestrzeni. Można to wyrazić jako przykrywający LP, którego dualność ma powyższy polytop jako swój możliwy do wykonania region. Fakt, że w tak interesujących okolicznościach był on integralny, wydawał się zbyt interesujący, aby nie udostępniać go tcs.se.

F_{2}^{n}

$\mathbb{F}_2^n$

— Andrew Morgan

@AndrewMorgan Dlaczego polytop jest naturalny lub przydatny? Współrzędne tylko rozmiar przechwytywanego .

x_{i}

$x_i$

G

$G$

— T ....

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^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_0=1/2$ $x_2=\frac{30}{2}-\frac{1}{2}=29/2$ $x_3=\frac{30}{3}-\frac{1}{2}=19/2$ $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 . $\mathbb{F}_2^n$ $n$ $\mathbb{F}_2^4$

— Chao Xu
źródło