Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-09T15:32:12.586Z 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: M.Borowiecki@im.uz.zgora.pl)
JAROSŁAW GRYTCZUK
Affiliation:
Institute of Mathematics, University of Zielona Góra, 65-246 Zielona Góra, Poland (e-mail: J.Grytczuk@im.uz.zgora.pl)
MARIUSZ HAŁUSZCZAK
Affiliation:
Institute of Mathematics, University of Zielona Góra, 65-246 Zielona Góra, Poland (e-mail: M.Haluszczak@im.uz.zgora.pl)
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: tuza@sztaki.hu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Paper
Copyright
2003 Cambridge University Press