In this post, I will discuss basic definitions and theory related to hypergraphs and cut sparsifiers. I will start from the basic definitions of Graphs, then generalize these definitions to Hypergraphs. Later, I will discuss some related theory about Cut-Sparsifiers.

Let’s start from the very beginning - graphs. Graphs are fundamental objects in computer science, and they are used to model relations between objects. Formally, a graph $G=\left(V,E,w\right)$ is a tuple of two sets, $V$ and $E$ and a function $w$ . $V$ is the set of vertices (i.e. the elements), usually denoted as $\left[n\right]:=\left\{ 1,2,..,n\right\}$ , and $E$ is a set of edges between those vertices (i.e. indicating which elements belongs to the relation the graph represents). An edge is just a set of two vertices, that is $e=\left\{ u,v\right\} \in E\subseteq\left\{ A\mid A\subseteq V,\:\:\left|A\right|=2\right\}$ . The function $w:\:E\rightarrow\mathbb{R}$ assigns a weight to every edge in the graph (we will focus on non-negative weights). For instance, we can model friendships in Facebook as a graph, the vertices will be all the users in Facebook, and there will be an edge between any pair of users if they are “friends” of each other.

The model of a graph, as defined above, can’t be used to describe non binary relationships. For example, say we want to model Facebook groups via a graph; the only way to do that is by including in the set of vertices also any group in Facebook, and then connecting each user to any of its groups with an edge. The main issue with such construction is that the vertices represents both users and facebook-groups. In order to avoid such ambiguity we can use a richer model, we can use Hypergraphs.

We move to define Cut-Sparsifiers: Let $\epsilon\in\left(0,1\right)$ . Given a hypergraph $H=\left(V,E\right)$ and a weight function $w$ , we say that a hypergraph $K=\left(V,E_{\epsilon},w\right)$ is $\epsilon$ -cut-sparsifier of $H$ if $$\forall S\subset V\qquad(1-\epsilon)\cdot w_{H}(S)\le w_{K}(S)\le(1+\epsilon)\cdot w_{H}(S)$$ and the set $E_{\epsilon}$ may be any set in $2^{V}\backslash\emptyset$ . The subscript “$H$ ” in the function $w_{H}\left(\cdot\right)$ indicates that the weights are over the hypergraph $H$ (and similarly with $w_{K}\left(\cdot\right)$ and $K$ ).

For regular graphs, we already know how to reduce the number of edges to be $\mathcal{O}\left(n/\epsilon^{2}\right)$ for any $\epsilon\in\left(0,1\right)$ . That is surprising, because no matter how many edges there are in the original graph, which can be up to $n^{2}$ , there is an algorithms that can reduce the number of edges to $\mathcal{O}\left(n/\epsilon^{2}\right)$ , while maintaining approximately the same weights for all possible cuts in the graph. Moreover, that algorithm find the cut-sparsifier in polynomial time.