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

Result code in 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>
Result on the web
<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>

Result language
angličtina
Original language name
A Similarity Space Approach to the 1/3-2/3 Conjecture in Partially Ordered Sets
Original language description
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.
Czech name
—
Czech description
—

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

Article name in the collection
Informatics 2024 : 2024 IEEEE 17th International Scientific Conference on Informatics : proceedings
ISBN
979-8-3503-8766-7
ISSN
—
e-ISSN
—
Number of pages
7
Pages from-to
532-537
Publisher name
IEEE (Institute of Electrical and Electronics Engineers)
Place of publication
New York
Event location
Poprad
Event date
Nov 13, 2024
Type of event by nationality
EUR - Evropská akce
UT code for WoS article
001483035700086

Similar results(10)