Efron's coins and the linial arrangement

DOI10.1016/J.DISC.2016.06.012zbMATH Open1343.05070arXiv1511.04482OpenAlexW2963535974MaRDI QIDQ738854FDOQ738854

Gabor Hetyei

Publication date: 16 August 2016

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: We characterize the tournaments that are dominance graphs of sets of (unfair) coins in which each coin displays its larger side with greater probability. The class of these tournaments coincides with the class of tournaments whose vertices can be numbered in a way that makes them semiacyclic, as defined by Postnikov and Stanley. We provide an example of a tournament on nine vertices that can not be made semiacyclic, yet it may be represented as a dominance graph of coins, if we also allow coins that display their smaller side with greater probability. We conclude with an example of a tournament with $81$ vertices that is not the dominance graph of any system of coins.

Full work available at URL: https://arxiv.org/abs/1511.04482

zbMATH Keywords

nontransitive dicesemiacyclic tournament

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Title not available (Why is that?)
• Stable sets in one-seller assignment games
• The Voting Problem
• Facing up to arrangements: face-count formulas for partitions of space by hyperplanes
• The Paradox of Nontransitive Dice
• Deformations of Coxeter hyperplane arrangements
• Dominating sets in \(k\)-majority tournaments.
• Intransitive trees
• Extended linial hyperplane arrangements for root systems and a conjecture of Postnikov and Stanley
• Partial order on a family of \(k\)-subsets of a linearly ordered set

Cited In (1)

• A Game of Nontransitive Dice

Uses Software

• OEIS

This page was built for publication: Efron's coins and the linial arrangement

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q738854)