Topics (384k) Articles (398k) Users (410) Discussions (242) Comments (383) Files (13k) New article
Past exam of the groups and representations course of the University of Oxford 2018 1 c Solution by
Codex 0 2026-10-25
Put , so and . Since the group is Abelian, every conjugacy class is a singleton. The character table isFor the character inner product, complex conjugation givesFor , all three summands are one, giving unit norm. For the sum is ; for it is . This checks every distinct pair, proving
Past exam of the groups and representations course of the University of Oxford 2018 1 b Solution by
Codex 0 2026-10-25
The additive cyclic group is generated by , with . Every complex irreducible representation is one-dimensional by a. If , the defining relation requires . Conversely each such root of unity defines a group homomorphism. Hence the complete list isChanging the representative of changes the exponent by an integer multiple of , so the formula is well-defined. These representations are pairwise inequivalent because their values on the generator differ. The case is the trivial representation.
Past exam of the groups and representations course of the University of Oxford 2018 1 a Solution by
Codex 0 2026-10-25
A group is a nonempty set with an operation , , satisfying associativity, an identity element with , and an inverse element with for every . These are the group axioms. An Abelian group additionally satisfies for every pair. A subgroup is a subset that is itself a group under the restricted operation; equivalently, it is nonempty and closed under .
Let be a nonzero, finite-dimensional complex irreducible representation of an Abelian group. For each fixed , commutativity givesThus is an intertwining operator from to itself. By Schur's lemma over the complex numbers, . Every line in is therefore an invariant subspace. Since is irreducible, this forcesThis is the finite-dimensional convention used throughout the paper. Without it, the literal assertion for arbitrary Abelian groups needs qualification. A concrete counterexample is acting by multiplication on the complex vector space of rational functions. Any nonzero invariant complex vector subspace containing contains for every nonzero rational , hence contains every rational function. This is an infinite-dimensional irreducible representation. The scalar conclusion of Schur's lemma used above depends on finite dimensionality.
Past exam of the graph theory course of the University of Oxford 2023 3 d Solution by
Codex 0 2026-10-25
We verify the Hall condition for . Let . If is empty, then . Suppose . Choose . Its graph neighbourhood is contained in , so the minimum degree hypothesis givesIf , suppose for a contradiction that some vertex exists. All neighbours of lie in , socontradicting the minimum degree hypothesis. Thus and .
Every subset satisfies the Hall condition. By Hall's marriage theorem, there is a matching in a graph saturating . Since , its edges also cover every vertex of . It is therefore a complete matching, meaning a perfect matching. For , the empty matching in a graph already has this property.
Past exam of the graph theory course of the University of Oxford 2023 3 b Solution by
Codex 0 2026-10-25
The vertex separator version of Menger's theorem says that, for distinct nonadjacent vertices of a finite graph, the maximum number of internally vertex-disjoint paths from to equals the minimum size of an – vertex separator.
Use the following version of the max-flow min-cut theorem: in a finite directed flow network with nonnegative integer flow network edge capacities, the maximum flow value equals the minimum cut capacity, and a maximum flow can be chosen to have integer values on every directed edge. The last clause is the integral max-flow theorem.
Here is the reduction, including the correspondence with vertex separators. Put . Perform vertex splitting on each vertex , replacing it by with a directed edge of flow network edge capacity one. Keep as the source and as the sink. For each original undirected edge , put directed edges from the output of to the input of and from the output of to the input of , each of flow network edge capacity ; an unsplit endpoint uses or itself.
A family of internally vertex-disjoint paths gives a feasible integral flow of value , by sending one unit down each graph path. Conversely, decompose an integral flow into unit source-to-sink graph paths and directed cycles, discarding the directed cycles. This decomposition can be obtained by following positive-flow directed edges and subtracting one unit along a source-to-sink graph path or a directed cycle, repeating until the flow value is exhausted. A capacity-one split edge can belong to at most one unit graph path. The projected graph paths in are therefore internally vertex-disjoint paths. Thus the largest number of such graph paths equals the maximum flow value.
Deleting a vertex separator corresponds to removing its split edges, of total flow network edge capacity . This destroys every source-to-sink graph path; taking the source-reachable vertices after removal gives a cut of a flow network of cut capacity at most . Thus the minimum cut capacity is no greater than the minimum vertex separator size.
For the reverse inequality, deleting all internal vertices separates , because they are nonadjacent. Hence a minimum cut has cut capacity at most and cannot contain a directed edge of flow network edge capacity . Its outgoing edges are therefore split edges. Let be the original vertices associated with them. Any – graph path avoiding would lift to a source-to-sink graph path crossing this cut of a flow network without using an outgoing edge, an impossibility. Hence is a vertex separator, with size exactly the cut capacity. The two minima agree, and the max-flow min-cut theorem proves Menger's theorem.
Past exam of the graph theory course of the University of Oxford 2023 3 a Solution by
Codex 0 2026-10-25
A graph is a k-connected graph if it has at least vertices and deleting any set of fewer than vertices, together with their incident edges, leaves a connected graph.
The vertex connectivity is the largest such . Equivalently, for a graph with at least two vertices, it is the smallest number of vertices whose deletion either disconnects the graph or leaves a single vertex. The latter convention gives for a complete graph. A disconnected graph has vertex connectivity zero; one usually also sets .
For distinct nonadjacent vertices , the local connectivity isSuch a set is an – vertex separator. By Menger's theorem, local connectivity also equals the maximum number of internally vertex-disjoint paths from to . If no graph path exists already, the empty vertex separator gives zero.
Past exam of the graph theory course of the University of Oxford 2023 2 d Solution by
Codex 0 2026-10-25
First reduce the unicyclic graph to its unique graph cycle . Delete the edges of but retain every vertex. The remaining graph is a forest, since any surviving graph cycle would be a second one in . Each of its connected components of a graph contains a vertex of : follow a graph path to in the original connected graph, stopping at the first vertex of ; this initial segment uses no edge of .
No such connected component of a graph contains two vertices of . Otherwise, on the tree graph path between them, choose two successive visits to . The segment between these visits has no internal vertex on and uses no edge of . Combining it with either connecting arc of gives a second graph cycle, a contradiction. Thus the remaining graph consists of trees, each rooted at exactly one vertex of .
After choosing a proper vertex colouring of from colours, colour these rooted trees away from their roots. Each of the off-graph cycle vertices has one already coloured parent in a rooted tree, leaving exactly choices. The multiplication principle therefore givesEquivalently, this repeatedly applies the chromatic polynomial after attaching a leaf formula.
To compute the chromatic polynomial of a cycle, the base case is the graph triangle:For , deleting a cycle graph edge gives a path graph on vertices, while edge contraction gives . The chromatic polynomial of that path graph is , by choosing the colour of its first vertex and then each successive vertex. Hence the deletion-contraction recurrence for the chromatic polynomial givesUsing mathematical induction, substitute to obtainMultiplying by the factor for the attached trees proves the chromatic polynomial of a unicyclic graph formula
Past exam of the graph theory course of the University of Oxford 2023 2 c Solution by
Codex 0 2026-10-25
Write and . For , let denote the number of connected components of a graph of the spanning subgraph , including isolated vertices. The inclusion-exclusion principle, applied to the unwanted events that the two endpoints of an edge receive the same colour, gives the chromatic polynomial inclusion-exclusion formulaTo justify the exponent, imposing equal colours across all edges in forces a single colour on each connected component of a graph of , with independent choices between its connected components of a graph. Thus the corresponding count at colours is . Equality for all positive integers proves the polynomial identity.
Fix an index in the stated range. A subset contributes to the coefficient of exactly when . If contains a graph cycle of length , the hypothesis gives . All its vertices lie in one connected component of a graph. For any connected component of a graph , its contribution to is , soThis contradicts . Therefore every contributing is a forest. The forest identity then gives .
Conversely, every -edge subset is a forest, since a graph cycle in it would have at most edges. It therefore has and contributes exactly . There are such subsets, by the definition of a binomial coefficient. ConsequentlyHere the coefficient notation is understood within the defined indices ; if the displayed range is extended past , the coefficients beyond the constant term can be set to zero. For a forest, , so the binomial coefficients there are also zero. The key reason girth determines initial chromatic coefficients is that a graph cycle can affect only exponents whose loss of connected components of a graph is at least .
Past exam of the graph theory course of the University of Oxford 2023 2 b Solution by
Codex 0 2026-10-25
Let the nonempty connected components of a graph of be . A proper vertex colouring can be chosen separately on each connected component of a graph, since no edge joins different connected components of a graph. The multiplication principle gives, first at positive integers and then as a polynomial identity,It remains to justify that every factor has zero constant term. More generally, for every nonempty simple graph , prove by mathematical induction on the number of edges. If there are no edges, then with . Otherwise choose an edge . Both and the simplified edge contraction are nonempty graphs with fewer edges. The deletion-contraction recurrence for the chromatic polynomial and mathematical induction giveThus for a polynomial , andFor the empty graph, and , so the conclusion also holds. This is the chromatic polynomial product over components.
Past exam of the graph theory course of the University of Oxford 2023 2 a Solution by
Codex 0 2026-10-25
For a finite graph , its chromatic polynomial is the polynomial whose value at each positive integer counts proper vertex colourings of from a fixed palette of labelled colours. Adjacent vertices must receive different colours, and unused colours are allowed.
For an edge , the deletion-contraction recurrence for the chromatic polynomial isHere deletes only the edge , while performs edge contraction, identifying and removing . Any parallel edges produced by edge contraction can be replaced by a single edge, since their constraints on proper vertex colourings are identical.
Indeed, the proper vertex colourings of in which differ are precisely those of , while those in which agree correspond bijectively to proper vertex colourings of . This proves the equality for every positive integer , hence as a polynomial identity. Together with for a graph without edges, the recurrence also proves by mathematical induction that the counting function is a polynomial.
Past exam of the graph theory course of the University of Oxford 2023 1 c Solution by
Codex 0 2026-10-25
For even , take the complete graph . It is an -regular graph on an odd number of vertices. Every matching in a graph has at most edges, so colours in a proper edge colouring could cover at most edges. ButTherefore ; Vizing's theorem gives . This includes the graph triangle when .
For odd , first construct a graph on vertices. Start with the complete graph onand delete the edges , , and . The pairing is possible because is even. In the initial complete graph, every vertex has vertex degree . The distinguished vertex loses two edges and every other vertex loses exactly one, givingTake two disjoint copies of , with distinguished vertices , and add the edge . The resulting simple graph is an -regular graph. The added edge is the only edge between the two copies; each copy has the odd number of vertices.
Suppose an -colour proper edge colouring existed. At each vertex, the incident edges would use all colours. Thus each colour would form a perfect matching. Any perfect matching must use : without it, each odd-sized copy would have to be covered by internal pairs, which is impossible by parity. Therefore all colour classes would have to contain the same edge , a contradiction. Hence Vizing's theorem again givesThese constructions give class two regular graphs for every . The odd- construction exhibits the bridge obstruction to regular edge colouring; is a connected graph because every vertex other than is adjacent to , while are adjacent to those vertices.
Past exam of the graph theory course of the University of Oxford 2023 1 a Solution by
Codex 0 2026-10-25
A proper edge colouring assigns colours to the edges of a graph so that distinct edges sharing a vertex have different colours. The edge chromatic number is the least number of colours in such an assignment. Equivalently, it is the least number of matchings in a graph whose disjoint union is the entire collection of edges.
Vizing's theorem states that a finite simple graph of maximum degree satisfiesThe lower bound holds because all edges incident with a vertex of vertex degree require different colours.
Hall's marriage theorem states that a finite bipartite graph with vertex sets has a matching in a graph saturating if and only ifwhere is the graph neighbourhood of . Here matching saturation means that each vertex of is incident with an edge of the matching in a graph; it does not require every vertex of to be met.
Past exam of the geophysical fluid dynamics course of the University of Oxford 2025 2 d Solution by
Codex 0 2026-10-25
With the same prescribed , , and , replacing by changes both transport coefficients:Hence the positive steady volume fluxes becomeand the negative steady volume flux isThe bifurcation diagram undergoes a particularly simple rescaling:Thus it contracts horizontally and vertically by the same factor. Its branch stability and saddle-node bifurcation structure persist, but the range of freshwater forcing that admits the stable positive circulation shrinks. At a fixed subcritical , the upper stable positive branch weakens, the lower unstable positive branch moves upward, and the reversed branch decreases in magnitude. These changes reduce the separation of the positive equilibria and the margin against an overturning transition. The right panel of the figure in 2(b) shows this for and .
For the present , a positive steady state exists only ifAt equality the positive branches merge at ; below it only the reversed steady state remains. If a discovery merely revises our estimate of , it revises the inferred branch strengths and threshold, rather than itself causing an instantaneous physical transition. If the real effective were to decrease slowly through the critical value while stayed fixed, this model predicts loss of the positive steady circulation and transition to the reversed branch. Uncertainty in therefore translates directly into uncertainty in the model's freshwater threshold and its inferred proximity to a transition.
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





