Source author record

Ron Holzman

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

2works

1topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2019arXiv

Rainbow fractional matchings

We prove that any family $E_1, \ldots , E_{\lceil rn \rceil}$ of (not necessarily distinct) sets of edges in an $r$ -uniform hypergraph, each having a fractional matching of size $n$ , has a rainbow fractional matching of size $n$ (that is, a set of edges from distinct $E_i$ 's which supports such a fractional matching). When the hypergraph is $r$ -partite and $n$ is an integer, the number of sets needed goes down from $rn$ to $rn-r+1$ . The problem solved here is a fractional version of the corresponding problem about rainbow matchings, which was solved by Drisko and by Aharoni and Berger in the case of bipartite graphs, but is open for general graphs as well as for $r$ -partite hypergraphs with $r>2$ . Our topological proof is based on a result of Kalai and Meshulam about a simplicial complex and a matroid on the same vertex set.

preprint2016arXiv

Edge-covers in d-interval hypergraphs

A d-interval hypergraph has d disjoint copies of the unit interval as its vertex set, and each edge is the union of d subintervals, one on each copy. Extending a classical result of Gallai on the case d = 1, Tardos and Kaiser used topological tools to bound the ratio between the transversal number and the matching number in such hypergraphs. We take a dual point of view, and bound the edge-covering number (namely the minimal number of edges covering the entire vertex set) in terms of a parameter expressing independence of systems of partitions of the d unit intervals. The main tool we use is an extension of the KKM theorem to products of simplices, due to Peleg. Our approach also yields a new proof of the Tardos-Kaiser result.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.