Graduate studies (PhD) in CS Theory vs. Applied Math Given most American universities only accept applications in only one field, I'm trying to figure out what are the advantages/disadvantages of applying to a CS theory program vs an applied math program given one's interest lies somewhere in both departments.

To be more specific, my areas of interest in decreasing order are 
1. Combinatorics (Both algebraic and extremal), 
2. Optimization (Both convex and combinatorial), 
3. Probability theory, randomized algorithm, and information theory.

I don't exactly know on what or with whom I want to work which makes applying to graduate programs a huge headache. So far my understanding is applied math programs are more flexible given CS theory groups are usually very small and focused. On the other hand, I feel a CS degree would fare better in industry if one happened to venture that path.

So to reiterate my question, for someone who doesn't exactly know what he wants to do but generally interested in aforesaid topics, which is better? CS Theory or Applied Math
My two cents are that in my university we've had both mathematics PhD students working on computer science questions (and faculty in the math department with interests in computer science), as well as some computer science students working primarily on purely combinatorial problems.

You might be right that it's sometimes easier to work on CS questions as a math student, rather than on pure math questions as a CS student. Keep in mind that at least in the first two years these two kinds of programs might be fairly different in content. As a math student you will be expected to take core math courses as real analysis, complex analysis, topology, algebra, etc. Combinatorics is usually not part of this core. For a CS program there will be a core CS requirement, which usually involves taking some mix of theoretical and more applied courses. While the core in a math program is fairly standard and strictly enforced, the core in a CS program tends to depend a lot on the program, and the requirements might be more flexible.

However, all that is not really of primary importance (although it will be loads of work) and is all over within the first two years. I understand it's hard to know what you want to work on before you're in grad school, and many students change  their fields. Nevertheless, I would encourage you to look at the faculty pages of schools you are considering, see what professors are working on, and write several emails to faculty and students. PhD level studies are much more about personal relationships and personal drive than they're about a program as a whole. Good programs at the PhD level in my view are distinguished by a strong faculty, and an energetic research culture, rather than by curriculum. You should inquire from faculty and current students about questions like the level of collaboration between math and CS departments. And you should really try to find faculty that have a mix of interests that appeals to you. It's a good idea to write to them to express your interest as well.

As far as industry jobs, I'm not sure there is a huge difference between a CS theory degree and an applied math  degree. But I am not very knowledgeable about this.