| Autor: |
Bousquet, N., Lochet, W., Thomass��, S. |
| Rok vydání: |
2017 |
| Předmět: |
|
| DOI: |
10.48550/arxiv.1703.08123 |
| Popis: |
A very nice result of B��r��ny and Lehel asserts that every finite subset $X$ or $\mathbb R^d$ can be covered by $f(d)$ $X$-boxes (i.e. each box has two antipodal points in $X$). As shown by Gy��rf��s and P��lv��lgyi this result would follow from the following conjecture : If a tournament admits a partition of its arc set into $k$ quasi orders, then its domination number is bounded in terms of $k$. This question is in turn implied by the Erd��s-Sands-Sauer-Woodrow conjecture : If the arcs of a tournament $T$ are colored with $k$ colors, there is a set $X$ of at most $g(k)$ vertices such that for every vertex $v$ of $T$, there is a monochromatic path from $X$ to $v$. We give a short proof of this statement. We moreover show that the general Sands-Sauer-Woodrow conjecture (which as a special case implies the stable marriage theorem) is valid for directed graphs with bounded stability number. This conjecture remains however open. |
| Databáze: |
OpenAIRE |
| Externí odkaz: |
|
