Conjecture 1/3 - 2/3
En théorie des ordres, en combinatoire et en algorithmique, la conjecture 1/3–2/3 affirme que lors d'un tri par comparaison, quelles que soient les comparaisons déjà effectuées, il est toujours possible de choisir la comparaison suivante de telle sorte que le nombre d'ordres possibles soit réduit d'un facteur au moins égal à 2/3 et au plus à 1/3. Cela est équivalent à ce que dans tout ensemble partiellement ordonné fini non totalement ordonné, il existe deux éléments x et y tels qu'au moins 1/3 et au plus 2/3 des extensions linéaires de l'ordre partiel placent x avant y.
Définitions et énoncé de la conjecture[modifier | modifier le code]
Un ensemble partiellement ordonné est un ensemble X muni d'une relation binaire ≤ réflexive, antisymétrique, et transitive. Un ordre total est un ordre partiel pour lequel tout couple d'éléments est comparable. Un ordre total sur X prolonge l'ordre partiel si x ≤ y pour l'ordre partiel entraîne x ≤ y pour l'ordre total. Sauf si X est totalement ordonné, plusieurs prolongements sont possibles, et la conjecture 1/3–2/3 affirme qu'il existe alors toujours deux éléments x et y (non comparables) tels que parmi ces prolongements, x est avant y dans au moins 1/3 des cas (et donc, par symétrie, y est avant x dans au plus 2/3 des cas)[1].
Dans le langage de la théorie des probabilités, on peut formuler la conjecture ainsi : avec une distribution de probablilité uniforme sur les ordres totaux prolongeant l'ordre donné, il existe toujours deux éléments x et y tels que la probabilité que x soit avant y dans une de ces extensions choisie au hasard est comprise entre 1/3 and 2/3 (en revanche, la conjecture ne dit rien sur la probabilité qu'il en soit ainsi si x et y sont choisis au hasard)[1].
En 1984, Jeff Kahn et Michael Saks ont défini δ(P), pour un ordre partiel P, comme le plus grand réel δ tel que P admette un couple (x, y) avec x précédant y dans une proportion d'ordres totaux prolongeant P comprise entre δ et 1−δ. Avec cette notation, la conjecture 1/3–2/3 affirme que les ordres partiels finis vérifient δ(P) ≥ 1/3[2].
Exemples[modifier | modifier le code]
L'ordre partiel formé par trois éléments a, b, et c avec la seule relation a ≤ b a trois prolongements totalement ordonnés : a ≤ b ≤ c, a ≤ c ≤ b, et c ≤ a ≤ b. a précède c dans deux de ces ordres, et donc le couple (a,c) possède la propriété cherchée, ce qui montre que cet ordre partiel vérifie la conjecture 1/3–2/3 (et que ces nombres sont les meilleurs possibles)[3].
Plus généralement, soit P un ordre série-parallèle (en) composé à partir d'ordres partiels, comme sur la figure ci-contre. P est un cas extrémal de la conjecture1/3–2/3, au sens où pour chaque paire d'éléments non comparables, l'un des deux apparait avant l'autre dans au plus 1/3 des ordres totaux prolongeant P. Les ordres construits ainsi sont les seuls cas extrémaux connus de la conjecture, et on peut démontrer que ce sont les seuls cas extrémaux d'ordres partiels de largeur 2[4].
Historique[modifier | modifier le code]
La conjecture 1/3–2/3 fut formulée par Sergey Kislitsyn (en) en 1968[5], et indépendamment par Michael Fredman (en)[6] et par Nati Linial en 1984[1]. Elle figurait comme exemple de conjecture ouverte dans le premier numéro de la revue Order, et reste non résolue ; elle a été appelée « l'un des problèmes les plus intrigants de la théorie des ensembles partiellement ordonnés[1] ». Un tour d'horizon de l'état de la conjecture a été publié en 1999[7].
Résultats partiels[modifier | modifier le code]
La conjecture 1/3–2/3 est vérifiée par certaines classes d'ordre partiels, comme ceux de largeur 2[8], ceux de hauteur 2[9], ceux ayant au plus 11 éléments[10], ceux dans lesquels chaque élément est incomparable à au plus 6 autres[11], ou encore les polyarbres[12]. La proportion d'ordres partiels à n éléments pour lesquels la conjecture est vraie tend vers 100% lorsque n tend vers l'infini[10].
En 1995, Graham Brightwell, Stefan Felsner, et William Trotter démontrèrent que pour tout ordre P (non total), δ(P) ≥ 1/2 − √5/10 ≈ 0.276, améliorant plusieurs autres bornes antérieures[13]. Utilisant l'interprétation probabiliste de δ(P) pour le définir pour des ordres infinis, ils montrèrent que cette borne est optimale, car il existe des ordres infinis pour lesquels δ(P) = 1/2 − √5/10.
Applications[modifier | modifier le code]
En 1984, Jeff Kahn et Michael Saks proposèrent l'application suivante : on veut trier par comparaison un ensemble X totalement ordonné, pour lequel on a déjà certaines information sous forme d'un ordre partiel. La conjecture 1/3–2/3 affirme qu'à chaque étape il existe une comparaison qui réduit d'un facteur 2/3 (dans le plus mauvais cas) le nombre d'ordres compatibles avec l'information déjà connue, ce qui implique que s'il restait initialement un nombre E d'ordres possibles, le tri demande au plus log3/2E comparaisons[2].
Cette analyse néglige cependant la difficulté de sélectionner la paire optimale pour chaque nouvelle comparaison. De plus, on peut parfois trier avec un nombre de comparaisons inférieur à ce que suggère cette analyse, le plus mauvais cas ne se produisant pas forcément à chaque étape. En fait, il est conjecturé que logφE comparaisons peuvent suffire,, où φ est le nombre d'or[10].
Généralisations et résultats associés[modifier | modifier le code]
En 1984, Kahn et Saks ont également conjecturé que, lorsque w tend vers l'infini, la valeur de δ(P) pour des ensembles partiellement ordonnés de largeur w devrait tendre vers 1/2. En particulier, ils s'attendent à ce que seuls des ordres de largeur 2 correspondent au pire cas δ(P) = 1/3[14], et en 1985 Martin Aigner a énoncé cela comme une c conjecture explicite[4]. La plus petite valeur connue de δ(P) pour des ordres de largeur 3 est 14/39[15], et on sait qu'on ne peut avoir une valeur inférieure pour des ordres de largeur 3 ayant 9 éléments ou moins[9]. Une autre conjecture basée également sur des explorations par ordinateur est que si δ(P) ne vaut pas exactement 1/3, alors δ(P) ≥ 0.348843[16].
Marcin Peczarski a formulé une « conjecture de la partition dorée » affirmant que pour tout ordre non total, on peut trouver deux comparaisons successives telles que, notant ti le nombre d'ordres totaux compatibles avec ce qui reste après que i des comparisons aient été faites, alors (quel que soit le résultat de ces comparaisons) t0 ≥ t1 + t2. Cette conjecture implique la conjecture 1/3–2/3, et implique également (avec les notations précédentes) que le tri peut s'effectuer avec au plus logφE comparaisons, d'où le nom de cette conjecture en relation avec le nombre d'or[10],[11].
Notes[modifier | modifier le code]
- Brightwell, Felsner et Trotter (1995).
- Kahn et Saks 1984
- Kahn et Saks 1984 ; Brightwell, Felsner et Trotter 1995.
- Aigner (1985).
- Kislitsyn 1968
- Fredman 1976. Cependant, en dépit de la relation étroite des questions qu'il analyse avec la conjecture 1/3–2/3, celle-ci n'est pas mentionnée explicitement dans cet article.
- Brightwell 1999
- Linial 1984, Theorem 2; Sah 2021.
- Trotter, Gehrlein et Fishburn (1992).
- Peczarski 2006.
- Peczarski 2008.
- Zaguia (2019).
- Brightwell, Felsner et Trotter 1995; Kahn et Saks 1984; Khachiyan 1989; Kahn et Linial 1991; Felsner et Trotter 1993.
- Kahn et Saks (1984).
- Saks (1985).
- Peczarski (2019).
Références[modifier | modifier le code]
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « 1/3–2/3 conjecture » (voir la liste des auteurs).
- (en) Martin Aigner, « A note on merging », Order, vol. 2, no 3, , p. 257–264 (DOI 10.1007/BF00333131, S2CID 118877843, lire en ligne).
- (en) Graham R. Brightwell, « Semiorders and the 1/3–2/3 conjecture », Order, vol. 5, no 4, , p. 369–380 (DOI 10.1007/BF00353656, S2CID 86860160).
- (en) Graham R. Brightwell, « Balanced pairs in partial orders », Discrete Mathematics, vol. 201, nos 1–3, , p. 25–52 (DOI 10.1016/S0012-365X(98)00311-2).
- (en) Graham R. Brightwell, Stefan Felsner et William T. Trotter, « Balancing pairs and the cross product conjecture », Order, vol. 12, no 4, , p. 327–349 (DOI 10.1007/BF01110378, MR 1368815, S2CID 14793475, CiteSeerx 10.1.1.38.7841).
- (en) Graham R. Brightwell et Peter Winkler, « Counting linear extensions », Order, vol. 8, no 3, , p. 225–242 (DOI 10.1007/BF00383444, S2CID 119697949).
- (en) Stefan Felsner et William T. Trotter, Combinatorics, Paul Erdős is eighty, vol. 1, Budapest, János Bolyai Mathematical Society, coll. « Bolyai Society Mathematical Studies », , 145–157 p. (MR 1249709).
- (en) M. L. Fredman, « How good is the information theory bound in sorting? », Theoretical Computer Science, vol. 1, no 4, , p. 355–361 (DOI 10.1016/0304-3975(76)90078-5)
- (en) Jeff Kahn et Nati Linial, « Balancing extensions via Brunn-Minkowski », Combinatorica, vol. 11, no 4, , p. 363–368 (DOI 10.1007/BF01275670, S2CID 206793172).
- (en) Jeff Kahn et Michael Saks, « Balancing poset extensions », Order, vol. 1, no 2, , p. 113–126 (DOI 10.1007/BF00565647, S2CID 123370506).
- (ru) Leonid Khachiyan, Computers and Decision Problems, Moscow, Nauka, , 161–205 p.. Cité par Brightwell, Felsner et Trotter 1995.
- (en) S. S. Kislitsyn, « A finite partially ordered set and its corresponding set of permutations », Mathematical Notes, vol. 4, no 5, , p. 798–801 (DOI 10.1007/BF01111312, S2CID 120228193).
- (en) Nati Linial, « The information-theoretic bound is good for merging », SIAM Journal on Computing, vol. 13, no 4, , p. 795–801 (DOI 10.1137/0213049, S2CID 5149351).
- (en) Marcin Peczarski, « The gold partition conjecture », Order, vol. 23, no 1, , p. 89–95 (DOI 10.1007/s11083-006-9033-1, S2CID 42415160).
- (en) Marcin Peczarski, « The gold partition conjecture for 6-thin posets », Order, vol. 25, no 2, , p. 91–103 (DOI 10.1007/s11083-008-9081-9, S2CID 42034095).
- (en) Marcin Peczarski, « The worst balanced partially ordered sets—ladders with broken rungs », Experimental Mathematics, vol. 28, no 2, , p. 181–184 (DOI 10.1080/10586458.2017.1368050, MR 3955809, S2CID 125593629).
- (en) Ashwin Sah, « Improving the – conjecture for width two posets », Combinatorica, vol. 41, no 1, , p. 99–126 (DOI 10.1007/s00493-020-4091-3, MR 4235316, arXiv 1811.01500, S2CID 119604901)
- (en) Michael Saks, « Balancing linear extensions of ordered sets », Order, vol. 2, , p. 327–330 (DOI 10.1007/BF00333138, S2CID 189901558, lire en ligne)
- (en) William T. Trotter, William V. Gehrlein et Peter C. Fishburn, « Balance theorems for height-2 posets », Order, vol. 9, no 1, , p. 43–53 (DOI 10.1007/BF00419038, S2CID 16157076).
- (en) Imed Zaguia, « The 1/3-2/3 Conjecture for N-free ordered sets », Electronic Journal of Combinatorics, vol. 19, no 2, , P29 (DOI 10.37236/2345, Bibcode 2011arXiv1107.5626Z, arXiv 1107.5626, S2CID 1979845).
- (en) Imed Zaguia, « The 1/3–2/3 conjecture for ordered sets whose cover graph is a forest », Order, vol. 36, no 2, , p. 335–347 (DOI 10.1007/s11083-018-9469-0, MR 3983482, arXiv 1610.00809, S2CID 119631612).