Dominating sets in k-majority tournaments

Noga Alon; Graham Brightwell; H. A. Kierstead; A. V. Kostochka; Peter Winkler

doi:10.1016/j.jctb.2005.09.003

Dominating sets in k-majority tournaments

Noga Alon, Graham Brightwell, H. A. Kierstead, A. V. Kostochka, Peter Winkler

Research output: Contribution to journal › Article › peer-review

31 Scopus citations

Abstract

A k-majority tournament T on a finite vertex set V is defined by a set of 2 k - 1 linear orderings of V, with u → v if and only if u lies above v in at least k of the orders. Motivated in part by the phenomenon of "non-transitive dice", we let F ( k ) be the maximum over all k-majority tournaments T of the size of a minimum dominating set of T. We show that F ( k ) exists for all k > 0, that F ( 2 ) = 3 and that in general C₁ k / log k ≤ F ( k ) ≤ C₂ k log k for suitable positive constants C₁ and C₂.

Original language	English (US)
Pages (from-to)	374-387
Number of pages	14
Journal	Journal of Combinatorial Theory. Series B
Volume	96
Issue number	3
DOIs	https://doi.org/10.1016/j.jctb.2005.09.003
State	Published - May 2006
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Keywords

Dominating set
Tournament
k-majority

Access to Document

10.1016/j.jctb.2005.09.003

Cite this

@article{20ae651070cf49e5b0c601908c80115a,

title = "Dominating sets in k-majority tournaments",

abstract = "A k-majority tournament T on a finite vertex set V is defined by a set of 2 k - 1 linear orderings of V, with u → v if and only if u lies above v in at least k of the orders. Motivated in part by the phenomenon of {"}non-transitive dice{"}, we let F ( k ) be the maximum over all k-majority tournaments T of the size of a minimum dominating set of T. We show that F ( k ) exists for all k > 0, that F ( 2 ) = 3 and that in general C1 k / log k ≤ F ( k ) ≤ C2 k log k for suitable positive constants C1 and C2.",

keywords = "Dominating set, Tournament, k-majority",

author = "Noga Alon and Graham Brightwell and Kierstead, {H. A.} and Kostochka, {A. V.} and Peter Winkler",

note = "Funding Information: Kierstead), [email protected] (A.V. Kostochka), [email protected] (P. Winkler). 1Research supported in part by a USA-Israeli BSF grant, by the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. 2Supported in part by NSA Grant MDA904-03-1-0007. 3Supported in part by NSF Grants DMS-0099608 and DMS-0400498. 4Work done while at Bell Labs, Lucent Technologies and at Institute for Advanced Study, supported in part by NMIMT/ICASA grant MDA904-01-C-0327.",

year = "2006",

month = may,

doi = "10.1016/j.jctb.2005.09.003",

language = "English (US)",

volume = "96",

pages = "374--387",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "3",

}

TY - JOUR

T1 - Dominating sets in k-majority tournaments

AU - Alon, Noga

AU - Brightwell, Graham

AU - Kierstead, H. A.

AU - Kostochka, A. V.

AU - Winkler, Peter

N1 - Funding Information: Kierstead), [email protected] (A.V. Kostochka), [email protected] (P. Winkler). 1Research supported in part by a USA-Israeli BSF grant, by the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. 2Supported in part by NSA Grant MDA904-03-1-0007. 3Supported in part by NSF Grants DMS-0099608 and DMS-0400498. 4Work done while at Bell Labs, Lucent Technologies and at Institute for Advanced Study, supported in part by NMIMT/ICASA grant MDA904-01-C-0327.

PY - 2006/5

Y1 - 2006/5

N2 - A k-majority tournament T on a finite vertex set V is defined by a set of 2 k - 1 linear orderings of V, with u → v if and only if u lies above v in at least k of the orders. Motivated in part by the phenomenon of "non-transitive dice", we let F ( k ) be the maximum over all k-majority tournaments T of the size of a minimum dominating set of T. We show that F ( k ) exists for all k > 0, that F ( 2 ) = 3 and that in general C1 k / log k ≤ F ( k ) ≤ C2 k log k for suitable positive constants C1 and C2.

AB - A k-majority tournament T on a finite vertex set V is defined by a set of 2 k - 1 linear orderings of V, with u → v if and only if u lies above v in at least k of the orders. Motivated in part by the phenomenon of "non-transitive dice", we let F ( k ) be the maximum over all k-majority tournaments T of the size of a minimum dominating set of T. We show that F ( k ) exists for all k > 0, that F ( 2 ) = 3 and that in general C1 k / log k ≤ F ( k ) ≤ C2 k log k for suitable positive constants C1 and C2.

KW - Dominating set

KW - Tournament

KW - k-majority

UR - http://www.scopus.com/inward/record.url?scp=33646104195&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33646104195&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2005.09.003

DO - 10.1016/j.jctb.2005.09.003

M3 - Article

AN - SCOPUS:33646104195

SN - 0095-8956

VL - 96

SP - 374

EP - 387

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 3

ER -

Dominating sets in k-majority tournaments

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this