Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-19T05:13:26.714Z Has data issue: false hasContentIssue false

Schütte's Tournament Problem and Intersecting Families of Sets

Published online by Cambridge University Press:  04 July 2003

MIECZYSŁAW BOROWIECKI
Affiliation:
Institute of Mathematics, University of Zielona Góra, 65-246 Zielona Góra, Poland (e-mail: [email protected])
JAROSŁAW GRYTCZUK
Affiliation:
Institute of Mathematics, University of Zielona Góra, 65-246 Zielona Góra, Poland (e-mail: [email protected])
MARIUSZ HAŁUSZCZAK
Affiliation:
Institute of Mathematics, University of Zielona Góra, 65-246 Zielona Góra, Poland (e-mail: [email protected])
ZSOLT TUZA
Affiliation:
Computer and Automation Institute, Hungarian Academy of Sciences, H-1111 Budapest, Kende u. 13-17 Department of Computer Science, University of Veszprém, H-8200 Veszprém, Egyetem u. 10, Hungary (e-mail: [email protected])

Abstract

In this paper we consider a bipartite version of Schütte's well-known tournament problem. A bipartite tournament $T=(A,B,E)$ with teams $A$ and $B$, and set of arcs $E$, has the property $S_{k,l}$ if for any subsets $K\subseteq A$ and $L\subseteq B$, with $|K| =k$ and $| L | =l$, there exist conquerors of $K$ and $L$ in opposite teams. The task is to estimate, for fixed $k$ and $l$, the minimum number $f(k,l)=| A | + | B | $ of players in a tournament satisfying property $S_{k,l}$. We achieve this goal by reformulating the problem in terms of intersecting set families and applying probabilistic as well as constructive methods. Intriguing connections with some famous problems of this area have emerged in this way, leading to new open questions.

Type
Paper
Copyright
2003 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)