Topics (384k) Articles (398k) Users (410) Discussions (242) Comments (383) Files (13k) New article
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 111 3 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Use the following normalization for Fourier analysis on a finite group. Choose one unitary irreducible representation from each equivalence class, including the trivial representation. For a scalar function , putThis convention uses , rather than , in the Fourier transform on a finite group; it makes the normalized convolution on a finite group preserve multiplication order.
The needed representation theory consists of Maschke's theorem and unitarization of a finite-group representation, together with the Schur orthogonality relations:The regular representation contains copies of each , so . Thus the scaled matrix coefficients , and also their complex conjugates, form an orthonormal basis of all scalar functions on . These facts imply Fourier inversion on a finite group and the Parseval identity on a finite group in the formsand henceIn particular, the transform is an isomorphism onto the direct sum of the matrix algebras , with the displayed weighted Hilbert-Schmidt inner product.
Define the normalized convolution on a finite group bySubstituting and using the group representation identity yields the convolution theorem on a finite groupUnlike normalized convolution on a finite group on an abelian group, this product need not commute. If , then . For left translation of a group function and right translation of a group function and ,For an abelian group, every irreducible representation is one-dimensional; this reduces to Fourier analysis on a finite abelian group with characters relabelled by their inverses. These formulas establish the basic scalar theory, with all normalizations and multiplication orders fixed.
Now suppose every nontrivial irreducible representation has . If is a mean-zero function, its component at the trivial representation is zero. The Parseval identity on a finite group gives, for each other ,Using the convolution theorem on a finite group, the Hilbert-Schmidt norm inequality , and the Parseval identity on a finite group once more gives the product mixing in a quasirandom group estimateWrite for the subset density values of , respectively, and let , be balanced subset indicators. Since both are mean-zero functions, . Their squared norms are and . Also , so the Cauchy-Schwarz inequality yieldsIf , the final bound is strictly smaller than . Thus the normalized number of pairs with is positive. Equivalently,This is the desired conclusion for a quasirandom group; the strict inequality ensures positivity rather than merely a nonnegative lower bound.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 111 1 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
A sufficient absolute constant is . The proof is a density increment argument for a cap set over the finite field .
First work in , write , and let be the indicator function of a cap set of subset density . All expectations below are uniform. In characteristic three, a solution of having two equal entries has all three equal. Consequently the normalized linear configuration count isSet and use Fourier analysis on a finite abelian group withThe orthogonality of roots of unity and the Parseval identity on a finite group giveIf , then for a cap set andThus some nonzero finite abelian Fourier coefficient has magnitude at least .
For this , let be the subset density of on the affine subspace , for . These three affine subspaces have equal cardinality, andAmong three directions separated by , one makes an angle at most with any given complex number. Hence . Restricting to that hyperplane gives the hyperplane density increment for cap setsTranslate the affine subspace to its underlying vector space. This preserves the cap set property: translating a triple by changes its sum by . The same argument can therefore be iterated.
For completeness, the density increment iteration gives an explicit uniform bound. If , the hypothesis is impossible. Suppose and a cap set has . For every integer , its remaining dimension is at least , and its current subset density is at least . ThusThe last inequality holds at and remains true as increases: the successive ratio of is for . At each step, as long as the subset density remains at most one,After steps this would implya contradiction. The endpoint already contradicts the cap set property in positive dimension. This proves the claimed existence of three distinct points and the Meshulam bound for cap sets.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 110 5 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
There is a genuine error in the printed threshold. With , its only nontrivial requirement is that some two consecutive classes contain at least one vertex of the triple. Every triple meets some class, so every triple qualifies. For example, when , the printed construction is the complete 3-uniform hypergraph, of edge density , whereas the claimed density is . Thus the stated edge-count assertion is false even in a nondegenerate parameter range.
The intended cyclic Turán covering construction, which gives the claimed density and the stated lower bound, uses threshold , in the natural range . We solve this repaired version explicitly. Denote it by to keep it separate from the literal printed construction.
A cyclic prefix argument gives the covering property. We first prove the relevant cycle lemma. If integers satisfy , exactly one cyclic starting position has every nonempty partial sum strictly positive. Existence follows by starting after the last minimum among the proper partial sums . Subsequent nonwrapped sums are strictly above that minimum, and wrapped sums add the total . For uniqueness, if two starts split the cycle into arcs with sums and , both positive, their integrality would require and , a contradiction.
Take any vertices and let count them in class . The increments sum to one. The cycle lemma gives a start for which the first classes contain at least vertices, for every . Take the first vertices encountered from that start in class order. The first classes already contain at least vertices; the chosen vertices therefore satisfy all the repaired prefix inequalities. HenceEvery repaired edge also satisfies the weaker printed inequalities. Thus this argument proves the covering assertion for the printed construction too, although it cannot repair its false edge count.
Count the repaired edges by labelled class assignments. Put . For a fixed cyclic start, an edge satisfying the repaired inequalities has all vertices in its first classes. Assign labelled vertices to these positions. There are assignments in total. Their occupancy counts satisfy ; the cycle lemma says exactly one of their cyclic starts has the required prefixes. Rotational symmetry therefore gives exactly good assignments for a specified start.
We must check that summing over the starts does not count an edge twice. Suppose two starts cut the circle into arcs of lengths and . If an arc has length at most , goodness of its starting point forces that arc to contain at least its length plus one vertices. If its length is greater than , it contains all vertices, while the other good start demands vertices in the disjoint complementary arc, impossible. If both lengths are at most , their combined demand is at least vertices, again impossible. Thus a repaired edge has a unique good start.
There are consequently good assignments of class labels to labelled vertices. For any such assignment, balanced class sizes givewhere is the falling factorial. Divide the total count of ordered distinct vertices by . For fixed ,This is precisely the edge density requested, but for the corrected construction.
Pass from covering to a forbidden-hypergraph clique construction. Use balanced classes in and take its hypergraph complement. Every -set contains an edge of , so the complement contains no complete -uniform hypergraph . The preceding count givesHere Turán density means for a fixed -uniform forbidden hypergraph; the limit exists because these normalized extremal densities are nonincreasing under averaging over smaller vertex subsets.
A corresponding classical upper bound is the de Caen bound for hypergraph Turán density:Equivalently, an -uniform covering hypergraph in which every -set contains an edge has asymptotic edge density at least . Its proof recursively counts complete subhypergraphs by their one-vertex extensions. Double counting the extensions and applying the Cauchy-Schwarz inequality to common extension neighbourhoods gives a lower bound for the ratio of successive hypergraph clique counts. If the missing-edge density were smaller than , those bounds would force a positive number of -vertex hypergraph cliques, a contradiction. Applying the resulting covering bound to the complement of a -free hypergraph gives the displayed upper bound. This incidence argument supplies the extra factor beyond the simpler direct count of one covering edge in each -set, which alone yields only .
The lower bound is therefore valid via , while the printed enumeration cannot be proved with threshold . Both the counterexample and the necessary repair are part of the solution, rather than a silent change of the definition.
The general upper bound is recorded, for example, in Turán densities of some hypergraphs related to complete uniform hypergraphs.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 110 4 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Assume the uniform hypergraph has positive average hypergraph vertex degree , so . Its hypergraph degree measure isIt is a probability measure on the vertex set; vertices of degree zero have measure zero. If the hypergraph is regular, it equals . An edgeless hypergraph has no normalized degree measure of this form and must be treated separately.
Every edge entirely in contributes to the degree sum over , giving the upper bound. For the lower bound, an edge entirely in contributes , and any other edge contributes at most . ThereforeTogether these give both degree-measure inequalities:In particular every hypergraph independent set has measure at most , which explains why degree measure can control containers even in very nonregular hypergraphs.
A sufficient container theorem. For every fixed , there are positive constants such that if andthere is a family of hypergraph containers covering all hypergraph independent sets, each with . Each container is determined by a container fingerprint with and . In particular, for sufficiently small , the number of containers is at most . We will give an algorithm and constants establishing this version.
The golden rule for container algorithms is that reconstruction may depend on the small container fingerprint, but never on unrevealed information about the independent set. When a deterministic test calls for inspecting a vertex, a positive membership answer is recorded in the container fingerprint, while a negative answer permits its exclusion from the container. All tests and all state updates must be reproducible using that container fingerprint. Choosing tests that permit only a few positive answers then yields few containers.
Here is an explicit implementation with controlled links. Use the fixed order , parameters , and a bound on nonsingleton codegrees. Let count incidences with multiplicity in the -uniform multihypergraph . Define thresholdsA saturated subset is one whose current degree has reached its threshold.
- Put ; start and their saturation families empty for . Put , , and .
- At the current vertex , for every compute the multisetRetain the multiplicity from . Compute all these multisets before modifying any at this vertex.
- Inspect if and either or for some . If it is not inspected, leave in and continue.
- On inspection, if , remove it from . If , put it in and retain it in .
- For a vertex put in , add the full multiset to for every . Then insert into every nonempty future subset with and . Once saturated, a subset stays in .
- Advance to the next vertex. To reconstruct from , use exactly the same state evolution, replacing the inspected membership test by .
Every generated edge of extends to an original edge by adding earlier vertices from . Thus, for a hypergraph independent set , no singleton generated in can be a member of . In particular an inspected vertex in cannot give a positive membership answer. All other positive answers are recorded. The golden rule for container algorithms now proves that the reconstructed container contains and that its state depends only on .
Control the possible overshoot at saturation. The multisets are added in batches; merely claiming would be wrong. In the last batch that increases , the set was not yet saturated, and the batch comes from some vertex . Its contribution is at most . HenceInduction downwards from yields, for ,Indeed the two terms in the last-batch bound have coefficients and with the same power of . Applying this nonsingleton bound to gives the singleton estimateSumming over , using , proves the requested estimate at every stage of the algorithm:It applies with multiplicities; replacing the multisets by sets in the accounting would invalidate the argument.
Check that the container fingerprint is small and the container loses positive measure. Assign each positive inspected vertex to one index witnessing its test. Its added link batch has size at least . Distinct batches count separately in the multiset. Since , the preceding bound givesThe second inequality uses for every .
For completeness, the loss of measure can be verified by a short incidence count. Put and . Every saturated singleton belongs to . Partition by its earliest vertex. An earliest vertex in accounts for at most incidences. For any other earliest vertex, the unsaturated link has size less than ; the remaining edges meet some saturated subset of .
For a saturated nonsingleton , the degree bounds imply . For a saturated singleton the corresponding bound is . Every multiedge of has fewer than nonempty subsets. These observations giveFor , all saturated subsets are singletons in , so directly summing their degrees givesSince , these inequalities prevent from having arbitrarily small measure. To make the constants explicit, letIterating the displayed inequalities gives , hence whenever . Also , so gives , while . ThereforeOne can take in the stated container fingerprint bounds. Counting subsets of size at most gives the asserted bound on the number of containers. Thus the explicit algorithm produces the family promised by the sufficient hypergraph container theorem, as well as the required intermediate degree estimate.
For the standard weak-threshold formulation, see Online containers for hypergraphs. The constants above come from the explicit incidence estimates given here.
For , no multilevel construction is needed: take the sole container to be the vertices that are not singleton edges. It contains every hypergraph independent set and has degree measure zero when ; its fingerprint is empty. The requested degree-sum inequality follows directly from the definition of .
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 110 3 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Think of a vertex of this hypergraph as an edge of the complete graph on . A hyperedge is the edge set of one -vertex clique. A fixed pair belongs to a clique precisely when its other vertices are chosen from the remaining , givingFor a set of graph edges, let be the number of their distinct endpoints. If , no -clique contains them and the codegree is zero. Otherwise its other vertices may be chosen freely, soFor , distinct edges have at least three endpoints, and all edges lie among the possible pairs. Thus and . In particular,This also identifies why the relevant exponent is .
For fixed and , the ratio of the two binomial coefficients satisfies for all sufficiently large , with one constant valid for every . For ,For any fixed , choose so large that the last bound is at most for every . Zero codegrees satisfy the bound automatically. The asserted small-codegree condition therefore holds uniformly. Its domain is the nonsingleton sets considered above: for a singleton, , so the assertion with arbitrary would be false.
A family of hypergraph containers is a collection of vertex subsets such that every hypergraph independent set of the hypergraph is contained in some . Here a hypergraph independent set is exactly the edge set of a -free graph on .
We use the following edge-sparse form of the hypergraph container theorem. For fixed uniformity and , there are constants such that an -uniform hypergraph on vertices with positive average hypergraph vertex degree , sufficiently small, andhas a family covering its hypergraph independent sets withOne obtains this form by iterating a degree-measure hypergraph container theorem, recording small container fingerprints at each step. To ensure the requested strict edge inequality, apply it with .
For our clique hypergraph, , and . The established codegree bound permits this choice of , andEvery container, viewed as an ordinary graph, has at most copies of .
We also use clique supersaturation: for each fixed , graphs with at least edges have at least copies of , for some and all sufficiently large . For clarity, this follows already from the Erdős-Stone theorem: choose a fixed sample size with . A uniformly sampled -set has expected value of the edge count above this bound by at least , forcing a positive proportion of samples to contain a clique. Counting each clique's extensions to -sets then gives the claimed bound.
Choose smaller than the corresponding supersaturation constant after converting to . Each container has fewer than ordinary edges. Every -free graph is a subgraph of one of these containers, so their number is at mostConversely, every subgraph of a balanced Turán graph with parts is -free, giving at least possibilities. Letting be arbitrarily small proves the enumeration formula:
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 110 2 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
For disjoint nonempty vertex sets , write . The regular pair of vertex sets is -uniform when every , with and satisfiesThis is also called an -regular pair.
Count transversal cliques by maintaining common neighbourhoods. For there are exactly copies, so the claim is immediate. For the hypotheses are vacuous if ; assume . SetAfter choosing vertices in the first classes, let be their common neighbours in each later class. We maintain . In a regular pair, whenever , fewer than vertices of have fewer than neighbours in : otherwise those bad vertices, together with , contradict regularity. There are at most future classes, so their union excludes at most candidates from . At least choices remain, and each maintains the stated bound for all new common neighbourhoods.
Making these choices through all classes gives at least transversal cliques. Different selections give different vertex sets, since the classes are disjoint. ConsequentlyAll constants depend only on , not on .
The Szemerédi regularity lemma states that for every and integer there exist such that every graph of order has a partition with , , equal-sized nonexceptional classes, and at most irregular unordered pairs of classes.
Apply the partition to prove clique removal. For , choose , , and a regularity parameter small enough for the preceding counting argument at density . The Szemerédi regularity lemma supplies . Delete all edges incident with , inside individual classes, between irregular pairs, and between regular pairs with density below . If the common class size is , the number deleted is at mostA surviving would have its vertices in distinct classes; every pair of these classes is regular and has density at least . The counting result would then give at least copies in the original graph. Since , choose, for example,This would exceed , contradicting the assumed copy count. Thus fewer than cliques can be destroyed by removing at most edges, leaving no . This is the clique removal lemma.
For , take : a graph of order always has copies of , so the hypothesis is impossible. The assertion in that degenerate case is vacuous, rather than an edge-removal procedure capable of deleting vertices.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 110 1 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
The Erdős-Stone theorem says that, for a fixed graph with chromatic number ,The lower bound comes from the balanced Turán graph with parts; the theorem supplies the matching asymptotic upper bound. Here and below, all forbidden graphs and blow-up parameters are fixed as .
First obtain an almost spanning, almost complete multipartite core. Put . We give the stability argument, rather than infer pointwise degree bounds by differentiating an asymptotic edge-count formula. Suppose first .
We need two elementary ingredients. First, positive homomorphism density of forces a fixed complete multipartite graph . To see this, perform vertex cloning in a graph, replacing one vertex by independent twins. Conditional on the images of the other vertices, its contribution to the homomorphism density changes from a number to ; Jensen inequality gives . Duplicating each original vertex therefore givesA positive lower bound on the right supplies a positive proportion of all maps of the blow-up. Only maps fail to be injective, so for large at least one map is an embedding. Consequently a -free sequence has copies of . The clique removal lemma, proved in the next solution, then deletes edges to give a -free graph with .
Second, we prove the required stability for -free graphs by induction on . For such a graph is edgeless. In an -vertex -free graph , take a vertex of maximum vertex degree , put and , and note that is -free. The Turan theorem and the maximum-degree bound giveIf , both nonnegative error terms are : and . The deficit in the bound for is likewise . Induction partitions into classes with a total of internal edges; adjoining gives an -class partition with the same property. Applying this to and restoring the removed edges gives such a partition of .
The number of possible crossing edges is . Since the actual crossing-edge count is within of this maximum, for every , and there are missing crossing edges. Choose so slowly that the number of vertices missing more than neighbours in other classes is . Delete those vertices and all internal edges. The remaining r-partite graph has vertices and every vertex has crossing vertex degree at least . The Turan theorem, or the size of a largest part, supplies the matching upper bound for its minimum vertex degree. ThusThis is a high-minimum-degree multipartite stability subgraph. The subgraph need not be spanning; deleting the exceptional vertices is essential. For , the spanning edgeless subgraph already proves the assertion.
Extremality forces the minimum degree. Choose . A proper -graph colouring embeds in , so every -free is also -free. By the Erdős-Stone theorem, its extremal edge count has the needed asymptotic size. The preceding proof supplies core classes of size in which every vertex misses only crossing neighbours, uniformly over the core.
Delete an arbitrary vertex from and introduce a new vertex adjacent precisely to with removed if necessary. The new graph is still -free. Indeed any new copy would use , all its neighbours in that copy would be in the specified core classes, and their set of common neighbours in has size . A vertex of this common neighbourhood outside the bounded vertex set of the copy replaces , producing an existing copy of in , a contradiction. For the new vertex is isolated and the same conclusion is immediate.
The replacement adds edges. Since has the maximum possible number of edges, . As was arbitrary and the minimum vertex degree is at most the average vertex degree,This proves the minimum degree of an extremal forbidden-subgraph graph. The replacement argument avoids the invalid implication based solely on the asymptotic formula.
A colour-critical vertex also bounds the maximum degree. Suppose a vertex of has for some fixed . Since the core omits only vertices and all its classes have size , has at least neighbours in each . Otherwise, even counting every vertex in all other classes and outside the core would give too small a vertex degree.
Inside these neighbourhood sets, greedily choose a fixed number of vertices in each class. Every previously chosen vertex excludes only crossing nonneighbours, so each next candidate set still has positive linear size. This produces inside . A proper -graph colouring of embeds it in that complete multipartite graph; map to . All required incident edges exist, so this embeds , a contradiction. The case simply uses enough neighbours to embed the edgeless . Hence , and the average-degree lower bound completes the answer:
Pinned article: Introduction to the OurBigBook Project
Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.
Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!
Intro to OurBigBook
. Source. We have two killer features:
- topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculusArticles of different users are sorted by upvote within each article page. This feature is a bit like:
- a Wikipedia where each user can have their own version of each article
- a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.Figure 1. Screenshot of the "Derivative" topic page. View it live at: ourbigbook.com/go/topic/derivativeVideo 2. OurBigBook Web topics demo. Source. - local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
- to OurBigBook.com to get awesome multi-user features like topics and likes
- as HTML files to a static website, which you can host yourself for free on many external providers like GitHub Pages, and remain in full control
Figure 2. You can publish local OurBigBook lightweight markup files to either OurBigBook.com or as a static website.Figure 3. Visual Studio Code extension installation.Figure 5. . You can also edit articles on the Web editor without installing anything locally. Video 3. Edit locally and publish demo. Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension. - Infinitely deep tables of contents:
All our software is open source and hosted at: github.com/ourbigbook/ourbigbook
Further documentation can be found at: docs.ourbigbook.com
Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact





