most recent 30 from http://mathoverflow.net 2013-05-24T06:25:24Z http://mathoverflow.net/feeds/question/36583 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/36583/to-what-degree-do-min-cuts-specify-the-cut-function-of-a-graph Aaron 2010-08-24T18:49:47Z 2010-08-24T21:49:31Z

<p>Given an unweighted graph $G = (V, E)$, let the cut function on this graph be defined to be: $C:2^V \rightarrow \mathbb{Z}$ such that: $$C_G(S) = |{(u,v) \in E : u \in S \wedge v \not\in S}|$$</p> <p>For any two vertices $i,j \in V$, let the $(i,j)$ min-cut in a graph $G$ be: $$\alpha_{i,j}(G) = \min_{S \subset V : i \in S, j \not \in S}C_G(S)$$ Now, suppose we have two unweighted graphs on the same vertex set, $G = (V,E)$ and $H = (V,E')$ such that they are identical with respect to all $(i,j)$ min-cuts: $$\forall i,j \in V, \alpha_{i,j}(G) = \alpha_{i,j}(H)$$ How much can $H$ and $G$ differ with respect to their cuts? That is, how large can the following quantity be: $$\Delta(H,G) = \max_{S \subset V} |C_G(S) - C_H(S)|$$</p> <p>Note that if the graphs are allowed to be weighted (or to be multigraphs), then for any $G$, there is a tree $T$ that agrees with $G$ on all min-cuts (A Gomory-Hu tree). But I am interested in the case of unweighted graphs...</p>

http://mathoverflow.net/questions/36583/to-what-degree-do-min-cuts-specify-the-cut-function-of-a-graph/36589#36589 Tsuyoshi Ito 2010-08-24T20:18:12Z 2010-08-24T21:49:31Z

<p>If G and H are graphs with n vertices, Δ(G,H) can be Θ(n²).</p> <p>Here is an example which shows this. Let n=4k+1 be a prime. Define two graphs G=(V,E) and H=(V,E′) by V={0,1,2,…,4k}, E = {{i,j} | 1 ≤ ((j−i) mod n) ≤ k}, E′ = {{i,j} | k+1 ≤ ((j−i) mod n) ≤ 2k}. Note that G and H are both unions of k edge-disjoint Hamiltonian circuits, which implies that α_i,j(G)=α_i,j(H)=2k for any distinct i and j. Let S={0,1,2,…,2k−1}. Then Δ(G,H) ≥ C_H(S)−C_G(S) = k(3k+1)−k(k+1) = 2k² = Θ(n²).</p> <p>There is no reason to believe that this is the maximum of Δ(G,H) for given n, but it is obviously optimal up to a constant factor.</p>