Publikace detail

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

Autoři: Rozinek Ondřej

Rok: 2024

Druh publikace: článek ve sborníku

Název zdroje: Informatics 2024 : 2024 IEEEE 17th International Scientific Conference on Informatics : proceedings

Název nakladatele: IEEE (Institute of Electrical and Electronics Engineers)

Místo vydání: New York

Strana od-do: 532-537

Tituly:

Jazyk	Název	Abstrakt	Klíčová slova
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

Vyhledávání

Přihlášení pro studenty

Přihlášení pro zaměstnance

Publikace detail

Katedry

Služby

Jak nás najdete?

Často hledáte