BZPEER

preprint2022arXiv

Fractionally balanced hypergraphs and rainbow KKM theorems

A d-partite hypergraph is called *fractionally balanced* if there exists a non-negative, not identically zero, function on its edge set that has constant degrees in each vertex side. Using a topological version of Hall's theorem we prove lower bounds on the matching number of such hypergraphs. These bounds yield rainbow versions of the KKM theorem for products of simplices, which in turn are used to obtain some results on multiple-cake division, and on rainbow matchings in families of d-intervals.

preprint2022arXiv

Strongly maximal matchings and strongly minimal covers

This is a not-to-be-journal-published paper, aimed to serve as reference. It is a summary of the main ideas on the topic appearing in the title, and an opportunity to state correctly the main conjecture in the field.

preprint2021arXiv

Badges and rainbow matchings

Drisko proved that $2n-1$ matchings of size $n$ in a bipartite graph have a rainbow matching of size $n$ . For general graphs it is conjectured that $2n$ matchings suffice for this purpose (and that $2n-1$ matchings suffice when $n$ is even). The known graphs showing sharpness of this conjecture for $n$ even are called badges. We improve the previously best known bound from $3n-2$ to $3n-3$ , using a new line of proof that involves analysis of the appearance of badges. We also prove a "cooperative" generalization: for $t>0$ and $n \geq 3$ , any $3n-4+t$ sets of edges, the union of every $t$ of which contains a matching of size $n$ , have a rainbow matching of size $n$ .

preprint2020arXiv

A rainbow version of Mantel's Theorem

Mantel's Theorem asserts that a simple $n$ vertex graph with more than $\frac{1}{4}n^2$ edges has a triangle (three mutually adjacent vertices). Here we consider a rainbow variant of this problem. We prove that whenever $G_1, G_2, G_3$ are simple graphs on a common set of $n$ vertices and $|E(G_i)| > ( \frac{ 26 - 2 \sqrt{7} }{81})n^2 \approx 0.2557 n^2$ for $1 \le i \le 3$ , then there exist distinct vertices $v_1,v_2,v_3$ so that (working with the indices modulo 3) we have $v_i v_{i+1} \in E(G_i)$ for $1 \le i \le 3$ . We provide an example to show this bound is best possible. This also answers a question of Diwan and Mubayi. We include a new short proof of Mantel's Theorem we obtained as a byproduct.

preprint2020arXiv

Cooperative colorings of trees and of bipartite graphs

Given a system $(G_1, \ldots ,G_m)$ of graphs on the same vertex set $V$ , a cooperative coloring is a choice of vertex sets $I_1, \ldots ,I_m$ , such that $I_j$ is independent in $G_j$ and $\bigcup_{j=1}^{m}I_j = V$ . For a class $\mathcal{G}$ of graphs, let $m_{\mathcal{G}}(d)$ be the minimal $m$ such that every $m$ graphs from $\mathcal{G}$ with maximum degree $d$ have a cooperative coloring. We prove that $Ω(\log\log d) \le m_\mathcal{T}(d) \le O(\log d)$ and $Ω(\log d)\le m_\mathcal{B}(d) \le O(d/\log d)$ , where $\mathcal{T}$ is the class of trees and $\mathcal{B}$ is the class of bipartite graphs.

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

A rainbow $r$ -partite version of the Erdős-Ko-Rado theorem

Let $f(n,r,k)$ be the minimal number such that every hypergraph larger than $f(n,r,k)$ contained in $\binom{[n]}{r}$ contains a matching of size $k$ , and let $g(n,r,k)$ be the minimal number such that every hypergraph larger than $g(n,r,k)$ contained in the $r$ -partite $r$ -graph $[n]^{r}$ contains a matching of size $k$ . The Erdős-Ko-Rado theorem states that $f(n,r,2)=\binom{n-1}{r-1}$ ~~( $r \le \frac{n}{2}$ ) and it is easy to show that $g(n,r,k)=(k-1)n^{r-1}$ . The conjecture inspiring this paper is that if $F_1,F_2,\ldots,F_k\subseteq \binom{[n]}{r}$ are of size larger than $f(n,r,k)$ or $F_1,F_2,\ldots,F_k\subseteq [n]^{r}$ are of size larger than $g(n,r,k)$ then there exists a rainbow matching, i.e. a choice of disjoint edges $f_i \in F_i$ . In this paper we deal mainly with the second part of the conjecture, and prove it for $r\le 3$ . \vspace{.1cm} We also prove that for every $r$ and $k$ there exists $n_0=n_0(r,k)$ such that the $r$ -partite version of the conjecture is true for $n>n_0$ .

preprint2016arXiv

Cross-intersecting pairs of hypergraphs

Two hypergraphs $H_1,\ H_2$ are called {\em cross-intersecting} if $e_1 \cap e_2 \neq \emptyset$ for every pair of edges $e_1 \in H_1,~e_2 \in H_2$ . Each of the hypergraphs is then said to {\em block} the other. Given parameters $n,r,m$ we determine the maximal size of a sub-hypergraph of $[n]^r$ (meaning that it is $r$ -partite, with all sides of size $n$ ) for which there exists a blocking sub-hypergraph of $[n]^r$ of size $m$ . The answer involves a fractal-like (that is, self-similar) sequence, first studied by Knuth. We also study the same question with $\binom{n}{r}$ replacing $[n]^r$ .

preprint2016arXiv

Degree conditions for matchability in $3$ -partite hypergraphs

We study conjectures relating degree conditions in $3$ -partite hypergraphs to the matching number of the hypergraph, and use topological methods to prove special cases. In particular, we prove a strong version of a theorem of Drisko \cite{drisko} (as generalized by the first two authors \cite{ab}), that every family of $2n-1$ matchings of size $n$ in a bipartite graph has a partial rainbow matching of size $n$ . We show that milder restrictions on the sizes of the matchings suffice. Another result that is strengthened is a theorem of Cameron and Wanless \cite{CamWan}, that every Latin square has a diagonal (permutation submatrix) in which no symbol appears more than twice. We show that the same is true under the weaker condition that the square is row-Latin.

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.

preprint2016arXiv

Fair representation by independent sets

For a hypergraph $H$ let $β(H)$ denote the minimal number of edges from $H$ covering $V(H)$ . An edge $S$ of $H$ is said to represent {\em fairly} (resp. {\em almost fairly}) a partition $(V_1,V_2, \ldots, V_m)$ of $V(H)$ if $|S\cap V_i|\ge \lfloor\frac{|V_i|}{β(H)}\rfloor$ (resp. $|S\cap V_i|\ge \lfloor\frac{|V_i|}{β(H)}\rfloor-1$ ) for all $i \le m$ . In matroids any partition of $V(H)$ can be represented fairly by some independent set. We look for classes of hypergraphs $H$ in which any partition of $V(H)$ can be represented almost fairly by some edge. We show that this is true when $H$ is the set of independent sets in a path, and conjecture that it is true when $H$ is the set of matchings in $K_{n,n}$ . We prove that partitions of $E(K_{n,n})$ into three sets can be represented almost fairly. The methods of proofs are topological.

preprint2016arXiv

Independent sets in the union of two Hamiltonian cycles

Motivated by a question on the maximal number of vertex disjoint Schrijver graphs in the Kneser graph, we investigate the following function, denoted by $f(n,k)$ : the maximal number of Hamiltonian cycles on an $n$ element set, such that no two cycles share a common independent set of size more than $k$ . We shall mainly be interested in the behavior of $f(n,k)$ when $k$ is a linear function of $n$ , namely $k=cn$ . We show a threshold phenomenon: there exists a constant $c_t$ such that for $c<c_t$ , $f(n,cn)$ is bounded by a constant depending only on $c$ and not on $n$ , and for $c_t <c$ , $f(n,cn)$ is exponentially large in $n ~(n \to \infty)$ . We prove that $0.26 < c_t < 0.36$ , but the exact value of $c_t$ is not determined. For the lower bound we prove a technical lemma, which for graphs that are the union of two Hamiltonian cycles establishes a relation between the independence number and the number of $K_4$ subgraphs. A corollary of this lemma is that if a graph $G$ on $n>12$ vertices is the union of two Hamiltonian cycles and $α(G)=n/4$ , then $V(G)$ can be covered by vertex-disjoint $K_4$ subgraphs.

preprint2016arXiv

On a conjecture of Stein

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- \frac{1}{e})n$ . Using a topological version of Hall's theorem we improve this bound to $\frac{2}{3}n$ .

preprint2015arXiv

Covers in Partitioned Intersecting Hypergraphs

Given an integer $r$ and a vector $\vec{a}=(a_1, \ldots ,a_p)$ of positive numbers with $\sum_{i \le p} a_i=r$ , an $r$ -uniform hypergraph $H$ is said to be $\vec{a}$ -partitioned if $V(H)=\bigcup_{i \le p}V_i$ , where the sets $V_i$ are disjoint, and $|e \cap V_i|=a_i$ for all $e \in H,~~i \le p$ . A $\vec{1}$ -partitioned hypergraph is said to be $r$ -partite. Let $t(\vec{a})$ be the maximum, over all intersecting $\vec{a}$ -partitioned hypergraphs $H$ , of the minimal size of a cover of $H$ . A famous conjecture of Ryser is that $t(\vec{1})\le r-1$ . Tuza conjectured that if $r>2$ then $t(\vec{a})=r$ for every two components vector $\vec{a}=(a,b)$ . We prove this conjecture whenever $a\neq b$ , and also for $\vec{a}=(2,2)$ and $\vec{a}=(4,4)$ .

preprint2015arXiv

Multipartite hypergraphs achieving equality in Ryser's conjecture

A famous conjecture of Ryser is that in an $r$ -partite hypergraph the covering number is at most $r-1$ times the matching number. If true, this is known to be sharp for $r$ for which there exists a projective plane of order $r-1$ . We show that the conjecture, if true, is also sharp for the smallest previously open value, namely $r=7$ . For $r\in\{6,7\}$ , we find the minimal number $f(r)$ of edges in an intersecting $r$ -partite hypergraph that has covering number at least $r-1$ . We find that $f(r)$ is achieved only by linear hypergraphs for $r\le5$ , but that this is not the case for $r\in\{6,7\}$ . We also improve the general lower bound on $f(r)$ , showing that $f(r)\ge 3.052r+O(1)$ . We show that a stronger form of Ryser's conjecture that was used to prove the $r=3$ case fails for all $r>3$ . We also prove a fractional version of the following stronger form of Ryser's conjecture: in an $r$ -partite hypergraph there exists a set $S$ of size at most $r-1$ , contained either in one side of the hypergraph or in an edge, whose removal reduces the matching number by 1.

preprint2015arXiv

Rainbow sets in the intersection of two matroids

Given sets $F_1, \ldots ,F_n$ , a {\em partial rainbow function} is a partial choice function of the sets $F_i$ . A {\em partial rainbow set} is the range of a partial rainbow function. Aharoni and Berger \cite{AhBer} conjectured that if $M$ and $N$ are matroids on the same ground set, and $F_1, \ldots ,F_n$ are pairwise disjoint sets of size $n$ belonging to $M \cap N$ , then there exists a rainbow set of size $n-1$ belonging to $M \cap N$ . Following an idea of Woolbright and Brower-de Vries-Wieringa, we prove that there exists such a rainbow set of size at least $n-\sqrt{n}$ .

preprint2015arXiv

Uniqueness of the extreme cases in theorems of Drisko and Erdős-Ginzburg-Ziv

Drisko \cite{drisko} proved (essentially) that every family of $2n-1$ matchings of size $n$ in a bipartite graph possesses a partial rainbow matching of size $n$ . In \cite{bgs} this was generalized as follows: Any $\lfloor \frac{k+2}{k+1} n \rfloor -(k+1)$ matchings of size $n$ in a bipartite graph have a rainbow matching of size $n-k$ . We extend this latter result to matchings of not necessarily equal cardinalities. Settling a conjecture of Drisko, we characterize those families of $2n-2$ matchings of size $n$ in a bipartite graph that do not possess a rainbow matching of size $n$ . Combining this with an idea of Alon \cite{alon}, we re-prove a characterization of the extreme case in a well-known theorem of Erdős-Ginzburg-Ziv in additive number theory.

preprint2014arXiv

Fractional covers and matchings in families of weighted $d$ -intervals

A $d$ -{\em interval} is a union of at most $d$ disjoint closed intervals on a fixed line. Tardos [Combinatorica 15 (1995), 123-134] and the second author [Disc. Comput. Geom. 18 (1997), 195-203] used topological tools to bound the transversal number $τ$ of a family $H$ of $d$ -intervals in terms of $d$ and the matching number $ν$ of $H$ . We investigate the weighted and fractional versions of this problem and prove upper bounds that are tight up to constant factors. We apply both the topological method and an approach of Alon [Disc. Comput. Geom. 19 (1998), 333-334]. For the use of the latter, we prove a weighted version of Turán's theorem. We also provide a proof of the second author's upper bound that is more direct than the original proof.

preprint2013arXiv

A weak version of Rota's basis conjecture for odd dimensions

The Alon-Tarsi Latin square conjecture is extended to odd dimensions by stating it for reduced Latin squares (Latin squares having the identity permutation as their first row and first column). A modified version of Onn's colorful determinantal identity is used to show how the validity of this conjecture implies a weak version of Rota's basis conjecture for odd dimensions, namely that a set of $n$ bases in $\mathbb{R}^n$ has $n-1$ disjoint independent transversals.

preprint2013arXiv

On a Generalization of the Ryser-Brualdi-Stein Conjecture

A rainbow matching for (not necessarily distinct) sets F_1,...,F_k of hypergraph edges is a matching consisting of k edges, one from each F_i. The aim of the paper is twofold - to put order in the multitude of conjectures that relate to this concept (some of them first presented here), and to present some partial results on one of these conjectures, that seems central among them.

Ron Aharoni

Research overview

Is this your work?

20 publications

Fractionally balanced hypergraphs and rainbow KKM theorems

Strongly maximal matchings and strongly minimal covers

Badges and rainbow matchings

A rainbow version of Mantel's Theorem

Cooperative colorings of trees and of bipartite graphs

Rainbow fractional matchings

A rainbow $r$ -partite version of the Erdős-Ko-Rado theorem

Cross-intersecting pairs of hypergraphs

Degree conditions for matchability in $3$ -partite hypergraphs

Edge-covers in d-interval hypergraphs

Fair representation by independent sets

Independent sets in the union of two Hamiltonian cycles

On a conjecture of Stein

Covers in Partitioned Intersecting Hypergraphs

Multipartite hypergraphs achieving equality in Ryser's conjecture

Rainbow sets in the intersection of two matroids

Uniqueness of the extreme cases in theorems of Drisko and Erdős-Ginzburg-Ziv

Fractional covers and matchings in families of weighted $d$ -intervals

A weak version of Rota's basis conjecture for odd dimensions

On a Generalization of the Ryser-Brualdi-Stein Conjecture

See the researcher in context

Building this map preview

Ron Aharoni

Research overview

Is this your work?

20 publications

Fractionally balanced hypergraphs and rainbow KKM theorems

Strongly maximal matchings and strongly minimal covers

Badges and rainbow matchings

A rainbow version of Mantel's Theorem

Cooperative colorings of trees and of bipartite graphs

Rainbow fractional matchings

A rainbow rrr-partite version of the Erdős-Ko-Rado theorem

Cross-intersecting pairs of hypergraphs

Degree conditions for matchability in 333-partite hypergraphs

Edge-covers in d-interval hypergraphs

Fair representation by independent sets

Independent sets in the union of two Hamiltonian cycles

On a conjecture of Stein

Covers in Partitioned Intersecting Hypergraphs

Multipartite hypergraphs achieving equality in Ryser's conjecture

Rainbow sets in the intersection of two matroids

Uniqueness of the extreme cases in theorems of Drisko and Erdős-Ginzburg-Ziv

Fractional covers and matchings in families of weighted ddd-intervals

A weak version of Rota's basis conjecture for odd dimensions

On a Generalization of the Ryser-Brualdi-Stein Conjecture

See the researcher in context

Building this map preview

A rainbow $r$ -partite version of the Erdős-Ko-Rado theorem

Degree conditions for matchability in $3$ -partite hypergraphs

Fractional covers and matchings in families of weighted $d$ -intervals