Une version combinatoire de la conjecture polynomiale de Hirsch

Considérons familles disjointes de sous-ensembles de {1,2,…, n}, F 1 , F 2 , … F t .$t$${\cal F}_1,{\cal F_2},\dots {\cal F_t}$

Supposer que

(*)

Pour chaque et chaque R ∈ F i , et T ∈ F k , il existe S ∈ F j qui contient R ∩ T .$i \lt j \lt k$$R \in {\cal F}_i$$T \in {\cal F}_k$$S \in {\cal F}_j$$R \cap T$

La question fondamentale est:

Quelle taille ne peut pas être ???

Ce qui est connu

La borne supérieure la plus connue est le quasi-polynôme .$t \le n^{\log n+1}$

La limite inférieure la plus connue est (jusqu’à un facteur logarithmique) quadratique.

Ce paramètre abstrait est tiré du document Diameter of Polyhedra: The Limits of Abstraction de Friedrich Eisenbrand, Nicolai Hähnle, Sasha Razborov et Thomas Rothvoss . La limite inférieure quadratique ainsi qu'une preuve de la limite supérieure peuvent être trouvées dans leur document.

Motivation

Chaque limite supérieure s'appliquera au diamètre des graphes de polytopes de dimension d à n facettes. Pour voir cette association à chaque sommet l'ensemble S v des facettes le contenant. Puis, partant d’un sommet w, soyons F r les ensembles correspondant aux sommets du polytope de distance r + 1 de w .$v$$S_v$$w$${\cal F}_r$$r+1$$w$

Plus

Ce problème fait l’objet de polymath3 . Mais j’ai pensé qu’il pouvait être utile de le présenter ici et sur MO même s’il s’agissait d’un problème ouvert. Si le projet aboutit à des sous-problèmes spécifiques, je (ou d’autres) pourrais aussi leur poser la question.

(Mise à jour; 5 octobre :) Un problème particulier qui présente un intérêt particulier est de limiter l’attention aux ensembles de taille d. Soit f (d, n) la valeur maximale de t lorsque tous les ensembles de toutes les familles ont une taille d. Soit f * (d, n) la valeur maximale de t lorsque nous autorisons des multisets de taille d. Comprendre f * (3, n) peut être crucial.

Problème: f * (3, n) se comporte-t-il comme 3n ou comme 4n?

Les limites inférieure et supérieure connues sont 3n-2 et 4n-1, respectivement. et puisque le 3 est le début de la séquence 'd' alors que le 4 est le début de la séquence décider si la vérité est 3 ou 4 peut avoir une importance. Voir le deuxième fil .$2^{d-1}$

$t$$n$$d$$3^{2^n}$$f$de ses premières valeurs. Nous n’avons pas non plus étudié en détail tous les commentaires des discussions précédentes, de sorte que certaines de ces informations sont peut-être déjà connues - nous nous sommes bien amusés à créer notre code rapidement et avons voulu publier nos résultats quelque part. Si j’avais un environnement LaTeX fonctionnel, j’aurais mettez ceci sur le ArXiV.

Code (ce n'est pas exactement le code de production ...): http://pastebin.com/bSetW8JS . Valeurs:

f(d=2, n)=2n-1 for n <= 6

f(d=3, n=3) = 6
{} {0} {01} {012} {12} {2}

f(d=4, n=4) = 8
f(d=3, n=4) = 8
{} {0} {01} {1,02,03} {2,13} {123} {23} {3}
{} {0} {01} {2,013} {1,02,03} {023} {23} {3}

f(d=5, n=5) = 11
f(d=4, n=5) = 11
f(d=3, n=5) = 11
{} {0} {01} {1,02} {2,13,04} {12,03,14} {3,124} {23,24} {234} {34} {4}
{} {0} {01} {1,02} {2,13,04} {12,03,14} {3,124} {23,24} {234} {34} {4}
{} {0} {01} {012,3} {02,12,013,014} {13,023,04,124} {123,024} {23,24} {234} {34} {4}
{} {0} {01} {012,13} {02,12,013} {03,123,014,024} {023,124} {23,24} {234} {34} {4}

${\cal F}_1, ..., {\cal F}_t$${\cal F}_1, ..., {\cal F}_t$${\cal F}_1, ..., {\cal F}_{t-1}$${\cal F}_1, ..., {\cal F}_t$$A \in {\cal F}_t$${\cal F}_1, ..., {\cal F}_{t-1}, \{ A \}$$A$${\cal F}_1, ..., {\cal F}_{t-1}$${\cal F}_1, ..., {\cal F}_{t-1}, \{ A \}$${\cal F}_t$${\cal F}_1, ..., {\cal F}_t$

$\sim$${\cal F}_1, ..., {\cal F}_t \sim {\cal F}'_1, ..., {\cal F}'_t$$A$${\cal F}_1, ..., {\cal F}_t$${\cal F}'_1, ..., {\cal F}'_t$${\cal F}_1, ..., {\cal F}_t \sim {\cal F}'_1, ..., {\cal F}'_t$${\cal F}_1, ..., {\cal F}_t, {\cal F}_{t+1}$${\cal F}_1, ..., {\cal F}_t, {\cal F}_{t+1} \sim {\cal F}'_1, ..., {\cal F}'_t, {\cal F}_{t+1}$${\cal F}_1, ..., {\cal F}_t, {\cal F}_{t+1}$${\cal F}_{t+1}$${\cal F}_1, ..., {\cal F}_t$. L'algorithme de programmation dynamique qui en résulte est alors évident. Le nombre de classes d'équivalence (ainsi que le temps pris par les deux opérations ci-dessus) donne ensuite une limite sur le temps d'exécution de l'algorithme de programmation dynamique évident.

$A$$\{ 1, \dots, n \}$$A$${\cal F}_1, ..., {\cal F}_t$$\{ k \mid \exists B \in {\cal F}_k : A \subseteq B \} = \{ i, \dots, j \}$$1 \leq i \leq j \leq n$$(i, j)$$A$${\cal F}_1, ..., {\cal F}_t$$\{ 1, \dots, n \}$

${\cal F}_1, ..., {\cal F}_t$$\{ 1, \dots, n \}$${\cal F}_t$${\cal F}_1, ..., {\cal F}_{t-1}$$B$$A$${\cal F}_1, ..., {\cal F}_{t-1}$$(i, j)$$j < t - 1$$A$$\sim$$B$$C \in {\cal F}_t$$D \in {\cal F}_{t+1}$$B \cap C \subseteq D$$3^{2^n}$

${\cal F}_{t+1}$${1, \dots, i}$${\cal F}_1 = \{ \{ 1 \} \}, {\cal F}_2 = \{ \{ 1, 2 \} \}$${\cal F}_{t-1}$${\cal F}_t$${\cal F}_3$ peut entraîner des économies plus drastiques.