Fetching the paper…
Reading the bibliography…
We show that for any graph $G$, by considering "activation" through the strong product with another graph $H$, the relation $\alpha(G) \leq \vartheta(G)$ between the independence number and the Lov\'{a}sz number of $G$ can be made arbitrarily tight: Precisely, the inequality \[ \alpha(G \times H) \leq \vartheta(G \times H) = \vartheta(G)\,\vartheta(H) \] becomes asymptotically an equality for a suitable sequence of ancillary graphs $H$.
doi:10.1017/S0305004100021162
P. A. M. Dirac, A new notation for quantum mechanics, Mathematical Proceedings of the Cambridge Philosophical Society 35 (3) (1939) 416–418 · 1939
Earlier work this paper cites.
doi:10.1109/TIT.1956.1056798
C. E. Shannon, The Zero Error Capacity of a Graph, IRE Transactions on Information Theory 2 (3) (1956) 8–19 · 1956
Earlier work this paper cites.
doi:10.2307/2035288
M. Rosenfeld, On a Problem of C. E. Shannon in Graph Theory, Proceedings of the American Mathematical Society 18 (2) (1967) 315–319 · 1967
Earlier work this paper cites.
doi:10.1214/aoms/1177693169
R. J. McEliece, E. C. Posner, Hide and seek, data storage, and entropy, The Annals of Mathematical Statistics 42 (5) (1971) 1706–1716 · 1971
Earlier work this paper cites.
C. Berge, Graphs and Hypergraphs, North-Holland (Elsevier), Amsterdam, 1973
1973
Earlier work this paper cites.
doi:10.1007/BF00535895
R. Ahlswede, Channels with Arbitrarily Varying Channel Probability Functions in the Presence of Noiseless Feedback, Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete 25 (3) (1973) 239–252 · 1973
Earlier work this paper cites.
doi:10.1016/0095-8956(73)90014-2
R. S. Hales, Numerical invariants and the Strong Product of Graphs, Journal of Combinatorial Theory B 15 (2) (1973) 146–155 · 1973
Earlier work this paper cites.
doi:10.1109/TIT.1976.1055607
H. S. Witsenhausen, The zero-error side information problem and chromatic numbers, IEEE Transactions on Information Theory 22 (5) (1976) 592–593 · 1976
Earlier work this paper cites.
R. J. McEliece, E. R. Rodemich, J. Howard C. Rumsey, The Lovasz Bound and Some Generalizations, Journal of Combinatorics, Information and System Sciences 3 (3) (1978) 134–152
1978
Earlier work this paper cites.
doi:10.1109/TIT.1979.1055985
L. Lovász, On the Shannon Capacity of a Graph, IEEE Transactions on Information Theory 25 (1) (1979) 1–7 · 1979
Cited alongside, same era.
doi:10.1109/TIT.1979.1056027
W. Haemers, On Some Problems of Lovász Concerning the Shannon Capacity of a Graph, IEEE Transactions on Information Theory 25 (2) (1979) 231–232 · 1979
Cited alongside, same era.
doi:10.1109/TIT.1979.1056072
A. Schrijver, A Comparison of the Delsarte and Lovász Bounds, IEEE Transactions on Information Theory 25 (4) (1979) 425–429 · 1979
Cited alongside, same era.
R. A. Horn, C. R. Johnson, Matrix Analysis, Cambridge University Press, 1990
1990
Cited alongside, same era.
doi:10.1007/BF01261326
R. Peeters, Orthogonal Representations Over Finite Fields and the Chromatic Number of Graphs, Combinatorica 16 (3) (1994) 417–431 · 1994
Cited alongside, same era.
D. E. Knuth, The Sandwich Theorem , The Electronic Journal of Combinatorics 1 (1) (1994) #A1. URL http://www.combinatorics.org/ojs/index.php/eljc/article/view/v1i1a1
doi:10.1103/PhysRevA.82.010303
S. Beigi, Entanglement-assisted zero-error capacity is upper-bounded by the Lovász ϑ \vartheta function, Physical Review A 82 (2010) 010303 · 2010
Later among the works it cites.
doi:10.1109/TIT.2011.2159047
T. S. Cubitt, D. Leung, W. Matthews, A. Winter, Zero-Error Channel Capacity and Simulation Assisted by Non-Local Correlations, IEEE Transactions on Information Theory 57 (8) (2011) 5509–5523 · 2011
Later among the works it cites.
M. K. de Carli Silva, L. Tunçel, Optimization Problems over Unit-Distance Representations of Graphs , The Electronic Journal of Combinatorics 20 (1) (2013) #P43. URL http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i1p43
2013
Later among the works it cites.
M. K. de Carli Silva, Geometric Ramifications of the Lovász Theta Function and Their Interplay with Duality, Ph.D. thesis, University of Waterloo (2013)
2013
Later among the works it cites.
doi:10.1109/TIT.2014.2349502
T. Cubitt, L. Mančinska, D. Roberson, S. Severini, D. Stahlke, A. Winter, Bounds on Entanglement Assisted Source-channel Coding via the Lovász ϑ \vartheta Number and its Variants, IEEE Transactions on Information Theory 60 (11) (2014) 7330–7344 · 2014
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
1994
Cited alongside, same era.
doi:10.1109/SFCS.1994.365707
M. Szegedy, A note on the ϑ \vartheta number of Lovász and the generalized Delsarte bound, in: Proc. 35th Annual Symposium on Foundations of Computer Science, IEEE, 1994, pp. 36–39 · 1994
Cited alongside, same era.
E. R. Scheinerman, D. H. Ullman, Fractional Graph Theory: A Rational Approach to the Theory of Graphs, Vol. 46 of Wiley Series in Discrete Mathematics and Optimization, John Wiley & Sons, 1997
1997
Cited alongside, same era.
doi:10.1007/978-1-4684-2001-2_9
R. M. Karp, Reducibility among Combinatorial Problems, in: R. E. Miller, J. W. Thatcher, J. D. Bohlinger (Eds.), Complexity of Computer Computations, The IBM Research Symposia Series 1972, Springer Verlag, 1972, pp. 85–103 · 2001
Cited alongside, same era.
Later among the works it cites.
2015
Closest in time.
doi:10.1007/s00220-014-2260-1
A. Acín, T. Fritz, A. Leverrier, A. B. Sainz, A Combinatorial Approach to Nonlocality and Contextuality, Communications in Mathematical Physics 334 (2) (2015) 533–628 · 2015
Closest in time.
doi:10.1109/TIT.2015.2507979
R. Duan, A. Winter, Zero-Error Classical Channel Capacity of Quantum Channels and an Information Theoretic Interpretation of the Lovász Number, IEEE Transactions on Information Theory 62 (2) (2016) 891–914 · 2015
Closest in time.
D. Yang, A. Winter, Potential capacities of quantum channels , IEEE Transactions on Information Theory 62, (to appear); arXiv[quant-ph]:1505.00907 · 2016
Closest in time.