Comparing Graphs of Different Sizes

NEW

Problem: Reconstructed statement: for finite connected graphs $H,G$, say $H$ fractionally tiles $G$ if $G$ has a finite multiset of copies of $H$ covering every vertex of $G$ the same number of times. For a fixed finite graph $K$, let $f_K(X)$ be the number of packings of $X$ by vertex-disjoint copies of $K$, including the empty packing. The question asks whether

whenever $H$ fractionally tiles $G$. The source text supports the direction $\ge$ by referring to the preceding matching inequality and then asking the same for general packings, including the case $K=H$.

Result: The statement is false, even in the particular case $K=H$.

Let $G$ be the incidence graph of the projective plane $\mathrm{PG}(2,7)$. It is bipartite, with $57$ point-vertices and $57$ line-vertices; every vertex has degree $8$, any two points lie on a unique line, and any two lines meet in a unique point. Thus $|V(G)|=114$.

Let

the star with $8$ leaves, so $|V(H)|=9$.

Every vertex $x\in V(G)$ determines exactly one copy of $K_{1,8}$, namely the star consisting of $x$ and its eight neighbors. These $114$ stars fractionally tile $G$: each vertex belongs to its own star and to the $8$ stars centered at its neighbors, hence is covered $9$ times.

Now count packings by copies of $K_{1,8}$. In $H=K_{1,8}$, there is only one copy of $H$, so

In $G$, two point-centered stars intersect, since two points share a line; two line-centered stars intersect, since two lines share a point. A point-centered star and a line-centered star are disjoint exactly when the point is not incident to the line. Therefore packings in $G$ have size at most $2$, and

The proposed inequality would require

But $2908<2^{12}$, hence

So the claimed inequality fails.

Citation: Original problem: Russell Lyons, “Comparing Graphs of Different Sizes,” Combin. Probab. Comput. 26 (2017), 681–696, §5. The counterexample above is self-contained.