Packing Numbers – Are Packing Numbers Smaller Than Fractional Packing Numbers?

combinatoricselementary-number-theorygraph theoryinteger programminglinear programming

Take a graph $G=(V,E)$.

One of the equivalent ways of defining its independence number (also known as $1$packing number) is
$$\alpha = \max\left\{ \sum_{v\in V}f(v) : \forall v\in V, f(v) \in \{0,1\}\text{ and } \forall \text{ clique }C, \sum_{v\in C} f(v) \le 1\right\}$$
In words, it is the maximum number of $1$'s that can be obtained by assigning either $0$ or $1$ to each vertex, with the constraint that each clique can have at most a $1$.

The Rosenfeld number (also known as fractional packing number) is similarly defined by
$$\alpha^\star = \max\left\{ \sum_{v\in V}f(v) : \forall v\in V, f(v) \in [0,1]\text{ and } \forall \text{ clique }C, \sum_{v\in C} f(v) \le 1\right\}$$
where the only difference is that now vertices can be assigned any real number in $[0,1]$.

By their definition, it is clear that $\alpha \le \alpha^\star$, and I am aware that it can happen that $\alpha < \alpha^\star$ for some graphs.
However, in all the examples I could find, the two differ only by a small constant (see., e.g, Hales, 9172, Examples 2 and 4, where $\alpha = \beta$ and $\alpha^\star = \rho$).
This does not really allow me to see the big picture, so I wonder…

Question: Is it possible that $\alpha^\star \gg \alpha$?

I am assuming the answer is yes (it is hard to believe that people would introduce two different quantities that are always essentially the same), but noting that $\alpha^\star$ is the relaxation of the integer linear program that defines $\alpha$, I feel it could also be possible to prove that the two always differ by a (multiplicative and/or additive) constant.
That said, I have zero experience with LP techniques and it could very well be the case that one could find a sequence of graphs $(G_n)_{n\in\mathbb N}$ with $\alpha(G_n)= const$ but $\alpha^\star(G_n) \approx |V_n| \to \infty$ as $n\to \infty$.

Best Answer

One way to get an example is to find a triangle-free graph with low independence number. If an $n$-vertex graph $G$ contains no triangles, then $\alpha^*(G)$ is at least $\frac12 n$: we can assign $\frac12$ to every vertex, and because the only cliques are edges, this is still fine. So is there such a graph with $\alpha(G) \ll \frac12n$?

Well, it's known that the Ramsey number $R(3,t)$ is of order $\Theta(\frac{t^2}{\log t})$: there is a graph with $\Theta(\frac{t^2}{\log t})$ vertices that has no triangles or $t$-vertex independent sets. Solving for $t$ in terms of $n$, we can say that there is an $n$-vertex triangle-free graph with $\alpha(G) = \Theta(\sqrt{n \log n})$. This gives us the example we wanted, since $\sqrt{n \log n} \ll \frac12 n$ as $n \to \infty$.

The way to construct such examples is not very satisfying: it is a random process where we add random edges to our graph with the restriction of not creating any triangles, until no more edges can be added. Explicit constructions are known, but they are not as good; for example, Noga Alon's paper Explicit Ramsey graphs and orthonormal labelings constructs triangle-free graphs with $n$ vertices and $\alpha(G) = O(n^{2/3})$.

The only easily described example I can think of is a blow-up of a small triangle-free graph with small independence number. This can't get us an example with $\alpha \ll \alpha^*$, but we can still show that they can be far away from each other. For example, the blow-up of $C_5$ (take the $5$-cycle, replace every vertex by an independent set of size $\frac n5$, and replace every edge by $(\frac n5)^2$ edges between the two independent sets) has $\alpha = \frac25n$ and $\alpha^* = \frac12n$.


Moving away from triangle-free graphs, we have $\alpha^*(G) \ge \frac{n}{\omega(G)}$, where $\omega(G)$ is the clique number: just assign $\frac1{\omega(G)}$ to every vertex. So we get examples where $\alpha(G) \ll \alpha^*(G)$ whenever we have $\alpha(G) \cdot \omega(G) \ll n$. Again, this is intimately tied to Ramsey numbers.

A random graph on $n$ vertices where we flip a coin for every edge has $\alpha(G), \omega(G) = O(\log n)$, so that will work really well. Again, explicit examples that are equally good are hard to come by; see this MathOverflow question for details.

If all we want is $\alpha(G) \cdot \omega(G) \ll n$, then (inspired by this paper) we can do the following. Start with $C_5$ and repeat the following procedure: replace each vertex by a copy of $C_5$ and each edge by a copy of $K_{5,5}$ between the two copies of $C_5$ we got from its endpoints. After $k-1$ iterations, we get a graph with $5^k$ vertices, but clique number $2^k$ and independence number $2^k$. So the fractional independence number will be $(\frac 52)^k$ by assigning $\frac1{2^k}$ to every vertex: we get $\alpha \ll \alpha^*$.