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 2007 iii Paper 13 2 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
The claimed sufficient condition is false for the printed all-colours requirement. This is a polychromatic hypergraph colouring problem, which is stronger than merely avoiding monochromatic edges.
For a counterexample even with , take and all four triples as edges. Every edge meets the other three, so , andAny assignment of three colours to four vertices repeats a colour on a pair. Any triple containing that pair has at most two colours. Thus this uniform hypergraph satisfies the numerical hypothesis but has no required colouring. A single two-vertex edge would already provide a smaller counterexample if is allowed.
Here is the correlation graph of events argument that correctly applies to the printed colouring definition. Colour each vertex independently and uniformly with three colours, and let be the event that edge misses some colour. For , the inclusion-exclusion principle givesJoin two bad events when their edges intersect. This is a dependency graph of events, hence also a correlation graph of events, of maximum degree at most : each depends only on colours on , which are jointly independent of the colours on all disjoint edges. Precisely, the symmetric Lovász local lemma says that events of probability at most with such a graph have positive simultaneous avoidance probability whenever . It follows from the asymmetric form , taking for and using ; the case is direct independence.
Thus a valid replacement sufficient condition isor the simpler, stronger condition . Under either replacement, avoiding all gives exactly the requested polychromatic hypergraph colouring. For infinitely many vertices, finite subfamilies can be coloured and compactness of the product of three-point spaces extends this to all constraints; positive simultaneous avoidance probability is only asserted for finite families. The printed bound cannot be justified by substituting monochromatic-event probabilities for missing-colour probabilities.
Past exam of the mathematics course of the University of Cambridge 2007 iii Paper 12 4 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
View a set family as a set of vertices of the Boolean lattice. The operation acts independently on each pair , where : it keeps a full or empty pair and moves a sole upper member down. Thus downward coordinate compression preserves cardinality.
Fix a tracing set . If , compression leaves the trace of a set family on unchanged. If , write for the two sections of the old trace, according to absence or presence of . The absent- section of the new trace is . Its present- section is contained in : an upper member survives only when its lower partner was also present in the original family. ConsequentlyIn particular, downward coordinate compression cannot create new set shattering.
Repeatedly apply any changing downward coordinate compression. Each change strictly decreases , so the process terminates at a down-set with the same cardinality and with no larger trace on any . The Sauer-Shelah lemma says that a family shattering no -element set satisfiesIndeed, the compressed down-set also shatters no -element set. If it contained any member of size at least , all subsets of a -subset of that member would belong to the down-set, contradicting this restriction. Every member therefore has size at most , giving the bound. Equivalently, VC dimension at most gives size at most . The family of all sets of size at most attains this bound.
There is a different extremal example when . Toggle a fixed coordinate in the family of sets of size at most two:The symmetric difference is a bijection, so this family has members. On each tracing set , it simply toggles coordinate if ; thus it preserves trace cardinality and set shattering. A triple has seven trace patterns, not eight. The new family differs from the original one because it contains . For the specified cardinality is , so the entire power set is the unique family of that size; the different example requires .
For the final bound, let count pairs both in the family. Deleting coordinate identifies precisely these pairs, soSuppose every deletion lost at least two members, so for every . The trace inequality and preservation of cardinality show that after downward coordinate compression. The down-set contains the empty set and every singleton. For each , its second edge in direction has an upper endpoint of size at least two. Downward closure then supplies a pair . The pairs in therefore cover all coordinates, so at least pairs are needed. This proves two cube edges in every direction force many vertices:Taking the contrapositive gives the required answer:The threshold is sharp for every . Take the empty set, all singletons and pairs covering every coordinate. For even , use the disjoint pairs ; for odd , pair the first coordinates and add . This down-set has exactly members and at least two edges in every direction, so every -coordinate trace has size at most . Adding further members preserves those pairs and therefore preserves the failure whenever a larger cardinality is feasible. For , the putative counterexample cardinality is three, exceeding the size of the Boolean lattice; the sharpness construction naturally starts at .
Past exam of the mathematics course of the University of Cambridge 2007 iii Paper 12 3 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
For , define the complete-intersection candidate familiesEach is a t-intersecting family, since two members have at least common points in the distinguished block. The cardinality form of the Ahlswede-Khachatrian theorem isA binomial coefficient is taken as zero if its lower argument is outside its usual range.
First reduce to left-compressed set families. One of the coordinate shifts of a set family, with , replaces by only when the target set is absent. It preserves cardinality and the property of being t-intersecting. To verify the latter, a pair of newly moved sets has the same intersection size as its old pair. If just one member moves and its intersection with a retained member decreases, the retained member contains and avoids . Its own shifted partner must already have belonged to the old family, otherwise it would have moved too. The old moved member and that shifted partner have the same intersection size as the allegedly bad new pair, a contradiction. Repeating changing shifts terminates because the sum of all point labels strictly decreases.
A generating family for a uniform set family is a collection of sets of size at most such thatUse the following small-support generating lemma for extremal intersecting families, the auxiliary result permitted here. If , , andthen every maximum-cardinality left-compressed set family that is t-intersecting has a generating family contained in . Reflection gives the corresponding right-end supporting interval for a right-compressed optimum. The inequality is strict.
The main ideas of the generating lemma are as follows. When , its hypothesis forces , making the support conclusion automatic. Otherwise . Choose inclusion-minimal compressed generators minimizing their furthest point . Partition generators containing by size. A pair whose intersection would fall below on deleting must fill and have sizes summing to . Compare the two replacements associated to those complementary size classes; counting their rank- extensions makes one replacement larger unless the sizes are equal. In that balanced case, put , where is even. Delete from generators avoiding a suitably chosen earlier point. Averaging supplies a proportion at least . The ratio of the guaranteed gain to the loss isIt exceeds one precisely when , implied by the stated hypothesis. This contradicts maximal cardinality; redundant generators are removed after each replacement. These extension counts explain both the support bound and its strict threshold.
We also need the compatibility bound for complementary generating families, which has a short direct proof. Write . If generates and generates , thenOtherwise contain their union in a set of size . Under this size is at least both and . Extend inside to sets of those respective sizes. Then , whereas , a contradiction.
The easy parameter ranges can now be disposed of. If , every two -sets intersect in at least points, and . This is a candidate value too: choose , for which the minimum possible intersection with is exactly . If and , Question 1 gives . If , complementation of uniform intersecting families turns the problem into an intersecting family of rank , on a ground set of size at least twice that rank. Question 1 then giveswith equality from that candidate, the family of all -sets avoiding the last point.
It remains to treat and . Put andSince , there is with . Take a maximum left-compressed set family . Its complement family is right-compressed and has parametersIt is maximum for those parameters, since complementation is a cardinality-preserving bijection between the two intersection problems. Put . The strict inequality impliesFor , multiplying out reduces this to , exactly ; for it reduces to . The reflected generating lemma therefore gives generators for supported on
First suppose . The original generating lemma supplies generators supported on . If every has size at least , then . The same conclusion follows if every has size at least : every complement member then has at least that many points in , forcing each original member to have at least points in . If neither condition holds, choose and . Thencontradicting the proved compatibility bound. Thus , and the candidate itself attains equality.
Now suppose . The earlier exceptional case excludes . Since , , so the original generating lemma gives supported on , while the same dual argument still gives supported on . If all have size at least , then . If all have size at least , then . Otherwise a pair with and violates compatibility. HenceBoth candidates are available, so this proves the maximum formula also at the boundaries.
For completeness, their equality and the maximizing intervals follow from a direct count, with no appeal to the theorem. Moving from to adds sets containing both new coordinates and exactly old block points, and loses sets containing neither new coordinate and exactly old block points. ThusIn the nontrivial range, the gain-to-loss ratio is . It exceeds, equals or falls below one according as is below, equal to or above . Since the thresholds decrease with when , the largest candidate is in each strict interval and the consecutive candidates tie at . This completes the proof of the cardinality theorem in every parameter range.
Past exam of the mathematics course of the University of Cambridge 2007 iii Paper 12 2 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
There is a genuine qualification missing from the printed bound. With , the family of three singletons has distinct intersections of size zero, which is not congruent to modulo . Nevertheless its size is three, whereas . Thus that bound cannot hold without a restriction on the parameters. The valid prime-power modular intersection bound isIn particular the printed form holds when .
Put with a prime number, and . If , the corrected bound is simply the total number of -sets. Assume henceforth . For an integer , consider the residue detectorFor nonnegative upper arguments, the Lucas theorem and the fact that every base- digit of equals show that is one when and zero otherwise. The assertion also holds for negative upper arguments, using integer-valued generalized binomial coefficients. Indeed the coefficient of in is periodic in the integer exponent modulo : in characteristic , , so multiplying even a formal power series by does not change coefficients of degrees below . Reduce any exponent modulo to obtain the stated detector.
For each , apply that detector to . Its evaluations on form the identity matrix, since the diagonal intersection is and every off-diagonal intersection has a different residue. The detector is represented on Boolean vectors by the multilinear polynomialTo check this expression, evaluate at the characteristic vector of : summing by gives by the coefficient identity for .
Here is the necessary low-degree evaluation rank on a uniform layer, with care about characteristic . Let be the integer incidence matrix whose rows are subsets of size at most , whose columns are all -sets , and whose entries are . Over the rational numbers, for its row satisfiesThus its rational matrix rank is at most . Every larger square minor has integer determinant zero; reducing those determinants modulo gives too. This argument does not divide by a potentially zero element of the finite field. The identity evaluation matrix factors through these incidence rows, so its rank is at most . This proves the qualified bound.
Choose the two-applications alternative. First, the polynomial method in combinatorics yields a constructive lower bound for a diagonal Ramsey number. Let be prime, set , and use all -subsets of as vertices of a complete graph. Color a pair red when its intersection size is modulo , and blue otherwise. A blue clique has size at most by the proved bound with modulus . In a red clique, all distinct intersections belong toFor each vertex of that clique, the polynomial vanishes at all the other vertices' characteristic vectors and is nonzero at its own. Replace repeated powers by on Boolean vectors. Its degree is at most , so the rational version of the same incidence-rank argument bounds a red clique by as well. Therefore this two-coloring has neither color containing a clique of size , andThe usual estimates give and . Thus along this explicit sequence the diagonal Ramsey number exceeds for some absolute . This is substantially larger than any fixed power of .
Second, obtain an exponential lower bound for the chromatic number of Euclidean space. Let , and join two -subsets exactly when their intersection has size . An independent set in this graph avoids that intersection. Among the possible distinct intersection sizes , the only one congruent to modulo is . Hence every independent set has size at most . Embed each vertex as in Euclidean space. Thenso the graph's edges have exactly Euclidean distance one. Each color class must be an independent set, givingThe Stirling formula makes the logarithm of this ratio , where . Since , this is an exponential dimensional lower bound for the chromatic number of Euclidean space. Both applications lie in the valid parameter range of the proved modular bound.
Past exam of the mathematics course of the University of Cambridge 2007 iii Paper 12 1 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
For a nonempty -uniform set family , write its cardinality in its unique greedy binomial representationThe Kruskal-Katona theorem gives the exact minimum size of its lower shadow:Equality is attained by the colexicographic initial segment of the same cardinality. The empty family has empty shadow. In colexicographic order, precedes exactly when the largest point of belongs to . The greedy expansion exists by choosing each top argument as large as possible; Pascal's identity makes the next residual less than , forcing the next top argument below . This also proves uniqueness.
Here is a proof by UV-compression of the theorem, including the step that controls the lower shadow. For disjoint nonempty sets of equal size, let replace a member containing and avoiding by only when is absent. Other members stay. This UV-compression preserves cardinality. Allow only , and at each step choose a changing compression with as small as possible. Every smaller allowed UV-compression then fixes the current family.
For such a chosen UV-compression, we proveFirst let be a new shadow member, not in . It has the form for a moved member . If , choose with when . The smaller UV-compression with sets fixes , and therefore its target already belongs to . This would put in the old shadow, a contradiction. For the same target is simply , giving the same contradiction without a compression. Hence . Now is an old shadow member whose compression target is ; since was absent, it appears in the compressed shadow.
It remains to check that a surviving old shadow member is not removed on the right side. Such a removal could occur only for containing , avoiding , with absent from the old shadow. A witness in the compressed family must be a retained old member, since newly moved members avoid . If , retention of the eligible member forces its target to be in the old family, contrary to the absence of from its shadow. If , the smaller fixed compression just used forces into the old family; for this is itself. Again there is a contradiction. This proves the containment, and hence the chosen compression cannot increase lower shadow cardinality.
Each change strictly decreases the integer potential . The procedure therefore terminates. Its terminal family is an initial segment of colexicographic order: otherwise take an absent earlier set and a present later set . The choice is an allowed changing compression. Thus UV-compression transforms into the colexicographic initial segment of the same size without increasing its lower shadow.
Finally compute that shadow. The first block comprises all -subsets of and contributes shadow members. The next block has maximum point and its remaining points form a smaller colexicographic initial segment. Shadow members omitting are already in the first block's shadow; those containing it are counted by the lower shadow of that smaller initial segment. Recursion through the binomial representation gives precisely the displayed sum. This completes the proof.
To deduce the Erdős-Ko-Rado theorem, let and let be an intersecting family. Put and take the complement family . Its rank- lower shadow, obtained by deleting points, is disjoint from : membership of in that shadow would give for some . If , iterating the proved Kruskal-Katona theorem gives this shadow at least as many members as the corresponding colex shadow. The colex family contains every -set of and a further -set containing . Its rank- shadow therefore contains every -set of and at least one more -set containing . This applies also when , with no shadow operation. The two disjoint families would consequently have total size greater thana contradiction. Thus , attained by all -sets containing a fixed point.
For nonisomorphic colex shadow minimizers of rank two, take and . Its shadow has four singletons, as does the initial four-set colex segment . The first family is the edge set of a cycle graph; its four point degrees are all two. The second has point degrees , so no permutation makes them isomorphic.
For rank three, take andThe first lower shadow comprises the three pairs in and the six pairs joining that set to . The second shadow comprises every pair on except . Both therefore have size nine. Their point-degree multisets are respectively and , so again the two families are not isomorphic. These examples can be embedded in larger ground sets by adding unused points.
Past exam of the mathematics course of the University of Cambridge 2007 iii Paper 11 6 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
A hyperbolic Riemann surface in potential theory is a noncompact Riemann surface admitting a positive Green function on a Riemann surface. With pole , this is a positive function harmonic off , having local form plus a harmonic function in a coordinate , and obtained as the minimal such positive function by exhaustion. This is a noncircular definition for the present proof. For a simply connected surface it is equivalent to disk conformal type; for arbitrary surfaces potential-theoretic hyperbolicity and disk universal-cover type should be distinguished.
The unit disk is an example. At pole zero its function is : it is positive in the punctured disk, harmonic there, has the correct logarithmic singularity, and tends to zero at the boundary. If another positive function has the same singularity and is harmonic elsewhere, subtract and apply the maximum principle for harmonic functions on disks of radius ; the boundary lower bound is . Letting shows that the other function dominates . Thus is indeed the positive Green function on a Riemann surface. At a general pole it is
Here is a Green-function exhaustion proof of disk uniformization. The main analytic idea is to build conformal maps on bordered disks from their Green functions and pass to an extremal limit. The positive global Green function prevents that limit from becoming constant.
First exhaust the noncompact simply connected surface by relatively compact domains containing , each with a smooth Jordan boundary. This topological step does not use conformal uniformization: take regular neighborhoods of finitely many coordinate disks covering successive compact sets and fill bounded complementary components. Simple connectedness and the Jordan curve theorem make the filled neighborhoods topological disks; enlarge them to be nested.
Each has a zero-boundary Green function on a Riemann surface . One analytic construction, independent of conformal uniformization, is as follows. Equip the compact bordered domain with a smooth conformal metric. Multiply by a smooth cutoff function equal to one near and zero near the boundary; call the result . Distributionallywhere is smooth and supported away from . Solve with zero boundary data. This auxiliary Dirichlet problem can be obtained by minimizing over functions with zero boundary trace: the Poincaré inequality gives coercivity, minimization in a Hilbert space gives a weak solution, and interior and smooth-boundary elliptic regularity give a smooth solution. Then is harmonic away from , has the logarithmic pole, and vanishes at the boundary. It is positive by the maximum principle for harmonic functions, applied after removing a sufficiently small circle around its positive pole. This construction uses ordinary linear elliptic existence, not the desired uniformization theorem. Equivalently, the same bordered-domain Green functions can be constructed by the Perron method for the Dirichlet problem using local logarithmic barriers.
On choose local harmonic conjugates . Their period around the pole is , and every closed loop is homologous to an integer multiple of that loop. Thereforeis a single-valued holomorphic function. It extends across with one simple zero and has no others. Since , ; since on the boundary, there. Thus is proper. For any , choose a smooth interior contour sufficiently close to the boundary that everywhere on it. The contour surrounds and all possible preimages of , because throughout a thin boundary collar. By Rouché's theorem, has the same number of zeros inside as , namely one. Hence is onto and one-to-one, with nonzero derivative: it is a biholomorphism from to the disk.
Write near Multiply by a unit constant so that, in the fixed coordinate, . Domain monotonicity gives : their difference is harmonic even at and nonnegative on . The global positive Green function on a Riemann surface similarly majorizes every . Comparing the regular parts shows that increases and is bounded above by the finite regular part of at . Consequently
On each fixed compact subdomain, the are eventually bounded holomorphic functions. Montel theorem and a diagonal subsequence therefore give a locally uniform convergence limit with and . The maximum modulus principle keeps its values strictly inside the disk. It is injective: for fixed , the functions have no zeros away from ; Hurwitz's theorem implies that their nonconstant limit has no other zeros. This is the locally uniform limit of univalent functions argument.
There is also an extremality property. For any holomorphic function with , the function is a disk self-map fixing zero. The Schwarz lemma gives . Passing to the limit yields .
Finally suppose omits . Necessarily . Apply the disk Möbius transformation . The nowhere-zero function has a global holomorphic logarithm because is simply connected, hence a holomorphic square root . It maps into the disk and . Normalize it by setting , so . Direct differentiation givesThe strict inequality follows from . This contradicts extremality. Therefore omits no point, and we conclude
Past exam of the mathematics course of the University of Cambridge 2007 iii Paper 11 5 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
On a connected Riemann surface , a Perron family of subharmonic functions is a nonempty family of real continuous subharmonic functions closed under pairwise maxima and under harmonic lifting on every relatively compact coordinate disk. A harmonic lifting of a continuous subharmonic function replaces its values inside such a disk by the harmonic Poisson integral of its boundary values, leaving the function unchanged outside. Harmonic comparison shows that the lift dominates the original function. The lift is continuous and remains subharmonic by harmonic comparison across the circle.
Write . Because the family is nonempty and its members are finite, cannot be minus infinity. Suppose first , and choose a relatively compact coordinate disk containing . Choose approaching at . Lift on to get , and recursively lift to get . These are members of the family, harmonic on , and increasing. Also .
The nonnegative harmonic functions are bounded at . The Harnack inequality for harmonic functions, on chains of compact subdisks, bounds them uniformly on every compact subset of . The Poisson integral then bounds their derivatives on smaller subdisks. Compact convergence and the mean value property show that their increasing limit is finite and harmonic; denote the limit of by .
Fix an arbitrary , and let be the lift of on . These functions increase, are harmonic on , and satisfy . They are bounded at , so the same Harnack inequality for harmonic functions argument gives a harmonic limit . At , , whereas on . The nonnegative harmonic difference has an interior zero, so the strong maximum principle for harmonic functions gives . Since , we have . Taking the supremum over gives , and gives the opposite inequality. Thus on .
The finite locus of is open by this argument. It is also closed: if a point is a limit of finite points, choose a coordinate disk around it and a finite point in that disk; the preceding argument applied with that finite point shows that is finite on the entire disk. Connectedness now proves the dichotomyBoth occur. The family of all continuous subharmonic functions bounded above by zero is a Perron family of subharmonic functions, since the maximum principle for harmonic functions keeps every lift below zero; it contains zero, so its supremum is zero. The family of constant functions with positive integer values is also a Perron family of subharmonic functions, and its supremum is everywhere infinite.
For the final application, the radius must enclose the evaluation point. For setThis is the harmonic lifting of a continuous subharmonic function on the radius- disk. Hence there. If , on the radius- boundary, so harmonic comparison gives throughout the smaller disk. The increasing limit is either everywhere infinite or finite and harmonic, by the preceding Harnack argument and propagation across overlapping disks. In the finite case it dominates . Any harmonic majorant of dominates by boundary comparison and therefore dominates their limit. Thus the precise conclusion isprovided a finite harmonic majorant exists. This is the least harmonic majorant by expanding disk lifts.
There are two necessary qualifications to the printed formula. First, the supremum cannot include . For example, if and , the kernel has normalized integral for and for . The displayed integral is consequently in the first case and in the second. The unrestricted supremum would be , although the least harmonic majorant is ; at the kernel is undefined. Second, a finite harmonic majorant need not exist. The continuous subharmonic functionhas . If were harmonic, its centered circular means would equal and dominate for every , an impossibility. In this case the limit formula holds only in the extended sense, with value and no finite least harmonic majorant.
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





