# C1: Static EDCS

This post is based on [1].

The definition of EDCS can be seen in the post EDCS Definitions.

## 1. EDCS for a bipartite graph

\(\textbf{Lemma 1}\). Let \(G=(L, R, E)\) be a bipartite graph and \(\epsilon < 1/2\). For \(\lambda \leq \frac{\epsilon}{4}\), \(\beta_2 \geq 2\lambda^{-1} \geq \frac{8}{\epsilon}\), and \(\beta_1 \geq (1-\lambda)\beta_2 \geq 8/\epsilon -2\), \(H:=EDCS(G, \beta_1,\beta_2)\), \(\mu(G) \leq (3/2+\epsilon)\mu(H)\).

So, let us try to prove this in one hour. For bipartite matching, we had to know the famous Hall’s Theorem.

\(\textbf{Lemma 2} \text{(Hall's Marriage Theorem)}\). A biparite graph \(G=(L, R, E)\) has a perfect graph if and only if \(\forall A\subseteq L: \lvert A\rvert \leq \lvert N(S) \rvert\) and \(\forall B\subseteq R: \lvert B\rvert \leq \lvert N(B) \rvert\).

But what if a bipartite graph does not have a perfect matching. There is a conception that is interesting.

\(\textbf{Deficiency}\). Let \(G = (V, E)\) be a graph and let \(U\) be an independent set of vertices. We use \(N_G(U)\) to denote the set of neighbors of \(U\). The deficiency of a set \(U\) is defined as \(def_G(U) = \lvert U \rvert - \lvert N_G(U) \rvert\) If \(G\) is a bipartite graph \(G=(L, R, E)\), we define \(def(G;L) = \max_U def_G(U)\)

\(\textbf{Theorem 1}\). Every bipartite graph \(G=(L,R,E)\) admits a matching with size \(\mu(G) \geq \lvert L\rvert- def(G;L) = n -def(G,L).\)

To prove Lemma 1, we need to find the relationship between EDCS and the above observation. I feel EDCS is a set of sampling average edges. The degree of each node in EDCS is similar. What does that help us prove this lemma?

( After 0.5 hour ......) Oh, I cannot know how to find the relationship. Let me try to start from the conclusion. There is an obstacle: how to remove \(\max\) from the formula?

It is not easy to prove this lemma. I will try to prove this next time.

To be continued....## 2. EDCS for a non-bipartite graph

## Reference

[1]. Assadi, Sepehr, and Aaron Bernstein. “Towards a Unified Theory of Sparsification for Matching Problems.” *2nd Symposium on Simplicity in Algorithms*. 2019.