On the discrepancy of 3 permutations | Zendy

Bohus Géza | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

On the discrepancy of 3 permutations

Author(s) -

Bohus Géza

Publication year - 1990

Publication title -

random structures and algorithms

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.314

H-Index - 69

eISSN - 1098-2418

pISSN - 1042-9832

DOI - 10.1002/rsa.3240010208

Subject(s) - hypergraph , combinatorics , mathematics , conjecture , bounded function , element (criminal law) , constant (computer programming) , set (abstract data type) , discrete mathematics , computer science , mathematical analysis , political science , law , programming language

Consider different orderings of an n ‐element set and the hypergraph consisting of the intervals of these orderings. A conjecture of J. Beck states that in the case of three orderings this hypergraph has bounded discrepancy. We show that for any constant number of orderings the discrepancy is O (log n ). the proof also gives an efficient algorithm to determine such a coloring.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research