Sea un grupo abeliano finito, y sea el politopo en definido como los puntos satisfacen las siguientes desigualdades:P R Γ x
donde significa que es un subgrupo de . ¿Es integral? Si es así, ¿podemos caracterizar sus vértices?G
Mi pregunta originalmente surgió con , donde algunos pequeños ejemplos ( ) sugieren que la respuesta es "sí" y "tal vez, pero no es simple". También probé el grupo cíclico en 9 y 10 elementos, así como , donde nuevamente el politopo es integral. El politopo no es integral cuando es cualquiera de , y , por lo que la abelianness es aparentemente esencial.
Debo mencionar que si escribe el primer conjunto de ecuaciones como , entonces no es necesariamente totalmente unimodular (lo que implicaría que el politopo es integral). Cuando , puede elegir tres linealmente independientes y tomar las tres abarca cada par de elementos seleccionados . La submatriz resultante es hasta la permutación, y también tiene determinante .
Es fácil (aunque tedioso) caracterizar los vértices para grupos de primer orden y observar que son integrales. Estoy bastante seguro de que esto puede extenderse a grupos cíclicos con un orden de primer poder. No estoy seguro de lo que sucede al tomar productos.
Este sistema recuerda mucho a los que definen los polimatroides , pero en lugar de una función de conjunto submodular, las restricciones son una "función de subgrupo" que sospecho que es "submodular" una vez que se ha definido de la manera correcta. Aún así, las técnicas para mostrar que ciertos polimatroides son integrales también podrían funcionar aquí, pero no veo cómo.
Además, el análisis de Fourier puede ser relevante: cuando , parece que los vértices que maximizan son exactamente el punto con para todo , así como aquellos con donde es el -ésimo carácter de Fourier (siguiendo la notación estándar del análisis de funciones booleanas), y no está vacío. (Cuando está vacío, el punto correspondiente es , que también es un vértice).
fuente
Respuestas:
Andrew (el autor de la pregunta) y yo discutimos esto por correo electrónico, y hemos demostrado que la conjetura es falsa. El politopo no es integral para los grupos abelianos, ni siquiera para los grupos cíclicos.
En el lado positivo.
Teorema : para grupos cíclicos con el orden , donde p y q son primos y k ∈ N , la matriz de incidencia de elementos y subgrupos es totalmente unimodular.pkq p q k∈N
Esto se debe a que la familia de subgrupos es una unión de dos familias laminares.
fuente