Shannon Capacity, Lovász Theta Number and the Mycielski Construction

Csonka, Bence and Simonyi, Gábor (2024) Shannon Capacity, Lovász Theta Number and the Mycielski Construction. IEEE TRANSACTIONS ON INFORMATION THEORY. pp. 1-35. ISSN 0018-9448 (print); 1557-9654 (online) (In Press)

Preview

Text 2312.09224v1.pdf Download (506kB) | Preview

Abstract

We investigate the effect of the well-known Mycielski construction on the Shannon capacity of graphs and on one of its most prominent upper bounds, the (complementary) Lovász theta number. We prove that if the Shannon capacity of a graph, the distinguishability graph of a noisy channel, is attained by some finite power, then its Mycielskian has strictly larger Shannon capacity than the graph itself. For the complementary Lovász theta function we show that its value on the Mycielskian of a graph is completely determined by its value on the original graph, a phenomenon similar to the one discovered for the fractional chromatic number by Larsen, Propp and Ullman. We also consider the possibility of generalizing our results on the Sperner capacity of directed graphs and on the generalized Mycielsky construction. Possible connections with what Zuiddam calls the asymptotic spectrum of graphs are discussed as well.

Actions (login required)

Edit Item