Toward advanced combinatorics

How many edges can a graph on $n$ vertices have if it contains no triangle? A complete bipartite graph with two nearly equal parts gives $\lfloor n^2/4\rfloor$ edges. The difficult half is proving that every triangle-free graph satisfies the same bound. This is an extremal question: a construction gives a lower bound, and an argument excluding all better constructions gives an upper bound. Combinatorics also asks for exact counts, efficient constructions, and the existence of objects too complicated to specify directly. Those questions share examples, but they reward different methods.

A first collection of problems

For a broad undergraduate starting point, take Mitchel T. Keller and William T. Trotter's Applied Combinatorics, using the 2016 HTML edition for the chapter numbering here. Work through Chapter 2 on strings, sets, and binomial coefficients, then Chapter 5 on graphs. Section 2.4, Combinatorial Proofs, is especially useful: explain an identity by describing what its two sides count. You should be able to name the objects, explain the counting rule, and justify that nothing is omitted or counted twice. Algebraic simplification can check an answer, but it does not supply those explanations.

Start with induction, finite sets, and a willingness to write precise arguments. You do not need to complete real analysis or abstract algebra before counting subsets or proving elementary graph results. To skip the early counting material, give a bijective proof of $\binom{n}{k}=\binom{n}{n-k}$, derive a recurrence by dividing objects into disjoint cases, and prove that the sum of graph degrees equals twice the number of edges. If any step feels circular, work a few small examples and identify exactly what each side represents. Small cases are useful evidence, but agreement for several values does not establish a general identity.

Count, exclude, or prove existence

Enumeration offers one continuation within Keller and Trotter. Chapters 7–9 develop inclusion-exclusion, generating functions, and recurrence equations. Count permutations with forbidden fixed points, or count strings subject to a local restriction, and translate the same problem between a recurrence and a generating function. Record initial conditions. When multiplying formal power series, explain what choosing one term from each factor means combinatorially. This habit prevents a common error: finding an elegant expression that counts a slightly different class of objects. Questions involving symmetry lead to Chapter 15 on group actions, Burnside's lemma, and Pólya enumeration; add the required group theory as you reach it.

For the opening extremal problem, an alternative next text is Yufei Zhao's Graph Theory and Additive Combinatorics: Exploring Structure and Randomness, in the author-posted manuscript. Section 1.1 proves Mantel's theorem by two methods. Read one proof, close the text, and reconstruct both the bound and the equality example. Then compare the second proof to see what information it organizes differently. This is an advanced continuation: later chapters call on algebra, analysis, linear algebra, and probability. Enter after basic graph proofs are comfortable, rather than treating the apparent simplicity of the problem statement as a measure of the whole book's difficulty.

There is also an existence route. Keller and Trotter's Chapter 11 introduces Ramsey theory and the probabilistic method. A random construction can prove that an object exists even when no particular outcome has been selected. Begin by calculating an expectation or bounding the probability that a bad event occurs. Identify the probability space and justify every use of independence; linearity of expectation itself does not require independent summands. Elementary probability is enough for initial examples, while stronger concentration tools become useful for later problems.

Choose tools for the obstruction

Choose further tools by the obstruction in front of you. Linear algebra helps with ranks, eigenvalues, and incidence structures; group actions organize symmetry; probability helps build examples; analytic estimates control asymptotic counts. Zhao's later additive chapters connect equations in sets of integers with structural and random behavior. Keep exact answers separate from asymptotic estimates, and existence separate from efficient construction. A strong next project is one problem solved in two ways, with a written explanation of why each method succeeds and what it might generalize to.

Suggest an edit · Report a correction

Original introduction: CC BY-SA 4.0.