% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages \usepackage{amsthm,amsmath,amssymb} % we recommend the graphicx package for importing figures \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins % declare theorem-like environments \theoremstyle{plain} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \newtheorem{assertion}[theorem]{Assertion} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} \newcommand{\M}{\mathcal{M}} \newcommand{\re}{\mathbb R} \newcommand{\pf}{{\bf Proof}:~} \newcommand{\cig}{{\mathcal I}(G)} \newcommand{\cilj}{{\mathcal I}(L(J))} \newcommand{\ca}{\mathcal A} \newcommand{\cb}{\mathcal B} \newcommand{\cf}{\mathcal F} %\newcommand{\cm}{\mathcal M} \newcommand{\cn}{\mathcal N} \newcommand{\cm}{\mathcal M} \newcommand{\cp}{\mathcal P} \newcommand{\ce}{\mathcal E} \newcommand{\cx}{\mathcal X} \newcommand{\cv}{\mathcal V} \newcommand{\cq}{\mathcal Q} \newcommand{\cy}{\mathcal Y} \newcommand{\ck}{\mathcal K} \newcommand{\cz}{\mathcal Z} \newcommand{\cw}{\mathcal W} \newcommand{\cs}{\mathcal S} \newcommand{\ct}{\mathcal T} \newcommand{\cC}{\mathcal C} \newcommand{\enp}{\hfill \Box} \newcommand{\tn}{\tilde{N}} %\newcommand{\prf}{Proof:~} \newcommand{\ch}{\mathcal H} \newcommand{\ci}{\mathcal I} \newcommand{\cu}{\mathcal U} \newcommand{\cd}{\mathcal D} %\newcommand{\cb}{\mathcal B} \newcommand{\etabar}{\overline{\eta}} \newcommand{\heta}{\hat{\eta}} \newcommand{\tg}{\tilde{\gamma}} \newcommand{\ttau}{\tilde{\tau}} \newcommand{\rn}{\mathbb{R}^n} \newcommand{\vxu}{\vec{x}(u)} \newcommand{\vxv}{\vec{x}(v)} \newcommand{\vx}{\vec{x}} \newcommand{\gi}{\gamma i} \newcommand{\ig}{i\gamma} \newcommand{\mR}{\mathbb{R}} \newcommand{\x}{\vec{x}} \newcommand{\y}{\vec{y}} \newcommand{\z}{\vec{z}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf Fair representation\\in the intersection of two matroids} % input author, affiliation, address and support information as follows; % the address should include the country, and does not have to include % the street address \author{Ron Aharoni\\ \small Department of Mathematics\\[-0.8ex] \small Technion\\[-0.8ex] \small Haifa, Israel\\ \small\tt raharoni@gmail.com\\ \and Eli Berger\\ \small Department of Mathematics\\[-0.8ex] \small Haifa University\\[-0.8ex] \small Haifa, Israel\\ \small\tt berger.haifa@gmail.com\\ \and Dani Kotlar \qquad Ran Ziv\\ \small Department of Computer Science\\[-0.8ex] \small Tel-Hai College\\[-0.8ex] \small Upper Galilee, Israel\\ \small\tt \{dannykot,ranziv\}@telhai.ac.il } % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} %\date{\dateline{Jan 1, 2012}{Jan 2, 2012}\\ %\small Mathematics Subject Classifications: 05C88, 05C89} \begin{document} \maketitle % E-JC papers must include an abstract. The abstract should consist of a % succinct statement of background followed by a listing of the % principal new results that are to be found in the paper. The abstract % should be informative, clear, and as complete as possible. Phrases % like "we investigate..." or "we study..." should be kept to a minimum % in favor of "we prove that..." or "we show that...". Do not % include equation numbers, unexpanded citations (such as "[23]"), or % any other references to things in the paper that are not defined in % the abstract. The abstract will be distributed without the rest of the % paper so it must be entirely self-contained. \begin{abstract} Mysteriously, hypergraphs that are the intersection of two matroids behave in some respects almost as well as one matroid. In the present paper we study one such phenomenon - the surprising ability of the intersection of two matroids to fairly represent the parts of a given partition of the ground set. For a simplicial complex $\cC$ denote by $\beta(\cC)$ the minimal number of edges from $\cC$ needed to cover the ground set. If $\cC$ is a matroid then for every partition $A_1, \ldots, A_m$ of the ground set there exists a set $S \in \cC$ meeting each $A_i$ in at least $\lfloor \frac{|A_i|}{\beta(\cC)}\rfloor$ elements. We conjecture that a slightly weaker result is true for the intersection of two matroids: if $\cd=\cp \cap \cq$, where $\cp,\cq$ are matroids on the same ground set $V$ and $\beta(\cp), \beta(\cq) \le k$, then for every partition $A_1, \ldots, A_m$ of the ground set there exists a set $S \in \cd$ meeting each $A_i$ in at least $\frac{1}{k}|A_i|-1$ elements. We prove that if $m=2$ (meaning that the partition is into two sets) there is a set belonging to $\cd$ meeting each $A_i$ in at least $(\frac{1}{k}-\frac{1}{|V|})|A_i|-1$ elements. % keywords are optional \bigskip\noindent \textbf{Keywords:} dimatroid; fair representation. \end{abstract} \section{The unreasonably good behavior of the intersection of two matroids} \subsection{Some terminology}A hypergraph $\cC$ is called a {\em simplicial complex} (or just a ``complex'') if it is closed down, namely $e \in \cC$ and $f \subseteq e$ imply $f \in \cC$. A complex is called a {\em matroid} if all its maximal sets are of the same size, and this is true also for each of its induced hypergraphs. We denote by $rank(\cC)$ the maximal size of an edge in $\cC$. Also define $\zeta(\cC)=\max_{S \subseteq V(\cC)} \frac{|S|}{rank(\cC[S])} $ (here $\cC[S]$ is the set of edges of $\cC$ contained in $S$). \begin{definition} An {\em edge-cover} (or plainly a {\em cover}) of a complex $\cC$ is a collection of edges whose union is $V(\cC)$. The minimal size of an edge cover is denoted by $\beta(\cC)$, and is called the {\em edge covering number} of $\cC$. A {\em fractional cover} of the vertices of a hypergraph $\cC$ by edges is a function $f:E(\cC) \to \mR^+$ satisfying $\sum_{v\in A \in \cC}f(A) \ge 1$ for all $v\in V(\cC)$. Let $\beta^*(\cC)=\min \sum_{A \in \cC} f(A)$, where $f$ ranges over all fractional covers of vertices by edges in $\cC$. \end{definition} \begin{remark} In the literature $\beta(\cC)$ is sometimes denoted by $\rho(\cC)$, but in the context of matroids this may generate confusion, since $\rho$ often denotes ``rank''. \end{remark} Clearly, $\beta(\cC)\ge \zeta(\cC)$. A well known theorem of Edmonds \cite{edmondsdec} is: \begin{theorem}\label{edmonds} If $\cp$ is a matroid then $\beta(\cp)=\lceil\zeta(\cp)\rceil$. \end{theorem} This can be used to show: \begin{theorem} If $\cp$ is a matroid then $\beta^*(\cp)=\zeta(\cp)$. \end{theorem} If $\cp$ and $\cq$ are matroids, then $\cp \cap \cq$ is the collection of all sets that are independent in both $\cp$ and $\cq$. We shall use the term {\em dimatroid} for a complex that is the intersection of two matroids. Perhaps the best known example of a dimatroid is the matching complex $\cm(G)$ of a bipartite multigraph $G$. The ground set of this matroid is $E(G)$, and the two respective matroids are partition matroids, one whose parts are the stars in one side of the multigraph, and the other having as parts the stars in the other side of the multigraph. \subsection{Three conjectured properties of dimatroids} Imagine upgrading to business class for just one dollar. This is what seems to happen here. In some respects, going from one matroid to a dimatroid involves only a minute penalty. The intersection of two matroids behaves almost as nicely as one matroid - there is usually a price of just an extra ``1'' in the results. There are at least three aspects to the well-behavedness of dimatroids. {\bf I. The covering number $\beta(\cd)$.} K\"onig's edge coloring theorem is: \begin{theorem}\label{konigc} If $G$ is bipartite then $\beta(\cm(G))=\Delta(G)$. \end{theorem} Note that $\Delta(G)$, the maximal degree of a vertex of $G$, is $\max(\beta(\cp), \beta(\cq))$, where $\cp, \cq$ are the two matroids whose intersection is $\cm(G)$. Thus the theorem states that if $\cp, \cq$ are partition matroids, then $$\beta(\cp \cap \cq)=\max(\beta(\cp), \beta(\cq))$$ Closely related is Vizing's edge coloring theorem. For a graph $H$ let $L(H)$ be the line graph of $H$, namely $V(G)=E(H)$ and $ab \in E(G)$ is $a \cap b \neq \emptyset$ (as edges of $H$). Let $\ci(G)$ be the complex of independent sets in $G$ (so, $\ci(G)=\cm(H)$). Then $\beta(\ci(G))$ is the edge coloring number of $H$. The maximal degree of $G$, $\Delta(G)$, can be as high as $2\Delta(H)-2$, and thus Brooks' theorem yields only $\beta(\ci(G)) \le 2\Delta(H)-1$, yet Vizing's theorem gives $\beta(\ci(G))\le \Delta(H)+1$. The matching complex of a general graph is not a dimatroid, but something very close to it - a $2$-polymatroid (see \cite{lovaszplummer} for a definition). In \cite{matcomp} it was conjectured that for general pairs of matroids the above equality is almost true, with only a price of $1$ to be paid. \begin{conjecture}\cite{matcomp}\label{betaint} If $\cp, \cq$ are matroids on the same ground set then $$\beta(\cp \cap \cq) \le \max(\beta(\cp), \beta(\cq))+1.$$ \end{conjecture} In fact, we do not have a counterexample to the stronger $\beta(\cp \cap \cq) \le \max(\beta(\cp), \beta(\cq)+1).$ A particularly simple example showing the need in the extra $1$ on the right hand side is the intersection of the graphic matroid $\cp$ on $E(K_4)$ and the partition matroid $\cq$ whose three parts are the three perfect matchings in $K_4$, in which $\beta(\cp)=\beta(\cq)=2$, while $\beta(\cp \cap \cq)=3$. In \cite{matcomp} the following was proved: \begin{theorem} $\beta(\cp \cap \cq) \le 2\max(\beta(\cp),\beta(\cq))$. \end{theorem} In \cite{abz} Conjecture \ref{betaint} was proved when $\max(\beta(\cp), \beta(\cq))\le 2$. \begin{definition} Given subsets $S_1, \ldots, S_n$ of a set $V$ and a complex $\cC$ on $V$, a {\em $\cC$-transversal} is a set belonging to $\cC$, consisting of one vertex from each $S_i$. (In particular, the vertices chosen from the sets $S_i$ should be distinct.) %If $\cC$ is a matroid, then the set is called an {\em independent %transversal}. \end{definition} A famous conjecture of Rota \cite{huangrota} is: \begin{conjecture}\label{scrambled} If $B_1, \ldots, B_n$ are independent sets of size $n$ in a matroid $\cm$, then their multiset union is the disjoint union of $n$ $\cm$- transversals. \end{conjecture} Conjecture \ref{scrambled} suggests that even if we scramble the sets $B_i$ – so we no longer have independent sets, but a collection of $n$ sets of size $n$, whose union is decomposable into n independent sets, it is possible to cover their union by $n+1$ $\cm$-transversals. In \cite{ak} examples are given that show that $n+1$ $\cm$-transversals are indeed required in the scrambled case. This shows that if true Conjecture \ref{betaint} is tight for all values of $\max(\beta(\cp),\beta(\cq))$. In \cite{abz} other examples are given demonstrating this fact. A possible strengthening of Conjecture \ref{betaint} is that $\beta(\cp \cap \cq) \le \zeta(\cp \cap \cq)+1=\beta^*(\cp \cap \cq)+1$. This is reminiscent of a famous conjecture of Goldberg and Seymour \cite{seymour,goldberg}, stating that if $G$ is a multigraph then $\beta(\cm(G)) \le \beta^*(\cm(G)) +1$. In fact, the two conjectures have a common generalization, formulated in \cite{abz}. In \cite{matcomp} a fractional version of Conjecture \ref{betaint} was noted (one possible proof is by a standard application of LP duality and a weighted version of Edmonds' two matroids intersection theorem). This result will serve as a main tool in the current paper. \begin{theorem}\label{fracbeta} If $\cp$ and $\cq$ are matroids on the same vertex set then $$\beta^*(\cp \cap \cq) = \max(\zeta(\cp), \zeta(\cq))=\max(\beta^*(\cp), \beta^*(\cq)).$$ \end{theorem} {\bf II. Fair representation.} We say that a set $S$ represents a set $A$ $\alpha$-{\em fairly} (where $\alpha$ is a positive real number) if $|S \cap A| \ge \lfloor \alpha |A| \rfloor$, and that $S$ represents $A$ {\em almost $\alpha$-fairly} if $|S \cap A| \ge \lfloor \alpha |A|\rfloor -1$. A set is said to represent a partition $\ca=(A_1, \ldots ,A_m)$ of $V(\cC)$ (almost) $\alpha$-fairly if it represents all $A_i$'s (almost) $\alpha$-fairly. For every partition, a single matroid $\cm$ contains an independent set that represents the partition $\frac{1}{\beta(\cm)}$-fairly. The following is a rather bold conjecture: \begin{conjecture}\label{bold} If $\cp, \cq$ are matroids on the same ground set $V$, then any partition of $V$ can be represented by an edge of $\cp \cap \cq$ almost $\frac{1}{\max(\beta(\cp),\beta(\cq))}$-fairly. \end{conjecture} This is known (even in a slightly stronger form) for partition matroids with parts of size $2$ \cite{fairrep}– and even this rudimentary case is hard, the proof uses topology. It is known (with a slight weakening) for partitions into two sets.\\ {\bf III. Transversals.} For a complex $\cC$ and a partition $\cv=(V_1, V_2, \ldots, V_m)$ of its vertex set, a {\em $\cC$-transversal} is a choice function from the sets $V_i$, whose range belongs to $\cC$. \begin{conjecture}(Aharoni and Berger, unpublished): A collection of $n$ (not necessarily disjoint) sets, each of size $n+1$ in a dimatroid $\cd$ has a $\cd$-transversal. \end{conjecture} Again, a meager price of $1$ is (conjecturally!) paid, compared with the matroid case (if $\cd$ is a matroid, then size $n$ of each of the sets suffices.) The special case of $\cp, \cq$ being partition matroids (and then $\cp \cap \cq$ is the matching complex of a bipartite multigraph) was first published in \cite{ACH}, and has been studied extensively, with many partial results \cite{ACH, KZ14, cl-eh, Pok1, akz, Pok2}. \section{Fair and almost fair representation} %Given a complex $\cC$ and a set $S$, an edge $A \in \cC$ is said to represent $S$ {\em fairly} (resp. {\em almost fairly}) if $|A %\cap S|\ge \frac{|S|}{\beta)\cC}$ (resp. $|A \cap S|\ge \frac{|S|}{\beta)\cC}-1$. As mentioned above, matroids behave nicely with respect to representation of partitions. Here is a slightly stronger result than mentioned above, with $\zeta$ replacing $\beta$. \begin{theorem}\label{fairmatroid} If $\cp$ is a matroid, then every partition of $V(\cp)$ has a fair $\frac{1}{\zeta(\cp)}$- representation by a set belonging to $\cp$. \end{theorem} This can be be proved, e.g., by Edmonds' two matroids intersection theoerm \cite{edmondsdec}, or using polyhedral methods. It is possible that dimatroids behave almost as nicely with respect to fair representation - with the fairness parameter inherited from their matroid constituents. \begin{conjecture}\label{fairrepintmat} Let $\cp,\cq$ be two matroids on the same ground set $V$, let $\cd=\cp \cap \cq$, and let $\zeta=\max(\zeta(\cp), \zeta(\cq))$. Then any partition of $V$ has an almost $\frac{1}{\zeta}$-fair representation by a set from $\cd$. \end{conjecture} An example showing the necessity of the ``almost fair'' qualification is the matching complex of $C_4$, partitioned into two matchings, $A_1, A_2$. Here $\zeta=2$, so $|A_i|/\zeta=1$, and any matching misses completely one of the $A_i$s, so there is no $1/\zeta$-fair representation. In \cite{fairrep} Conjecture \ref{fairrepintmat} was proved when the dimatroid is the intersection of two partition matroids, each with parts of size $2$. This can be reduced to the case in which the complex is the complex of independent sets of vertices on a path. \begin{theorem}\label{treesconj0} If $P$ is a path and $(A_1, \ldots ,A_m)$ is a partition of its vertex set $V$, then there exists a subset $S$ of $V$ that is independent in $P$ and satisfies: $|S\cap A_i|\ge \frac{|A_i|}{2}-1$ for all $i \le m$. \end{theorem} In \cite{alishaimeunier} a stronger result, conjectured in \cite{fairrep}, was proved. \begin{theorem}\label{treesconj0conj} If $P$ is a path and $(A_1, \ldots ,A_m)$ is a partition of its vertex set $V$, then there exists a subset $S$ of $V$ that is independent in $P$ and satisfies: $|S\cap A_i|\ge \frac{|A_i|}{2}-1$ for all $i \le m$, with strict inequality holding for all but at most $\frac{m}{2}$ sets $A_i$. \end{theorem} The proofs of the above results use Borsuk's theorem. Another case of Conjecture \ref{fairrepintmat} solved in \cite{fairrep} is that in which the dimatroid is the matching complex $\cm(K_{n,n})$, and the partition is into three parts. In \cite{fekszabo} a particular case is studied, where the partition is into two sets, one of the matroids, say $\cp$, is the acyclic (graphic) matroid of a graph, and the other ($\cq$) is its dual - so their intersection is the set of all acyclic sets of edges whose complement contains a spanning tree. In \cite{fekszabo} the following was proved: \begin{theorem} If $G$ is a graph such that $E(G)$ can be partitioned into two spanning trees, then for every set $A \subseteq E(G)$ there exist complementary spanning trees $S,T$ such that $$\mid |E(S) \cap A|-|E(T) \cap A| \mid \le 1.$$ \end{theorem} In our terminology, $E(S)$ is a set that represents the partition $(A,E(G)\setminus A)$ $\frac{1}{2}$-fairly. This type of pairs of matroids yields another example showing that the ``almost'' qualification is needed in Conjecture \ref{fairrepintmat}: \begin{example} Let $\cp$ be the graphic matroid on $E(K_4)$, and let $\cq$ be its dual. Let $(A_1,A_2,A_3)$ be the partition of $E(K_4)$ into three matchings. Then $\zeta(\cp)=\zeta(\cq)=2$, and there is no set in $\cp \cap \cq$ meeting all $A_i$'s. \end{example} In this paper we prove a slightly weaker version of Conjecture \ref{fairrepintmat}, when the partition is into two sets. \begin{theorem}\label{main} Let $\cp,\cq$ be two matroids on the same ground set $V$, and let $\cd=\cp\cap \cq$. Let $n=|V|$, $\zeta=\max(\zeta(\cp), \zeta(\cq))$. Then any partition of $V$ into two sets has an almost $(\frac{1}{\zeta}-\frac{1}{n})$-fair representation by a set from $\cd$. \end{theorem} \section{Proof of Theorem \ref{main}. } For a complex $\cC$ and a positive integer $g$, let $\cC^g=\{A \in \cC \mid |A| \le g\}$. Clearly, if $\cm$ is a matroid then so is $\cm^g$. A main tool we shall use is: \begin{lemma}\label{main:lemma} Let $\cm$ be a matroid with $|V(\cm)|=n,\zeta(\cm)=\zeta$, and let $g$ be an integer not larger than $\frac{n}{\zeta}$. Then $\zeta(\cm^g)=\frac{n}{g}$. \end{lemma} \begin{proof} By the definition of $\zeta$, $\zeta(\cm^g)\ge \frac{n}{rank_{\cm^g}(V)}\ge \frac{n}{g}$. For the other direction, in order to show that $\zeta(\cm^g)\le \frac{n}{g}$ we have to show that for every $S\subseteq V$ it is true that $\frac{|S|}{rank_{\cm^g}(S)}\le \frac{n}{g}$ . That is, we want to show that every subset $S$ of $V$ contains a set $R$ belonging to $\cm$ such that $r=|R|$ satisfies $r\le g$ (so that $R \in \cm^g$) and $r \ge \frac{|S|g}{n}$. By the definition of $\zeta$, there exists a subset $T \in \cm$ of $S$ of size $t\ge \frac{|S|}{\zeta}$, and since $g \le \frac{n}{\zeta}$ we have $t \ge g\frac{|S|}{n}$. Let $r=\lceil g\frac{|S|}{n} \rceil$. Since $t$ is an integer, by the above $t \ge r$, so there exists a subset $R$ of $T$ of size $r$. Since $|S| \le n$ we have $r \le g$, and thus $R$ is the desired set. \end{proof} \begin{lemma}\label{moving} Let $\cp,\cq$ be two matroids, and let $\cd=\cp \cap \cq$. Let $S,T\in\cd$ satisfy $|S|=|T|=g$. Then there exist a sequencing $s_1,\ldots,s_g$ of the elements of $S$ and a sequencing $t_1,\ldots,t_g$ of the elements of $T$ such that $S-s_1+t_1-s_2+\ldots +t_{i-1}-s_i \in \cd$ for all $i=1,\ldots,g$. \end{lemma} \begin{proof} Below we use the common notation $A+x$ for $A \cup\{x\}$ and $A-a$ for $A \setminus \{a\}$. Let $S_1=S-s_1$ for some $s_1\in S$. Since $|T|>|S_1|$, there exists $t_1\in T$ such that $S_1+t_1\in \cp$. If also $S_1+t_1\in \cq$ we continue by choosing $s_2\in S_1$ arbitrarily. Otherwise, we choose any $s_2$ in $C_\cq(S_1,t_1)$, the circuit in $\cq$ contained in $S_1+t_1$. and then $S_1+t_1-s_2\in \cd$. Now, suppose we have obtained a set $S_i=S-s_1+t_1-s_2+\cdots+t_{i-1}-s_i\in\cd$. Since $|S_i|<|T|$ there is an element $t_i\in T$ such that $S_i+t_i\in\cp$. If also $S_i+t_i\in\cq$ we can pick $s_{i+1}$ arbitrarily from $S_i$ and we are done. Otherwise we pick $s_{i+1}\in C_\cq(S_i, t_i)\cap S$ (such an element must exist since $T\in\cq$) and we have $S_i+t_i-s_{i+1}\in\cd$ as required. \end{proof} We can now prove Theorem \ref{main}. Write $\theta$ for $\frac{1}{\zeta}-\frac{1}{n}$. \begin{proof} Let $n=|V|$, $g=\lfloor \frac{n}{\zeta} \rfloor$ and $h=\frac{n}{g}$. Let $n=g\zeta+\psi$, where $\psi <\zeta$. We have \begin{equation}\label{zeta-h} \frac{1}{h}=\frac{g}{n}=\frac{n-\psi}{n\zeta}=\frac{1-\psi/n}{\zeta}>\frac{1}{\zeta}-\frac{1}{n} =\theta. \end{equation} %hence we have $|S\cap A_i|\ge [\frac{1}{\zeta}-\frac{1}{n}]|A_i|-1$. By Theorem \ref{fracbeta} and Lemma~\ref{main:lemma} $\beta^*(\cd^g)=h$. Let $f: \cd^g \to \re$ be a minimal fractional cover. \begin{assertion} All sets in $supp(f)$ have the same size. \end{assertion} We have \begin{equation*} n=\sum_{v \in V}1 \le \sum_{v \in V}\sum_{v\in e \in supp(f)}f(e)= \sum_{e \in supp(f)}f(e)\sum_{v \in e}1=\sum_{e \in supp(f) }f(e)|e|. \end{equation*} Since $\sum_{e\in supp(f)}f(e)=h$, the weighted average of the sizes of the edges in $supp(f)$ is at least $\frac{n}{h}=g$. Since $|e|\le g$ for all $e \in \cd^g$, we must have that $|e|=g$ for all $e \in supp(f)$. \medskip Now, let $(A,B)$ be a partition of $V$. \begin{assertion} There exist a set $S\in supp(f)$ that represents $A$ $\theta$-fairly, and a set $T\in supp(f)$ that represents $B$ $\theta$-fairly. \end{assertion} Let us show the existence of $S$ as in the assertion. Assuming this is not the case, by \eqref{zeta-h} \begin{equation*} \begin{split} |A|=&\sum_{v \in A}1 \le \sum_{v \in A}\sum_{v\in e \in supp(f)}f(e)\\ =& \sum_{e \in supp(f)}f(e)\sum_{v \in e\cap A}1=\sum_{e \in supp(f) }f(e)|e\cap A|\\ <&\sum_{e \in supp(f) }f(e)\theta|A| < \sum_{e \in supp(f) }f(e)\frac{|A|}{h}\\=&|A|, \end{split} \end{equation*} which is a contradiction. If either $S$ or $T$ represents both $A$ and $B$ almost $\theta$-fairly, we are done. Otherwise, since $|S|=|T|$, we can apply Lemma \ref{moving} to obtain a sequence of sets $S=S_0, S_1, \ldots, S_g=T$ in $\cd$, such that $|S_1|=\cdots=|S_{g-1}|=g-1$ and every two adjacent sets in the sequence differ by one element. Now, each set in this sequence must represent at least one of $|A|$ or $|B|$ almost $\theta$-fairly. To see this, suppose $S_i$ does not represent $A$ $\theta$-fairly. We have \begin{equation*} \begin{split} |S_i\cap B|&\ge g-1-|S_i\cap A| > g-1-(\frac{1}{\zeta}-\frac{1}{n})|A|\\ &=g-1-(\frac{1}{\zeta}-\frac{1}{n})(n-|B|) =g-\frac{n}{\zeta}+(\frac{1}{\zeta}-\frac{1}{n})|B|\\ &> (\frac{1}{\zeta}-\frac{1}{n})|B| - 1. \end{split} \end{equation*} Thus, $S_i$ represents $B$ almost $\theta$-fairly. Since adjacent sets in the sequence differ by one element and $S_0$ represent $A$ $\theta$-fairly, it follows that one of the sets in this sequence must represent both $A$ and $B$ almost $\theta$-fairly. \end{proof} {\bf Remark:}~~ Truncating the matroids at $g$ is intended to obtain a fractional cover whose support consists of sets of equal size. There is another natural approach to obtaining this aim, which is to take an arbitrary fractional cover, and balance its support sets. This will require proving the following conjecture, which is of interest on its own: \begin{conjecture} If $\cd$ is a dimatroid and $C,D \in \cd$, then there exist $C', D' \in \cd$ such that $\mid |C'|-|D'|\mid \le 1$ and $C'\cup D' = C \cup D$. \end{conjecture} \subsection{Algorithmic considerations} If the two matroids in Theorem \ref{main} are given by an oracle, then the representing set can be found in polynomial time. This is entailed by the proof of the theorem and the following observation: \begin{observation} If a matroid $\cm$ is given by an oracle, then $\zeta(\cm)$, and hence also $\beta(\cm)$, can be found in polynomial time. Moreover, an optimal fractional cover of the vertices by edges can be found in polynomial time. \end{observation} \begin{proof} Given integers $p,q$, it is possible to determine whether $\zeta(\cm) \le \frac{p}{q}$ using a standard construction (the first use of this trick known to us was in the proof of Edmonds' theorem on covering by independent sets, in \cite{welsh}). Form a bipartite graph, whose one side $A$ consists of $p$ copies of each vertex in $V(\cm)$, and the other side $B$ consists of $q$ disjoint copies of $\cm$. Let $\cn$ be the direct sum of the copies of $\cm$, i.e., $\cn$ is a matroid on $B$, where a set is in $\cn$ if and only if its intersection with each of the $q$ copies of $V(\cm)$ belongs to $\cm$. Connect every vertex in $A$ to all its $q$ copies in $B$. Then $\zeta(\cm) \le \frac{p}{q}$ if and only if there exists a matching in this bipartite graph matching the entire side $A$, whose range in $B$ belongs to $\cn$. Determining whether there is such a matching is polynomial (cf \cite{matroidalgorithm}). Since it is enough to check this for $p, q \le |V(\cm)|$, determining $\zeta(\cm)$ can be done in polynomial time. Once the value of $\zeta(\cm)$ is determined by finding $p,q$ as above with minimal $\frac{p}{q}$, the matching gives rise to a minimum fractional edge cover. \end{proof} \section{A fractional version} A fractional version of the main conjecture is true, in a very general form: for any number of matroids, and partitions into any number of parts. The polytope $P(\cm)$ of a matroid $\cm$ is the set of all vectors $\vec{x}$ on $V=V(\cm)$ satisfying $\x[S]\le rank_{\cm}(S)$ for every subset $S$ of $V$. (Here and below, $\vx[S]$ denotes $\sum_{s \in S}x(s)$.) It is known \cite{edmondsdec} that the vertices of $P(\cm)$ are the characteristic vectors of the edges of $\cm$. \begin{theorem} Let $\cm_1, \ldots \cm_q$ be matroids on the same ground set $V$, and let $k=\max(\beta(\cm_i))$. For every partition $(A_1, A_2, \ldots, A_m)$ of $V$ there exists a vector $\x\in \bigcap P(\cm_i)$ satisfying $\x[A_j]\ge \frac{|A_j|}{k}$ for all $j \le m$. \end{theorem} \begin{proof} Note that by the definition of $k$, we have \begin{equation}\label{bound} rank_{\cm_i}(S)\ge \frac{|S|}{k} \end{equation} for all $i \le q$ and $S \subseteq V$. Consider the linear program $\max \x \cdot \vec{1}$ subject to the conditions: $$\x[S] \le min_{i \le q} (rank_{\cm_i}(S))$$ for every $S \subseteq V$, and $$\x[A_j] \le \frac{|A_j|}{k}$$ for all $j \le m$. The theorem is true for the given partition if and only if this maximum is $\frac{|V|}{k}$. By LP duality the value of the linear program is equal to the minimum of $$\sum_{S \subseteq V}y(S)\min_{j \le q}(rank_{\cm_i}(S)) +\sum_{j \le m}z(j)\frac{|A_j|}{k}$$ over all pairs $(\y, \z)$, where $\y$ is a vector on the subsets $S$ of $V$ and $\z$ is a vector on $[m]$, such that for every $v \in V$ there holds \begin{equation}\label{condition} z(j(v))+\sum_{S \ni v}y(S) \ge 1, \end{equation} where $j(v)$ is the index $j$ such that $v \in A_{j}$. By \eqref{bound} we have: $$\sum_{S \subseteq V}y(S)\min(rank_{\cm_i}(S)) +\sum_{j \le m}z(j)\frac{|A_j|}{k} \ge\sum_{S \subseteq V}y(S)\frac{|S|}{k}+\sum_{j \le m}z(j)\frac{|A_j|}{k}$$ Writing $|S|=\sum_{v \in S}1$, and reversing the order of summation, this is equal to: $$ \frac{1}{k}\sum_{v \in V}\left( \sum_{S \ni v} y(S)+z(j(v)) \right)$$ which, by \eqref{condition}, is at least $\frac{|V|}{k}$. \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % \bibliographystyle{plain} % \bibliography{myBibFile} % If you use BibTeX to create a bibliography % then copy and past the contents of your .bbl file into your .tex file \begin{thebibliography}{10} \bibitem{fairrep} R. Aharoni, N. Alon, E. Berger, M. Chudnovsky, D. Kotlar, M. Loebl and R. Ziv, Fair representation by independent sets, {\em to appear in a volume in memory of J. Matousek}. \bibitem{matcomp} R. Aharoni and E. Berger, The intersection of a matroid and a simplicial complex. {\it Trans. Amer. Math. Soc.} {\bf 358}(2006), 4895--4917. \bibitem{abz} R. Aharoni, E. Berger and R. Ziv, The edge covering number of the intersection of two matroids, {\em Discrete Math.} {\bf 312} (2012), 81-–85. \bibitem{ACH} R.~Aharoni, P.~Charbit and D.~Howard, On a generalization of the ryser-brualdi-stein conjecture, {\emph Journal of Graph Theory} \textbf{78} (2015), no.~2, 143--156. \bibitem{ak} R. Aharoni and D. Kotlar, A weak version of Rota's conjecture for odd Dimensions, {\em Siam J. Discrete Math} {\bf 28}(2014), 385--393. \bibitem{akz} R. Aharoni, D. Kotlar and R. Ziv, Representation of large matchings in bipartite graphs, {\em Siam J. Discrete Math}. {\em to appear}. \bibitem{alishaimeunier} M. Alishahi and F. Meunier, Fair splitting of colored paths, arXiv:1704.02921. \bibitem{cl-eh} D.~Clemens and J.~Ehrenm{\"u}ller, An improved bound on the sizes of matchings guaranteeing a rainbow matching, {\em arXiv preprint} arXiv:1503.00438v1. \bibitem{edmondsdec} J. Edmonds, Submodular functions, matroids, and certain polyhedra, in R. Guy; H. Hanani, N. Sauer, J. Sch\"onheim eds. {\em Combinatorial structures and their applications} (Proc. 1969 Calgary Conference), Gordon and Breach, New York, pp. 69-87. \bibitem{fekszabo} Z. Fekete and J. Szab\'o, Equitable partitions into spanning trees in a graph, {\em Electronic Journal of Combinatorics}, {\bf 18}, Issue 1 (2011). \bibitem{goldberg} M. K. Goldberg, On multigraphs of almost maximal chromatic class (in Russian). {\em Metody Diskret. Analiz.}, {\bf 23} (1973), 3--7. \bibitem{huangrota} R.Huang and G-C. Rota, On the relations of various conjectures on Latin squares and straightening coefficients. {\em Discrete Mathematics}, {\bf 128} (1994), 225--236. \bibitem{KZ05} D. Kotlar and R. Ziv, On partitioning two matroids into common independent subsets. {\em Discrete Mathematics}. {\bf300}, 239--244 (2005). \bibitem{KZ14} D.~Kotlar and R.~Ziv, Large matchings in bipartite graphs have a rainbow matching, \emph{European Journal of Combinatorics} \textbf{38} (2014), 97--101. \bibitem{lovaszplummer} L. Lov\'asz and Plummer, {\em Matching Theory}, North Holland 1986. \bibitem{Pok1} A.~Pokrovskiy, Rainbow matchings and rainbow connectedness, {\em Elec. J. Combin.} \textbf{24} (1) (2017), P1.13. \bibitem{Pok2} A.~Pokrovskiy, An approximate version of a conjecture of Aharoni and Berger, arXiv preprint arXiv:1609.06346. \bibitem{matroidalgorithm} Scheinerman, Edward, Ullman, and Daniel, "5. Fractional arboricity and matroid methods", in Fractional graph theory, Wiley-Interscience Series in Discrete Mathematics and Optimization, New York: John Wiley and Sons Inc., pp. 99–126 \bibitem{seymour} P. D. Seymour, On multi-colourings of graphs and conjectures of Fulkerson and Tutte, {\em Proc. London Math. Society Ser. (3)}, {\bf 38}(1979), 423--460. \bibitem{welsh} D. J. A. Welsh, Matroid theory, Courier corporation (2010). \end{thebibliography} \end{document}