Schttes Tournament Problem and Intersecting Families of Sets

Autor:	Mieczysław Borowiecki, Zsolt Tuza, Mariusz Hałuszczak, Jarosław Grytczuk
Rok vydání:	2003
Předmět:	Statistics and Probability Discrete mathematics Property (philosophy) Applied Mathematics Probabilistic logic Constructive Theoretical Computer Science Task (project management) Set (abstract data type) Combinatorics Computational Theory and Mathematics Bipartite graph Tournament Mathematics
Zdroj:	Combinatorics, Probability and Computing. 12:359-364
ISSN:	1469-2163 0963-5483
DOI:	10.1017/s0963548303005674
Popis:	In this paper we consider a bipartite version of Schutte'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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::5b02e3711c1c55aceb18fe11e503859d https://doi.org/10.1017/s0963548303005674 Zobrazit plný text záznamu