On a lemma of Scarf. (Q1403911)

From MaRDI portal
Revision as of 04:13, 5 March 2024 by Import240304020342 (talk | contribs) (Set profile property.)
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
    0 references
    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
    0 references
    fractional kernels in a digraph
    0 references
    Gale-Shapley theorem
    0 references
    hypergraphs
    0 references
    partial orders
    0 references