×

On a lemma of Scarf. (English) Zbl 1058.05031

In a 1998 paper, R. Aharoni and 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.

MSC:

05C20 Directed graphs (digraphs), tournaments
05C65 Hypergraphs

Citations:

Zbl 0904.05036
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R. Aharoni, T. Fleiner, On a lemma of Scarf, EGRES Technical Report TR-2001-15,; R. Aharoni, T. Fleiner, On a lemma of Scarf, EGRES Technical Report TR-2001-15, · Zbl 1049.90070
[2] Aharoni, R.; Holzman, R., Fractional kernels in digraphs, J. Combin. Theory Ser. B, 73, 1, 1-6 (1998) · Zbl 0904.05036
[3] T. Fleiner, A fixed-point approach to stable matchings and some applications, to appear in Math. Oper. Res.; T. Fleiner, A fixed-point approach to stable matchings and some applications, to appear in Math. Oper. Res. · Zbl 1082.90096
[4] T. Fleiner, Stable and crossing structures, August, 2000, Ph.D. Dissertation,; T. Fleiner, Stable and crossing structures, August, 2000, Ph.D. Dissertation, · Zbl 0966.91007
[5] Gale, D.; Shapley, L. S., College admissions and stability of marriage, Amer. Math. Monthly, 69, l, 9-15 (1962) · Zbl 0109.24403
[6] Irving, R. W., An efficient algorithm for the “stable roommates” problem, J. Algorithms, 6, 4, 577-595 (1985) · Zbl 0581.05001
[7] Lovász, L., Matroids and Sperner’s lemma, European J. Combin., 1, 1, 65-66 (1980) · Zbl 0443.05025
[8] Balinski, M. L., Integer programming: methods, uses, computation, Management Sci., 12, 253-313 (1965) · Zbl 0129.12004
[9] Shapley, L. S., On balanced games without side payments, (Hu, T. C.; Robinson, S. M., Mathematical Programming (1973), Academic Press: Academic Press NY), 261-290 · Zbl 0267.90100
[10] Sands, B.; Sauer, N.; Woodrow, R., On monochromatic paths in edge-coloured digraphs, J. Combin. Theory Ser. B, 33, 3, 271-275 (1982) · Zbl 0488.05036
[11] Scarf, H. E., The core of an \(N\) person game, Econometrica, 35, 50-69 (1967) · Zbl 0183.24003
[12] Tan, J. J.M., A necessary and sufficient condition for the existence of a complete stable matching, J. Algorithms, 12, 1, 154-178 (1991) · Zbl 0715.68069
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.