# where do combinatorics play a role in computer science?

I am graduated from computer science. I need some advice in Combinatorics material related to master fields of computer science. I already know that discrete mathematics have a key role in some concepts which I need a little more elaboration. In which fields could I trace combinatorics concepts and theorems and techniques?

• Combinatorial optimization. Commented Feb 15, 2017 at 19:54
• If you never heard about complexity theory, read about it, it is quite pleasant. Commented Feb 15, 2017 at 20:24
• Analysis of algorithms. For example, see "Analysis of Algorithms" by Sedgewick and Flajolet, or "Concrete Mathematics" by Graham, Knuth, and Patashnik. Commented Feb 16, 2017 at 1:04
• Honestly this question surprises me. Combinatorics is used pretty much everywhere in CS. You have a degree in computer science, what did you specialize in? I'm certain that no matter what you specialized in, combinatorics is used there. Commented Feb 16, 2017 at 3:58
• @StellaBiderman I know It's surprising But combinatorics topics and methods aren't recognized since they are very vast; from inclusionâ€“exclusion principle to well-known theorems like Ramsey theorem Hall theorem or even Regularity lemma) I was interested in some(including setsystems properties for example vc dimension or epsilon net theorem) and I find the other type of problems very hard to work with(like VC density and other topics in complexity) this post was for some clarifying purposes to finding the next step of combinatorics methods in cs. Commented Feb 17, 2017 at 14:25

## 1 Answer

Graph Theory is a part of Combinatorics that is extremely important in computer science. Roughly, it is the study of objects and connections between them.

Algorithms and Data Structures uses combinatorial techniques for analysis and design extensively. Several Data Structures use graph theoretic ideas to efficiently store and retrieve data. Randomized Algorithms and Approximation Algorithms require combinatorial methods for analysis. They are often faster or more "useful" than deterministic ones.

Complexity Theory, the study of the complexity of resources used by computational procedures, use combinatorial problems and ideas as examples of several sorts of complexity classes. Discrete Optimization, in particular, is a class of problems which are of relevance to both theoreticians and practical purpooses. Some of them represent problems which are too hard for detereministic procedures and give way to randomized and approximate algorithms.

Other interesting Computer Science fields where combinatorics is important include Coding Theory(Error Correcting Codes over Communication Channels), Computational Geometry, etc.