Finding Bipartite Components in Hypergraphs Supplementary Material

In this section we prove Theorem 2. After giving some additional preliminaries, and discussing the rules of the diffusion process, we will construct a linear program which can compute the rate of change r satisfying the rules of the diffusion process. We then give a complete analysis of the new linear program which establishes Theorem 2. A.1 Additional preliminaries Given a hypergraph H = (V A.2 Counter-example showing that rule (2) is needed First, we recall the rules which the rate of change of the diffusion process must satisfy. One might have expected that Rules (0) and (1) together would define a unique process. In such a scenario, either {u, w} or {v, w} can participate in the diffusion and satisfy Rule (0), which makes the process not uniquely defined and so we introduce Rule (2) to ensure that there will be a unique vector r which satisfies the rules. A.3 Computing r by a linear program Now we present an algorithm that computes the vector r = df Next we study every equivalence class U U in turn, and will set the r-value of the vertices in U recursively.