Skip to main content
Post Undeleted by user165057
Post Deleted by user165057
Post Undeleted by user165057
added 245 characters in body
Source Link
dbal
  • 242
  • 1
  • 4

I think there is a simple solution to this. Let $r$ be sufficiently large and partition $V(G)$ (approximately) evenly into sets $V_1, V_2, \ldots, V_{n/r}$. Your $G_i$s will be the graphs induced on the $V_i$s as well as the bipartiteany nonempty bipartite graphs induced between $V_i$ and $V_j$ with $i\neq j$. Then every edge is covered (exactly once in fact). And any intersection between two $G_i$s is either of size $r$ or of size 0.

The number of nonempty bipartite graphs incident to $V_i$ is at most $r\Delta$. So $$\sum_{j\neq i\,:\,n_{ij}>0}\frac{1}{2^{n_{ij}/4\Delta}} \le r\Delta\cdot \frac{1}{2^{r/4\Delta}} $$ which is less than 1 if $r$ is large enough.

I think there is a simple solution to this. Let $r$ be sufficiently large and partition $V(G)$ (approximately) evenly into sets $V_1, V_2, \ldots, V_{n/r}$. Your $G_i$s will be the graphs induced on the $V_i$s as well as the bipartite graphs induced between $V_i$ and $V_j$ with $i\neq j$. Then every edge is covered (exactly once in fact). And any intersection between two $G_i$s is either of size $r$ or of size 0.

I think there is a simple solution to this. Let $r$ be sufficiently large and partition $V(G)$ (approximately) evenly into sets $V_1, V_2, \ldots, V_{n/r}$. Your $G_i$s will be the graphs induced on the $V_i$s as well as any nonempty bipartite graphs induced between $V_i$ and $V_j$ with $i\neq j$. Then every edge is covered (exactly once in fact). And any intersection between two $G_i$s is either of size $r$ or of size 0.

The number of nonempty bipartite graphs incident to $V_i$ is at most $r\Delta$. So $$\sum_{j\neq i\,:\,n_{ij}>0}\frac{1}{2^{n_{ij}/4\Delta}} \le r\Delta\cdot \frac{1}{2^{r/4\Delta}} $$ which is less than 1 if $r$ is large enough.

Post Deleted by user165057
Source Link
dbal
  • 242
  • 1
  • 4

I think there is a simple solution to this. Let $r$ be sufficiently large and partition $V(G)$ (approximately) evenly into sets $V_1, V_2, \ldots, V_{n/r}$. Your $G_i$s will be the graphs induced on the $V_i$s as well as the bipartite graphs induced between $V_i$ and $V_j$ with $i\neq j$. Then every edge is covered (exactly once in fact). And any intersection between two $G_i$s is either of size $r$ or of size 0.