Network Coding in Undirected Graphs Is Either Very Helpful or Not Helpful at All
summary
Main claim: either undirected networks never benefit from coding, or there exist undirected graphs where coding beats flow by a gap that grows to roughly a power of log of the network size. Method: start from any small undirected gap (>1) and amplify it by a graph tensor construction that replaces edges with entire source–sink gadgets, controls flow blowup using high-girth bipartite gadgets, and bounds coding rates with entropy upper bounds. Outcome: no conjecture resolution, but a concrete amplification pathway and size/gap tradeoffs.
AI-written summary · about