1MTA-ELTE Lendület Combinatorial Geometry Research Group, Institute of Mathematics, Eötvös Loránd University, Budapest, Hungary 2Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, Hungary 3Department of Mathematics, École Polytechnique Fédérale de Lausanne, Lausanne, Switzerland 4Dept. of Computer Science and Information Theory, Budapest University of Technology and Economics, Budapest, Hungary
Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 601-609
Citer cet article
Gábor Damásdi; Dániel Gerbner; Gyula O. H. Katona; Abhishek Methuku; Balázs Keszegh; Dániel Lenger; Dániel T. Nagy; Dömötör Pálvölgyi; Balázs Patkós; Máté Vizer; Gábor Wiener; Gábor Damásdi; Dániel Gerbner; Gyula O. H. Katona; Abhishek Methuku; Balázs Keszegh; Dániel Lenger; Dániel T. Nagy; Dömötör Pálvölgyi; Balázs Patkós; Máté Vizer; Gábor Wiener. Adaptive majority problems for restricted query graphs and for weighted sets. Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 601-609. http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a38/
@article{AMUC_2019_88_3_a38,
author = {G\'abor Dam\'asdi and D\'aniel Gerbner and Gyula O. H. Katona and Abhishek Methuku and Bal\'azs Keszegh and D\'aniel Lenger and D\'aniel T. Nagy and D\"om\"ot\"or P\'alv\"olgyi and Bal\'azs Patk\'os and M\'at\'e Vizer and G\'abor Wiener and G\'abor Dam\'asdi and D\'aniel Gerbner and Gyula O. H. Katona and Abhishek Methuku and Bal\'azs Keszegh and D\'aniel Lenger and D\'aniel T. Nagy and D\"om\"ot\"or P\'alv\"olgyi and Bal\'azs Patk\'os and M\'at\'e Vizer and G\'abor Wiener},
title = { Adaptive majority problems for restricted query graphs and for weighted sets},
journal = {Acta mathematica Universitatis Comenianae},
pages = {601--609},
year = {2019},
volume = {88},
number = {3},
url = {http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a38/}
}
TY - JOUR
AU - Gábor Damásdi
AU - Dániel Gerbner
AU - Gyula O. H. Katona
AU - Abhishek Methuku
AU - Balázs Keszegh
AU - Dániel Lenger
AU - Dániel T. Nagy
AU - Dömötör Pálvölgyi
AU - Balázs Patkós
AU - Máté Vizer
AU - Gábor Wiener
AU - Gábor Damásdi
AU - Dániel Gerbner
AU - Gyula O. H. Katona
AU - Abhishek Methuku
AU - Balázs Keszegh
AU - Dániel Lenger
AU - Dániel T. Nagy
AU - Dömötör Pálvölgyi
AU - Balázs Patkós
AU - Máté Vizer
AU - Gábor Wiener
TI - Adaptive majority problems for restricted query graphs and for weighted sets
JO - Acta mathematica Universitatis Comenianae
PY - 2019
SP - 601
EP - 609
VL - 88
IS - 3
UR - http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a38/
ID - AMUC_2019_88_3_a38
ER -
%0 Journal Article
%A Gábor Damásdi
%A Dániel Gerbner
%A Gyula O. H. Katona
%A Abhishek Methuku
%A Balázs Keszegh
%A Dániel Lenger
%A Dániel T. Nagy
%A Dömötör Pálvölgyi
%A Balázs Patkós
%A Máté Vizer
%A Gábor Wiener
%A Gábor Damásdi
%A Dániel Gerbner
%A Gyula O. H. Katona
%A Abhishek Methuku
%A Balázs Keszegh
%A Dániel Lenger
%A Dániel T. Nagy
%A Dömötör Pálvölgyi
%A Balázs Patkós
%A Máté Vizer
%A Gábor Wiener
%T Adaptive majority problems for restricted query graphs and for weighted sets
%J Acta mathematica Universitatis Comenianae
%D 2019
%P 601-609
%V 88
%N 3
%U http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a38/
%F AMUC_2019_88_3_a38
Suppose that the vertices of a graph $G$ are colored with two colors in an unknown way. The color that occurs on more than half of the vertices is called the \emph{majority color} (if it exists), and any vertex of this color is called a \emph{majority vertex}. We study the problem of finding a majority vertex (or show that none exists), if we can query edges to learn whether their endpoints have the same or different colors. Denote the least number of queries needed in the worst case by $m(G)$. It was shown by Saks and Werman that $m(K_n)\!=\! n-b(n)$ where $b(n)$ is the number of 1's in the binary representation of $n$. In this paper we initiate the study of the problem for general graphs. The obvious bounds for a connected graph $G$ on $n$ vertices are $n-b(n)\le m(G)\le n-1$. We show that for any tree $T$ on an even number of vertices we have $m(T)=n-1$, and that for any tree $T$ on an odd number of vertices, we have $n-65\le m(T)\le n-2$. Our proof uses results about the weighted version of the problem for $K_n$, which may be of independent interest. We also exhibit a sequence $G_n$ of graphs with $m(G_n)=n-b(n)$ such that the number of edges in $G_n$ is $O(nb(n))$.
