Reproduce “A group-theoretic approach to Shannon capacity of graphs and a limit theorem from lattice packings” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Pjotr Buys, Sven Polak, Jeroen Zuiddam
A group-theoretic framework was developed to derive new lower bounds for the Shannon capacity of graphs, particularly for fraction graphs, by translating the problem of finding independent sets in their powers into constructing lattices with specific properties. This approach also extends Bohman's limit theorem, demonstrating the asymptotic convergence of Shannon capacity for all fraction graphs.
Key insights
- A systematic group-theoretic and lattice-based framework can provide a unified method for deriving Shannon capacity lower bounds, moving beyond ad hoc constructions.
- The developed approach successfully circumvents known limitations of other structured, 'linear' constructions for independent sets.
- The group-theoretic method is powerful enough to demonstrate the asymptotic convergence of Shannon capacity to the fractional clique covering number for a broad class of fraction graphs.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.