On a lemma of Scarf. (Q1403911)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On a lemma of Scarf. |
scientific article |
Statements
On a lemma of Scarf. (English)
0 references
20 August 2003
0 references
In a 1998 paper, \textit{R. Aharoni} and \textit{R. Holzman} [J. Comb. Theory, Ser. B 73, No. 1, 1--6 (1998; Zbl 0904.05036)] have applied Scarf's lemma in order to prove the existence of fractional kernels in a digraph not containing cyclic triangles. In this paper, the authors give some other possibilities of applying this lemma in combinatorics, namely they obtain some nice theorems: 1. A fractional version of the Gale-Shapley theorem for hypergraphs. 2. Given a family of partial orders on the same underlying set, there exists a system of weights on the vertices, which is fractionally independent in all orders, and each vertex is dominated by them in one of the orders.
0 references
fractional kernels in a digraph
0 references
Gale-Shapley theorem
0 references
hypergraphs
0 references
partial orders
0 references