On a conjecture of Stein

DOI10.1007/S12188-016-0160-3MaRDI QIDQ1688259zbMATH OpenOpenAlexWikidataFDO

Authors Ron Aharoni, Eli Berger, Dani Kotlar, Ran Ziv

Publication date 5 January 2018

Published in Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1605.01982

zbMATH Keywords

rainbow matchingsRyser's Latin square conjecturetransversals

Mathematics Subject Classification ID

Orthogonal arrays, Latin squares, Room squares (05B15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Extremal set theory (05D05) Transversal (matching) theory (05D15)

Abstract: Stein proposed the following conjecture: if the edge set of $K_{n,n}$ is partitioned into $n$ sets, each of size $n$, then there is a partial rainbow matching of size $n-1$. He proved that there is a partial rainbow matching of size $n(1-frac{D}_{n}n!)$, where $D_n$ is the number of derangements of $[n]$. This means that there is a partial rainbow matching of size about $(1-frac1e)n$. Using a topological version of Hall's theorem we improve this bound to $frac23n$.

Recommendations

• On rainbow matchings in bipartite graphs
• Topological methods for the existence of a rainbow matching
• On a generalization of the Ryser-Brualdi-Stein conjecture
• Rainbow matchings in r-partite r-graphs
• Large matchings in bipartite graphs have a rainbow matching

Cites work

• A condition for matchability in hypergraphs
• A lower bound for the length of a partial transversal in a Latin square
• A lower bound for the length of a partial transversal in a Latin square
• A lower bound for the order of a partial transversal in a latin square
• An n n Latin square has a transversal with at least n- n distinct symbols
• Chessboard Complexes and Matching Complexes
• Combinatorial matrix theory
• Complete Subgraphs of r-partite Graphs
• Domination numbers and homology
• Eigenvalues of \(K_{1,k}\)-free graphs and the connectivity of their independence complexes
• Fair representation by independent sets
• Hall's theorem for hypergraphs
• Independent systems of representatives in weighted graphs
• Independent transversals in \(r\)-partite graphs
• On a lower bound for the connectivity of the independence complex of a graph
• The clique complex and hypergraph matching
• Top homology of hypergraph matching complexes, p-cycle complexes and Quillen complexes of symmetric groups.
• Transversals of latin squares and their generalizations

Cited in

(16)

• Topological methods for the existence of a rainbow matching
• A Stein conjecture for the circle
• On a generalization of the Ryser-Brualdi-Stein conjecture
• On a conjecture of E. M. Stein on the Hilbert transform on vector fields
• scientific article; zbMATH DE number 5548551 (Why is no real title available?)
• On a Problem of Stein Concerning Infinite Covers
• A proof of the conjecture of Mazur-Rubin-Stein
• New bounds for Ryser’s conjecture and related problems
• On rainbow matchings in bipartite graphs
• Rainbow structures in locally bounded colorings of graphs
• A counterexample to Stein's equi-\(n\)-square conjecture
• On a Stein And Weiss Property of the Conjugate Function
• Colorful Matchings
• Fairness in temporal slot assignment
• Bounded degree graphs and hypergraphs with no full rainbow matchings
• A note on finding large transversals efficiently

This page was built for publication: On a conjecture of Stein

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1688259)