Apakah “pengepakan subkelompok” ini merupakan bagian integral?

Biarkan menjadi grup abelian terbatas, dan misalkan menjadi polytope di didefinisikan sebagai poin memenuhi ketidaksetaraan berikut:P R Γ$\Gamma$$P$$\mathbb{R}^\Gamma$$x$

di mana berarti adalah subkelompok dari . Apakah terpisahkan? Jika demikian, dapatkah kita mengkarakterisasi simpulnya?G Γ $G \le \Gamma$$G$$\Gamma$$P$

Pertanyaan saya awalnya muncul dengan , di mana beberapa contoh kecil ( ) menunjukkan bahwa jawabannya adalah "ya" dan "mungkin, tetapi tidak sederhana". Saya juga mencoba grup siklik pada elemen 9 dan 10, serta , di mana lagi polytope adalah integral. Polytope tidak terpisahkan ketika adalah salah satu dari , , dan , jadi abelianness tampaknya penting. 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$

Saya harus menyebutkan bahwa jika Anda menulis set pertama persamaan sebagai , maka belum tentu sama sekali tidak simetris (yang akan menyiratkan polytope adalah integral). Ketika , Anda dapat memilih tiga bebas linier dan mengambil tiga dibentangkan oleh setiap pasangan elemen yang dipilih . dihasilkan adalah hingga permutasi, dan karenanya memiliki determinan .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$

Sangat mudah (jika membosankan) untuk mengkarakterisasi simpul untuk kelompok orde utama dan mengamati bahwa mereka integral. Saya cukup yakin ini dapat diperluas ke grup siklik dengan memesan kekuatan utama. Saya tidak yakin apa yang terjadi ketika mengambil produk.

Sistem ini sangat mengingatkan pada polymatroid yang mendefinisikan , tetapi alih-alih fungsi himpunan submodular, batasannya adalah "fungsi subkelompok" yang saya curigai adalah 'submodular' begitu ditetapkan dengan cara yang benar. Namun, teknik untuk menunjukkan polymatroid tertentu merupakan bagian integral mungkin bekerja di sini juga, tapi saya tidak mengerti caranya.

Juga, analisis Fourier mungkin relevan: ketika , tampaknya simpul yang memaksimalkan adalah titik dengan untuk semua , serta yang dengan di mana adalah -th karakter Fourier (berikut notasi standar dari analisis fungsi boolean), dan tidak kosong. (Ketika kosong, titik yang sesuai adalah , yang juga merupakan simpul.) Σ 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 (si penanya) dan saya telah membahas ini melalui email, dan kami telah menunjukkan dugaan itu salah. Polytope tidak terpisahkan untuk kelompok Abelian, bahkan untuk kelompok siklik.

Di sisi positif.

Teorema : Untuk grup siklik dengan urutan , di mana dan adalah bilangan prima dan , matriks kejadian elemen dan subkelompok benar-benar tidak simetris.p q k ∈ $p^kq$$p$$q$$k\in \mathbb{N}$

Ini karena keluarga subkelompok adalah penyatuan dua keluarga laminar.

Oleh karena itu, ini menunjukkan sampel tandingan terkecil untuk grup siklik harus memiliki pesanan minimal . Ini sebenarnya menjelaskan mengapa tidak ada sampel kecil yang ditemukan.$2\times 3\times 5 =30$

Andrew menjalankan beberapa perhitungan, dan menemukan contoh tandingan untuk kelompok siklik pesanan .$30$

Contoh tandingan : , x 2 = 30$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$, dan0di tempat lain. Tidak sulit untuk memeriksa titik yang layak. Di sini saya ulangi bukti Andrew bahwa ini sebenarnya sebuah simpul. Ada30kendala ketat. Batasan seluruh kelompok, tiga subkelompok yang dihasilkan oleh2,3dan5masing-masing, dan kendala non-negatif. Karena kita memiliki30variabel,xadalah simpul.$x_5=\frac{30}{5}-\frac{1}{2}=11/2$$0$$30$$2,3$$5$$30$$x$

Orang mungkin bertanya-tanya apakah polytope untuk adalah integral untuk semua n . Sayangnya, Andrew juga menemukan polytope non-integral untuk F 4 2 .$\mathbb{F}_2^n$$n$$\mathbb{F}_2^4$