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

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216275%3A25530%2F24%3A39922659" target="_blank" >RIV/00216275:25530/24:39922659 - isvavai.cz</a>

Výsledek na webu

<a href="https://ieeexplore.ieee.org/document/10900886" target="_blank" >https://ieeexplore.ieee.org/document/10900886</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1109/Informatics62280.2024.10900886" target="_blank" >10.1109/Informatics62280.2024.10900886</a>

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

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

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10200 - Computer and information sciences

Projekt

—

Návaznosti

R - Projekt Ramcoveho programu EK

Rok uplatnění

2024

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Informatics 2024 : 2024 IEEEE 17th International Scientific Conference on Informatics : proceedings

ISBN

979-8-3503-8766-7

ISSN

—

e-ISSN

—

Počet stran výsledku

7

Strana od-do

532-537

Název nakladatele

IEEE (Institute of Electrical and Electronics Engineers)

Místo vydání

New York

Místo konání akce

Poprad

Datum konání akce

13. 11. 2024

Typ akce podle státní příslušnosti

EUR - Evropská akce

Kód UT WoS článku

001483035700086