fractional coloring of a matroid

49 Views Asked by At

Given a matroid $M$, a fractional coloring $f$ is a function from the collection $I(M)$ of independent sets of $M$ to non-negative real numbers such that for any $v$ in the ground set, $$\sum_{A\in I(M):v\in A}f(A)\ge 1.$$ And $\chi^*(M)$ is the minimum of $\sum_{A\in I(M)}f(A)$ over all fractional coloring of $M$.

Let $$\Delta(M):=\max_{A\subseteq V(M)}\frac{|A|}{\rho_M(A)},$$ where $\rho_M(A)$ is the largest size of independent sets of $M$ contained in $A$.

One claims that $$\chi^*(M)\ge \Delta(M).$$ I am wondering how to prove this.

1

There are 1 best solutions below

0
On BEST ANSWER

Let $A$ be a set attaining $\Delta(M)=|A|/\rho_M(A)$. So $\rho_M(A)=|A|/\Delta(M)$, which implies all the independent sets contained in $A$ has size at most $|A|/\rho_M(A)$.

Given a fractional coloring $f$, we have $\sum_{v\in A}\sum_{B\in I(M):v\in B}f(B)\ge |A|$. And each $B$ is over counted at most $|A|/\Delta(M)$ times: $B$ is over counted $|B\cap A|$ times, which is at most $\rho_M(A)=|A|/\Delta(A)$. Therefore we have $$\sum_{B\in I(M)}f(B)\ge \sum_{v\in A}\sum_{B\in I(M):v\in B}f(B)/(|A|/\Delta(A))=\Delta(A) $$ for any fractional coloring $f$.