$RD^d$ is bipartite graph in which the vertices are $(d−1)$-element subsets and $d$-element subsets of a $(2d−1)$-element ground set. Two vertices are adjacent if one of the corresponding sets is a subset of the other.
My question is why any edge together with its incident edges defines an antimatching of $2d-1$ edges? And why $2d-1$?
Answer probably is related to the fact that this graph is $d$-regular but I have problem to justify it.
Best Answer
Let $G$ be a $d$-regular bipartite graph. And let $e_{uv}$ be an edge of $G$.
Let $S$ the set of $e_{uv}$ and all its adjacent edges. Then the size of $S$ is $2d-1$ : They are $d$ edges connected at the vertex $u$, and $d$ connected at vertex $v$. As we double count $e_{uv}$, we reduce the count by one, and $|S|=2d-1$.
Recall that an antimatching $A$ of $G$ is a set of edges such that two edges are at most at distance 2, and that the distance between two edges is defined as the distance between corresponding vertices in $L(G)$ (the Line graph of $G$).
As all edges from $S$ are connected to $e_{uv}$, then the maximum distance between edges of $S$ is 2.
Therefore $S$ is an antimatching of size $2d-1$.
I think that's all to proove. (I never studied antimatching before, I might be missing something).
Note An antimatching can also be defined (equivalently) as a subgraph with no induced matching of size greater than 1. This is also clearly the case for $S$ :
Suppose there exist an induced matching of size 2 in $S$. Then it must contains one edge connected to $u$ and one connected to $v$. But then in order to be induced we would need to include $e_{uv}$, and would not be a matching. Hence a contradiction. Therefore the only induced matching of $S$ have size 1.