<p>Could we realize good bounds on Ramsey theoretic problems using semidefinite programming? Example: Is there a good bound on Ramsey numbers $R(r,s)$ from semidefinite programming?</p>

<p>Does number of quantifiers matter in semidefinite programming? In maximizing independence number, we ask ∃ independent set of given size? In Ramsey number we ask ∀ graphs of given size ∃ clique or independent set of given sizes?</p>

CC BY-SA 3.0
2015-02-17T04:07:42.817Z
You might be interested in the work on flag algebras: http://www.ams.org/notices/201310/rnoti-p1324.pdf.
Sasho Nikolov
CC BY-SA 3.0
2015-02-17T06:48:23.690Z
Thank you, I thought I saw somewhere that Shannon capacity and diagonal Ramsey numbers were linked by McEliece et al. Is this explicitly through SDP? Also does number of quantifiers matter? In maximizing independence number, we ask $\exists$ independent set of given size? In Ramsey number we ask $\forall$ graphs of given size $\exists$ clique or independent set of given sizes?
Turbo
CC BY-SA 3.0
2015-02-17T16:51:32.037Z
Did you try searching for these things? Here is the old paper I think you are referring to: http://projecteuclid.org/euclid.pjm/1102970742. Here is something recent in this direction http://arxiv.org/pdf/1201.0304.pdf
Sasho Nikolov
CC BY-SA 3.0
2015-02-17T20:40:30.633Z
@SashoNikolov Yes I saw both papers. They link independence numbers with ramsey but not shannon capacity. I assumed I saw there was a link. Atleast there was an approach via SDP which I cannot locate.
Turbo
<semidefinite-programming><ramsey-theory>
Ramsey theory through semidefinite programming
Turbo
# Ramsey theory through semidefinite programming

(Asked by: username_0 on 2015-02-17)

Could we realize good bounds on Ramsey theoretic problems using semidefinite programming? Example: Is there a good bound on Ramsey numbers $R(r,s)$ from semidefinite programming?

Does number of quantifiers matter in semidefinite programming? In maximizing independence number, we ask ∃ independent set of given size? In Ramsey number we ask ∀ graphs of given size ∃ clique or independent set of given sizes?

**Tags:** semidefinite-programming, ramsey-theory
> **Comments:**
> **username_1**: You might be interested in the work on flag algebras: http://www.ams.org/notices/201310/rnoti-p1324.pdf.  
> **username_0**: Thank you, I thought I saw somewhere that Shannon capacity and diagonal Ramsey numbers were linked by McEliece et al. Is this explicitly through SDP? Also does number of quantifiers matter? In maximizing independence number, we ask $\exists$ independent set of given size? In Ramsey number we ask $\forall$ graphs of given size $\exists$ clique or independent set of given sizes?  
> **username_1**: Did you try searching for these things? Here is the old paper I think you are referring to: http://projecteuclid.org/euclid.pjm/1102970742. Here is something recent in this direction http://arxiv.org/pdf/1201.0304.pdf  
> **username_0**: @SashoNikolov Yes I saw both papers. They link independence numbers with ramsey but not shannon capacity. I assumed I saw there was a link. Atleast there was an approach via SDP which I cannot locate.  

---

## 0 answers

