Ramsey's theorem and self-complementary graphs (Q2554708): Difference between revisions

A graph \(G\) is called \(s\)-good if neither \(G\) nor its complement contains a complete graph with \(s+1\) vertices. By Ramsey's theorem, given any \(s\) there is the least integer \(n(s)\) such that no graph with more than \(n(s)\) vertices is \(s\)-good. Let \(n^*(s)\) be the largest number of vertices of a self-complementary \(s\)-good graph. Then \(n^*(s) \leq n(s)\). One has \(n^*(2)=n(2)=5\) and \(n^*(3)=n(3)=17\); perhaps \(n^*(s)=n(s)\) for all \(s\). The authors prove \(n^*(st) \geq (n^*(s)-1)n(t)\); in particular, \(n^*(2t) \geq 4n(t)\). The last inequality together with an earlier exponential lower bound on \(n(s)\), due to Erdős, yields an exponential lower bound on \(n^*(s)\). An application to Shannon's notion of a capacity of \(G\) is mentioned.