What kinds of Combinatorial problems do you like?

Since many people asked me questions like ``what is combinatorics?'', ``What are combinatorists caring about?'', I decided to write this for a general answer.

Combinatorics is a problem-driven branch of mathematics. There are various kinds of problems you may find interesting. According to Four Types of Problems by Robin Wilson, combinatorists usually ask:

• Existence: Do there exist some structures satisfying two restrictions that seem contradictory?

  • Example: (Graph theory) Is there a graph with its girth $>g$, whilst its chromatic number $>\chi$?

  • Example: (Aperiodic tiling) Is there a 2D-shape that it can tile $\R^2$, but only non-periodically?

• Construction: We know that some structures exist; can we find an explicit one?

  • Example: (Ramsey number) By some probabilistic arguments, we know that $R(k,k)>2^{k/2}$, can we find an explicit construction?

  • Example: (Graph theory) How to find an explicit graph with girth $g$ and chromatic number $\chi$ efficiently?

• Enumeration: How many such elements(configurations) are there satisfying the restriction?

  • Example: (Stirling numbers) How many ways are there to put $n$ people into $k$ groups, so that each group has at least one person?

• Optimization: How best can you do to max(min)imize the value?

  • Example: (Minimal spanning tree) You are a city builder, and there are some cities you want to connect via building roads between some pairs of them. Building a road between each pair of cities requires different costs. What is the minimal cost to build a connected network?

Some of the above examples are still open, while some of them have been solved in recent years (2023).

Due to its wide variety and weak relation between topics, ``Combinatorics'' is not suggested to be considered as a ``field of mathematics'', but a wide collection of problem-based theories. So a course in the title of ``Combinatorics'' is not a good idea. A better name is either ``Probabilistic method and Algebraic method'', or ``Enumerative combinatorics and generating functions'', etc. 

To step into the kingdom of Combinatorics, I suggest studying this book:  A Course in Combinatorics by Jacobus Hendricus van Lint. 

A title like this surely attracts many people's eyes. This book contains many topics that are of general interest. It is a good way to take a glimpse of the Combinatorics world.

The other way to step into this kingdom is to see the problem directly! Most --- if not all --- books of Combinatorics I have seen inspire readers by problems, so it is better to first see the problems that you care about, then the theory for the solutions. 

For those who have known something about Combinatorics and want to see the whole picture of this kingdom, there are some topics in Combinatorics in my mind, and I have listed them here.

• Graph Theory: It is a fundamental theory of Combinatorics since 1736. Since many problems have a graph-theoretic formulation, it's best to read if you don't have a direction yet. 

  • Suggested: 演算法觀點的圖論 by 張鎮華, Graph Theory by Reinhard Diestel, Graph Theory by West Douglas (last but not least)

  • Note: Graph theory has its own problems, such as Ulam's conjecture. However, graphs are usually used to formulate problems, and these books are for background information on the properties of graphs. 

• Probabilistic method: The essence of Combinatorics is about problem-solving skills, so there are some theories based on problem-solving methods. This is a typical example of using probabilistic arguments for a wide variety of combinatorial problems.

  • Suggested: The Probabilistic Method, 4th Edition by Noga Alon, Joel H. Spencer

• Enumerative Combinatorics: If you are into counting, you must not miss this topic. The goal of this topic is to find elegant (and deep) connections between various mathematical objects, which may provide possibilities of transforming problems into one another.

  • Suggested: Enumerative Combinatorics by Richard P. Stanley

• Additive Combinatorics: I am not familiar with this topic, so I couldn't write anything about it, but some people (including me) find this cool.

  • Suggested: Additive Combinatorics by Terence Tao, Van H. Vu, or the online course by Timothy Gowers, a Fields Medalist.

• Algebraic Combinatorics: The scope of algebraic combinatorics contains combinatorial designs, Young tableaux, finite geometry, and more. This branch has a lot of structural results. Good if you like universal structures.

  • Suggested: For spherical design, strongly regular graph, association scheme, I suggest Algebraic Combinatorics by Eiichi Bannai, Etsuko Bannai, Tatsuro Ito, and Rie Tanaka

  • Richard P. Stanley is a prestigious combinatorist; for this reason, I also suggest Algebraic Combinatorics: Walks, Trees, Tableaux, and More for a basic understanding of Algebraic combinatorics.

• Polynomial method: Another useful method-type theory, which is still highly active.

  • Suggested: Polynomial Method in Combinatorics by Youri Tamitegama, a course of Yufei Zhao at MIT. Jian-An Wang  also suggested to me Polynomial Methods and Incidence Theory by Adam Sheffer 

• Lattice Theory: About posets, antichains. Just like graph theory, many problems are expressed in lattices.

  • Suggested: Lattice Theory by Garrett Birkhoff, or this one for a quick glimpse of what a lattice is for.

• Coding Theory: Yet another topic I have no experience with. 

  • Suggested: Error Correcting Codes: A Mathematical Introduction by John Baylis (you may get some alternative material here)

• Combinatorial Identities: Henry W. Gould has a table of combinatorial identities. As every identity is a theorem, this list is full of exciting problems, with possible relations to other problems. Highly related to Enumerative combinatorics.

• Some other topics I missed: Since I missed them, I could not list them here. Contact me if you want something on this list.

One can also see what problems the professors are interested in. Combinatorics is a subject that is relatively easy to understand, without too much prior knowledge.

Yufei Zhao: Yufei Zhao | MIT Mathematics

There is a list of unsolved combinatorial problems from 2001. See if you would like some random inspiration: BRICS-LS-01-1.pdf 

I don't understand all those materials I suggested, but I'd be happy to discuss them.