An infinite version of Ryser's inequality
type: Item
instance of: scholarly article
title: An infinite version of Ryser's inequality
zbMATH Open document ID: 0612.05005
DOI: 10.1016/0097-3165(86)90071-3
author: Péter Komjáth
published in: Journal of Combinatorial Theory. Series A
publication date: 1986-01-01T00:00:00Z
review text: The following conjecture of R. Aharoni (1984), generalizing Ryser's inequality, is known: If r is a natural number, \(H\neq \{\emptyset \}\) is a system of sets, and \(| A\cap B| =r\) for any two sets A,B in H, then H has the transversal property, i.e. it has a one-to-one choice function. The author proves the conjecture using the axiom of choice. Also the following assertion (in author's terminology ''claim'') is proved: The number of sets of type II is finite for \(\beta\) finite, and is at most \(\beta\) if \(\beta\) is infinite. Here a number \(A\in H\) is called of type I if \(A\supseteq X\) and of type II otherwise, \(X=A_ 0\cap A_ 1\), where \(A_ 0\) is a smallest member of H and \(A_ 1\) is a smallest member of \(H-\{A_ 0\}:\beta =| A_ 1-X|\).
Mathematics Subject Classification ID: 05A05
Mathematics Subject Classification ID: 05A19
zbMATH DE Number: 3989349
zbMATH Keywords: Ryser's inequality
zbMATH Keywords: axiom of choice
MaRDI profile type: Publication
full work available at URL: 0097-3165(86)90071-3
OpenAlex ID: W2010520169
cites work: König's Duality Theorem for Infinite Bipartite Graphs
cites work: Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas
cites work: An extension of a theorem of the Bruijn and Erdős on combinatorial designs
description: scientific article; zbMATH DE number 3989349