Publication detail

A Similarity Space Approach to the 1/3-2/3 Conjecture in Partially Ordered Sets

Authors: Rozinek Ondřej

Year: 2024

Type of publication: článek ve sborníku

Name of source: Informatics 2024 : 2024 IEEEE 17th International Scientific Conference on Informatics : proceedings

Publisher name: IEEE (Institute of Electrical and Electronics Engineers)

Place: New York

Page from-to: 532-537

Titles:

Language	Name	Abstract	Keywords
cze	Přístup prostoru podobnosti k domněnce 1/3-2/3 v částečně uspořádaných množinách	Domněnka 1/3-2/3, dlouholetý otevřený problém v kombinatorice, tvrdí, že v každém neřetězcovém konečném parciálním řádu existuje dvojice prvků (x, y) taková, že pravděpodobnost P(x ≺ y) leží v intervalu [1/3, 2/3]. Tento článek představuje nový přístup k řešení této domněnky s využitím konceptu prostorů podobnosti. Zavádíme pojem „rovnovážné konstanty“ v rámci podobnostních prostorů a dokazujeme, že její nadhodnota je 1/2, čímž potvrzujeme související domněnku. Naším hlavním přínosem je důkaz, že infimum normalizované podobnosti v množinách je 1/3, kterého jsme dosáhli v případě totálního nepořádku. Tento výsledek poskytuje nový pohled na domněnku 1/3-2/3 a spojuje ji s teorií podobnostních prostorů. Stanovujeme také vztahy mezi editační vzdáleností, výměnnými operacemi a zobecněnou Rozinekovou podobností a nabízíme vhled do struktury totálně neuspořádaných posloupností. Přestože poskytujeme důkaz domněnky 1/3-2/3 v obecném případě pomocí našeho přístupu, uznáváme, že k úplnému vyřešení tohoto dlouholetého problému v kombinatorice a teorii uspořádání je stále zapotřebí důkladnější a podrobnější důkaz.	1/3-2/3 domněnka; třídění; částečný řád; lineární rozšíření; podobnostní prostor
eng	A Similarity Space Approach to the 1/3-2/3 Conjecture in Partially Ordered Sets	The 1/3-2/3 Conjecture, a longstanding open problem in combinatorics, posits that in any non-chain finite partial order, there exists a pair of elements (x, y) such that the probability P(x ≺ y) lies in the interval [1/3, 2/3]. This paper presents a novel approach to addressing this conjecture by leveraging the concept of similarity spaces. We introduce the notion of a ’balance constant’ within the framework of similarity spaces and prove that its supremum is 1/2, confirming a related conjecture. Our main contribution is the proof that the infimum of normalized similarity in posets is 1/3, achieved in the case of total disorder. This result provides a new perspective on the 1/3-2/3 Conjecture, connecting it to the theory of similarity spaces. We also establish relationships between edit distance, swap operations, and Generalized Rozinek Similarity, offering insights into the structure of totally disordered sequences. While we provide a proof of the 1/3-2/3 Conjecture in the general case using our approach, we acknowledge that a more rigorous and detailed proof is still needed to fully resolve this longstanding problem in combinatorics and order theory.	1/3-2/3 Conjecture; Sorting; Partial Order; Linear Extension; Similarity Space

Search

Login for students

Login for employees

Publication detail

Department

Map

Services

Popular Links