\documentclass[12pt]{article}
\usepackage{amsmath,mathrsfs,bbm}
\usepackage{amssymb}
\textwidth=4.825in
\overfullrule=0pt
\thispagestyle{empty}
\begin{document}
\noindent
%
%
{\bf Dror Fidler }
%
%
\medskip
\noindent
%
%
{\bf A Recurrence for Bounds on Dominating Sets in $k$-Majority Tournaments}
%
%
\vskip 5mm
\noindent
%
%
%
%
A $k$-majority tournament is realized by $2k-1$ linear orders on the set of vertices,
where a vertex $u$ dominates $v$ if $u$ precedes $v$ in at least $k$ of the orders.
Various properties of such tournaments have been studied, among them the problem of
finding the size of a smallest dominating set. It is known that $2$-majority tournaments
are dominated by $3$ vertices and that $k$-majority tournaments are dominated by $O(k
\log k)$ vertices. However, precise values are not known even for $k=3$. We establish
new upper bounds for the size of a smallest dominating set in $k$-majority tournaments
that considerably improve upon previous bounds for small $k$. In particular our result
shows that $3$-majority tournaments are dominated by at most $12$ vertices.
\end{document}