The combinatorics, needless to say, is very closely related to TCS. But I found it hard to find the applications of enumerative combinatorics or Ramsey theory.

Or rather than being applied to TCS, the enumerative combinatorics or Ramsey theory is related to TCS because we use TCS techs and algorithms to tackle their problems.

I dont know very deep theory works, so please treat it easy.


2 Answers 2


This book will be helpful:


  • $\begingroup$ Yeah,thanks for mention the book. I have got one $\endgroup$
    – Yao Wang
    Mar 25, 2012 at 19:36

another book by stasys jukna[1] who was cited in the other answer has some key "applications". as always applications can be subjective, but in TCS a key application many would agree on is complexity class separations. there are about 30 references to ramsey graphs in this book as counted by a pdf search.

jukna makes the case that ramsey theory is about large structures guaranteed to contain some kind of "feature" and these can be shown to exist by shannon-style or shannon-reminiscent counting arguments, but building explicit constructions is very difficult and rarely accomplished in the literature. this is apparently highly analogous, possibly even directly linked, to the inability to explicitly construct complex circuits even though they are known to exist. construction of such circuits is key in complexity class separations. this is further emphasized by constructions in juknas book that directly tie graph complexity to complexity class separations (although so far not directly through ramsey graphs).

therefore this (same?/crosscutting?) phenomenon seems to be something like the "dark matter" of computer science. it is known to be there, it can be indirectly measured, but cannot be directly exhibited so to speak, and it is yet mysterious. jukna implies ramsey type thms or constructions could possibly be a bridge-type thm for complexity class separations (see sec 1.7).

see also sec 1.5, "where are all the complex functions"? however it is not so straightfwd, in constrast see also sec 11.7 where he uses ramsey graphs to show how "combinatorially complicated" graphs eg ramsey graphs are not nec "computationally complicated".

[1] Boolean function complexity, Advances and Frontiers by Stasys Jukna, 2011


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.