Welcome to MathOverflow

Question

0

2

Lovasz theta function bounds the Shannon capacity of graphs. What are some other uses of the function - especially in asymptotic coding theory and optimization problems?

edited Nov 23 2011 at 22:49

asked Nov 23 2011 at 19:04

unknown (google)
1,009●4●11

Community wiki? – Yemon Choi Nov 24 2011 at 2:22

Joseph O'Rourke · Answer 1 · 2011-11-23 19:36:32Z UTC

2

Schrijver long ago established a connection to the Delsarte bound for a Hamming association scheme: A. Schrijver, "A comparison of the Delsarte and Lovasz bounds," IEEE Transactions on Information Theory, 25: 425-429 (1979).

answered Nov 23 2011 at 19:36

Joseph O'Rourke
43.2k●1●49●214

	@Joseph: Good reference. So is there a spectral characterization of minimum distance bounds in particular the GV bound? – unknown (google) Nov 23 2011 at 19:57
	Sorry, unknown, I do not know. – Joseph O'Rourke Nov 24 2011 at 14:37

Lovasz theta function - uses

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.