Fetching the paper…

Reading the bibliography…

2018

New lower bound on the Shannon capacity of C7 from circular graphs

Polak, Sven, Schrijver, Alexander

Original
PDF
Post on X

Understand

We give an independent set of size $367$ in the fifth strong product power of $C_7$, where $C_7$ is the cycle on $7$ vertices.

This leads to an improved lower bound on the Shannon capacity of $C_7$: $\Theta(C_7)\geq 367^{1/5} > 3.2578$.
The independent set is found by computer, using the fact that the set $\{t \cdot (1,7,7^2,7^3,7^4) \,\, | \,\, t \in \mathbb{Z}_{382}\} \subseteq \mathbb{Z}_{382}^5$ is independent in the fifth strong product power of the circular graph $C_{108,382}$.
Here the circular graph $C_{k,n}$ is the graph with vertex set $\mathbb{Z}_{n}$, the cyclic group of order $n$, in which two distinct vertices are adjacent if and only if their distance (mod $n$) is strictly less than $k$.

New lower bound on the Shannon capacity of C7 from circular graphs · Around

Built on

M. Fekete, Über die Verteilung der Wurzeln bei gewissen algebraischen Gleichungen mit ganzzahligen Koeffizienten,
1923
Earlier work this paper cites.
C.E. Shannon, The zero-error capacity of a noisy channel,
1956
Earlier work this paper cites.
L. Baumert, R. McEliece, E. Rodemich, H. Rumsey, R. Stanley, H. Taylor, A combinatorial packing problem,
1971
Earlier work this paper cites.
L. Lovász, On the Shannon capacity of a graph,
1973
Earlier work this paper cites.
W.H. Haemers, On some problems of Lovász concerning the Shannon capacity of a graph,
1979
Earlier work this paper cites.

Similar

J.A. Bondy, P. Hell, A note on the star chromatic number,
1990
Cited alongside, same era.
C.D. Godsil, Problems in algebraic combinatorics,
1995
Cited alongside, same era.
N. Alon, The Shannon capacity of a union,
1998
Cited alongside, same era.
A. Vesel, J. Žerovnik, Improved lower bound on the Shannon capacity of
2002
Cited alongside, same era.
T. Bohman, A limit theorem for the Shannon capacities of odd cycles I,
2003
Cited alongside, same era.

Then

C. Bachoc, A. Pêcher, A. Thiéry, On the theta number of powers of cycle graphs,
2013
Later among the works it cites.
M. Jurkiewicz, M. Kubale, K. Turowski, Some lower bounds on the Shannon capacity,
2014
Later among the works it cites.
K.A. Mathew, P.R.J. Östergård, New lower bounds for the Shannon capacity of odd cycles,
2017
Later among the works it cites.
Gurobi Optimization, LLC,
2018
Closest in time.
J. Zuiddam, The asymptotic spectrum of graphs and the Shannon capacity,
2018
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…