Coarse-graining a hypergraph

Question

$\DeclareMathOperator{\poly}{\mathrm{poly}}$I have asked this question on math.SE here, but couldn't get a satisfactory answer. I have also asked a related question on math overflow here, but haven't received much response. I have since refined the question considerably, so the following is self-contained.

---

Let $G$ be a connected hypergraph with vertex-set $V$ and hyperedge-set $E \subseteq 2^V\smallsetminus \{\emptyset\}$. Assume that every vertex is part of at most $\Delta$ hyperedges and every hyperedge has at most $\Delta$ vertices. I call such $G$ a bounded-incidence hypergraph.

Let $n\ge1$ be an integer. I define a good cover of $G$, with $|V(G)|\ge n$ and maximum incidence $\Delta$, as a finite collection $\{G_1,G_2,\ldots\}$ of sub-hypergraphs of $G$ such that

1. each $G_i$ is a connected, induced sub-hypergraph of $G$,
2. there is an integer $m\ge1$ such that every hyperedge of $G$ is contained in at least one and at most $m$ distinct $G_i$'s.
3. there is an integer $N\ge n$ such that $n\le |V(G_i)|\le N$ for each $i$, and
4. for each $i\ne j$, either $V(G_i \cap G_j) = \emptyset$ or $|V(G_i\cap G_j)| \ge n$.

Given an individual hypergraph $G$, it is easy to construct good covers, but I want to do this uniformly for all bounded-incidence hypergraphs. More precisely,

Question: are there integers $m$ and $N$ which depend only on $\Delta$ and $n$ such that $m,N \sim \poly(n)$ and every hypergraph on at least $n$ vertices and of bounded-incidence $\Delta$ has a good cover with these parameters for sufficiently large $n$?

In other words, is the following statement true?

$\forall \Delta, \exists n_0, \forall n>n_0, \exists m,N \sim \poly(n), \forall G$ with $|V(G)| \ge n$ and maximum incidence $\Delta$, there is a good cover of $G$ with these parameters.

---

Motivation: The real motivation behind this question involves a problem in physics that I have been thinking about for a while. The key part of it can be explained by a standard example. Consider a $2$-dimensional square lattice with periodic identifications in both directions and large enough size in both directions. Consider the hypergraph $G$ with $V$ as the vertices of the lattice and $E$ as the plaquettes. (The hyperedges are supposed to represent four-body interactions of the particles on the four incident vertices.) Since each vertex is shared by four plaquettes, and each plaquette contains four vertices, this is a hypergraph of incidence $\Delta = 4$. For an integer $k\ge2$, consider the square regions of length $2(k-1)$ centred at points that are integer multiples of $k$. (This is known as coarse-graining in physics, because the square regions are larger than the original unit cells, and are now treated as the effective unit cells, albeit not necessarily disjoint.) It is easy to see that (i) each square region is a connected induced sub-hypergraph on the vertices it contains, (ii) each plaquette is contained in at least one and at most four square regions, (iii) each square region contains $(2k-1)^2$ vertices, and (iv) two such square regions contain $O(k^2)$ vertices whenever they overlap. Therefore, we have a good cover with $n=O(k^2)$, $N=O(k^2)$, and $m = 4$. In other words, as we make the square regions larger, the number of vertices within them increase, but they do not increase exponentially (i.e., $N$ grows only polynomially in $n$; here linearly), the number of overlaps between various square regions is not too big (i.e., $m$ grows only polynomially in $n$; here a constant), and the size of any nontrivial overlap is large enough (i.e., grows at least linearly in $n$; here linearly).

The above example generalizes straightforwardly to other regular lattices in any dimension. I want to further generalize this construction to situations where there is no underlying lattice. That is particles are situated at vertices of a hypergraph, and their interactions are captured by the hyperedges. In other words, I want to coarse-grain a hypergraph. I don't want too many particles to interact at the same time, and I also don't want a particle to be part of too many interactions. This translates to the requirement of bounded-incidence of the hypergraph.

---

Attempt: While it might seem impossible to satisfy all the above requirements, if $G$'s are restricted to be graphs (i.e., all hyperedges are edges), then I know how to construct a good cover uniformly for all graphs with $m \sim n$ and $N \sim n^2$. I first want to construct a partition of the vertices and then construct a good cover using it. Let $P$ be the set of "covered" vertices, which is initially empty. In the induced subgraph on $V(G)\setminus P$, pick a largest possible connected induced subgraph of size at most $n+1$. If the size of this subgraph is at least $n$, call it a good part, else call it bad part. Add the vertices in this part to $P$ and repeat until $P=V(G)$. The nice thing about this construction is that the bad parts are never adjacent to each other (if they were adjacent, we could have built a bigger connected part by combining them). Now, define the $G_i$'s for the good cover as follows: for each part, take the union of that part and all the good parts adjacent to it. It is easy to see that these $G_i$'s satisfy conditions 1, 2, and 3. For condition 4, if $G_i$ and $G_j$ intersect, they must do so on a good part because no two bad parts are adjacent. Therefore, any nontrivial intersection contains at least $n$ vertices. QED.

I also know how to make this argument work when the hypergraphs are tree-like. More precisely, consider the incidence graph of the hypergraph $G$: it is the bipartite graph with left-set as $V$ and right-set as $E$, with an edge from $v\in V$ to $e\in E$ if and only if $v$ is incident to $e$ in $G$. If this incidence graph is a tree, then I know how to construct a good cover using a similar argument as above. (A closely related argument is given here, where I show it for $\Delta$-regular tree, but it can be tweaked easily to make it work for any tree of maximum degree $\Delta$.)

The key issue with extending this approach to hypergraphs is that the bad parts could be adjacent. So the argument for "intersection is $\ge n$" doesn't go through. I don't know how to avoid this. I would appreciate any help in circumventing this issue or coming up with a new approach to answer the question in the positive.

Answer 1

Below I try to present a solution for the general case of your question that is based on your idea for graphs.
Let me split your $\Delta$ into two parts: every vertex should have degree at most $\Delta$ and every hyperedge should be of size at most $k$.

First, I will present the main idea for $k=3$ (which implies $3$-uniform hypergraphs).
In our initial hypergraph $G_3$, we take a maximal family $\mathcal{GP}$ of good parts: connected components whose size is between $n$ and $n+2$.
Denote the vertices covered by $\mathcal{GP}$ by $GV$.
Then we partition the graph induced by $V\setminus GV$ to maximal connected components; each of these has size less than $n$, allowing isolated vertices of size $1$.
We contract every part outside $\mathcal{GP}$ to obtain the vertex set of a new graph, $G_2$.
So each vertex of $G_2$ corresponds to less than $n$ vertices from $V\setminus GV$.
Two vertices $u,v$ of $G_2$ form an edge $uv$ if there is an edge $e$ of $G_3$ that intersects the two parts corresponding to $u$ and to $v$ in $G_3$.
Note that such an $e$ must necessarily intersect $GV$, otherwise the two parts it connects would not have been maximal, so $|e|=3$.

The graph $G_2$ satisfies the degree condition with some $\Delta_2\le n\Delta$.
We can apply your argument to $G_2$ to obtain a good cover $\mathcal{GC}_2$ of $G_2$ where the size of each part is at most $N_2\sim \Delta n^2$.
Using this, we construct a good cover $\mathcal{GC}$ for the original graph as follows.
Every part from $\mathcal{GP}$ will be in $\mathcal{GC}$.
Also, for each part of $\mathcal{GC}_2$ we add it (i.e., the vertices of $G_3$ contained in a part associated with a vertex of the part) with the parts of $\mathcal{GP}$ adjacent to it in $G_3$ to $\mathcal{GC}$.
In fact, we also need to do this for each edge of $G_3$ to ensure your condition 2 (I think this was also missing from your argument for graphs).
This gives us $m,N\sim \Delta^2n^3$.

The same argument works for $k>3$, just the exponent of the eventual polynomial will depend on $k$, but if I understood your motivation correctly, that is fine.
I don't know if one can remove this dependence or not.