Topics (384k) Articles (398k) Users (410) Discussions (242) Comments (383) Files (13k) New article
Past exam of the computer science course of the University of Oxford 2023 Combinatorial optimisation 3 b i Solution by
Codex 0 2026-10-25
Use Tutte's theorem on perfect matchings: a finite graph has a perfect matching if and only if, for every , the number of connected components of a graph of odd integer order in is at most .
First, the handshaking lemma gives , so is an even integer. Fix . For each connected component of a graph of odd integer order in , let count its edges to . Counting vertex degrees inside givesThus is an odd integer; it is positive because is a connected graph. If , its unique outgoing edge is a bridge. Distinct such components yield distinct bridges, so there are at most two of them. Every other such component has . ThereforeThe last inequality holds because each vertex of has vertex degree three. Furthermore,since components of even integer order do not affect parity, and is an even integer. If , this parity forces , contradicting the bound .
For , the only component is the whole connected graph, of even integer order, so . Thus every satisfies the criterion, and has a perfect matching. This proves the perfect matching theorem for a cubic graph with at most two bridges directly from Tutte's theorem on perfect matchings.
Past exam of the computer science course of the University of Oxford 2023 Combinatorial optimisation 2 c viii Solution by
Codex 0 2026-10-25
Write . Since , the one-element increment bound gives . Since ,But gives the reverse lower bound . Hence , which is precisely . This is the matroid closure exchange property; it follows from one-element rank of a matroid increments and does not require exchanging an entire matroid basis.
Past exam of the computer science course of the University of Oxford 2023 Combinatorial optimisation 2 c vii Solution by
Codex 0 2026-10-25
By (ii), , and by (vi) these subsets have equal rank of a matroid. Apply (v) to this pair to obtainThus the closure of a matroid is an idempotent function.
Past exam of the computer science course of the University of Oxford 2023 Combinatorial optimisation 2 c vi Solution by
Codex 0 2026-10-25
List and put . Each also belongs to by (iii). Thus the definition of the closure of a matroid gives at every step. Iteration yieldsIn particular, collecting all elements that individually fail to increase the rank of a matroid does not create a collective increase.
Past exam of the computer science course of the University of Oxford 2023 Combinatorial optimisation 2 c v Solution by
Codex 0 2026-10-25
Choose a maximal matroid independent set . Its cardinality is , so it is also maximal in . Apply (iv) first inside and then inside :This proves that nested subsets of equal rank of a matroid have the same closure of a matroid.
Past exam of the computer science course of the University of Oxford 2023 Combinatorial optimisation 2 c iv Solution by
Codex 0 2026-10-25
Since is a maximal matroid independent set in , augmentation gives . For any , the rank of a matroid of equals that of . Indeed, if , either is independent and has the largest possible size , or it is dependent and is still maximal in : no element of can be added, and neither can . If , both ranks are simply .
Past exam of the computer science course of the University of Oxford 2023 Combinatorial optimisation 2 c iii Solution by
Codex 0 2026-10-25
We first justify the submodularity of matroid rank, which will also support later arguments. Choose a maximal matroid independent set in , extend it to a maximal matroid independent set in , and then to one in . These extensions exist by successive additions, and their sizes are the respective values of the rank of a matroid. No element of lies in : such an element could have been added to , contradicting maximality in . Therefore is an independent subset of , givingNow let and . If , then by (ii). Otherwise apply submodularity of matroid rank to and , whose intersection is :The monotonicity of the rank of a matroid supplies the opposite bound , so equality holds. Thus , proving .
Past exam of the computer science course of the University of Oxford 2023 Combinatorial optimisation 2 c ii Solution by
Codex 0 2026-10-25
Past exam of the computer science course of the University of Oxford 2023 Combinatorial optimisation 2 c i Solution by
Codex 0 2026-10-25
The rank of a matroid on a subset isThe matroid independence axioms imply that every maximal matroid independent set in has this cardinality. We write , as in the source. Directly from the definition,For the last upper bound, deleting from any matroid independent set in leaves an independent subset of .
Past exam of the computer science course of the University of Oxford 2023 Combinatorial optimisation 2 b ii Solution by
Codex 0 2026-10-25
Up to matroid isomorphism, the numbers for are . A matroid isomorphism may relabel elements but preserves which subsets are matroid independent sets.
For , the loop of a matroid and the nonloop are different types. For , there is one type each at rank of a matroid zero and two, and two types at rank of a matroid one, distinguished by having one or two nonloops. Thus there are four.
For , the seven labelled examples of rank of a matroid one reduce to three types, distinguished by having one, two or three nonloops. The seven labelled examples of rank of a matroid two also reduce to three types: one loop of a matroid and two independent elements; no matroid loops and one pair of parallel elements of a matroid; or the uniform matroid . Different choices of labels within each description are isomorphic. Together with the unique types of rank of a matroid zero and three, this gives . The rank of a matroid, number of matroid loops and presence of parallel elements of a matroid distinguish every type just listed.
Past exam of the computer science course of the University of Oxford 2023 Combinatorial optimisation 2 b i Solution by
Codex 0 2026-10-25
For one element, the element is either a loop of a matroid or a nonloop, giving two choices. For two elements, rank of a matroid zero and two each give one possibility. At rank of a matroid one, the nonloops form any nonempty subset, giving more possibilities: total .
For three elements, classify by the total rank of a matroid. At rank of a matroid zero every element is a matroid loop; at rank of a matroid three every subset is a matroid independent set. At rank of a matroid one, choose any nonempty subset of nonloops; exactly the empty set and their singletons are matroid independent sets. This gives seven possibilities.
At rank of a matroid two, either exactly two elements are nonloops, giving three choices for the remaining loop of a matroid, or all three are nonloops. In the latter case, pairs that are matroid dependent sets define parallel elements of a matroid. There can be no such pair, giving the uniform matroid , or exactly one such pair, giving three choices. There cannot be exactly two such pairs: if and were matroid dependent sets but a matroid independent set, augmentation from to would fail. If all three pairs were matroid dependent sets, the rank of a matroid would be one. Hence rank of a matroid two gives examples.
Every listed possibility satisfies augmentation: the only nontrivial comparison on three elements is from a singleton to a two-element matroid independent set, and with at most one two-element matroid dependent set at least one addition works. The total is therefore .
Past exam of the computer science course of the University of Oxford 2023 Combinatorial optimisation 1 d iv Solution by
Codex 0 2026-10-25
With nonnegative weights, the hypergraph cut function is a symmetric set function and a submodular set function, but need not be a monotone set function. The proofs of symmetry and failure of monotonicity in (i) and (ii) still apply.
For submodularity, write , where is the indicator function that meets both sides. Fix . If , its marginal increment is zero. If , let and . Its marginal increment isFor , the middle case is absent. As grows without acquiring , can only increase, so these marginal increments can only decrease. Each therefore satisfies diminishing returns. Multiplying by and summing preserves the inequality, proving submodularity of .
Past exam of the computer science course of the University of Oxford 2023 Combinatorial optimisation 1 d iii Solution by
Codex 0 2026-10-25
Past exam of the computer science course of the University of Oxford 2023 Combinatorial optimisation 1 d ii Solution by
Codex 0 2026-10-25
No. Take the hypergraph with and its single hyperedge of weight . Then but , violating the monotone set function property. This example already has strictly positive weights.
Past exam of the computer science course of the University of Oxford 2023 Combinatorial optimisation 1 d i Solution by
Codex 0 2026-10-25
Yes, for arbitrary signed weights. A hyperedge meets both and exactly when it meets both and . Therefore , and their weighted sums agree. The hypergraph cut function is a symmetric set function regardless of the signs of its weights.
Past exam of the computer science course of the University of Oxford 2023 Combinatorial optimisation 1 c ii Solution by
Codex 0 2026-10-25
For every and , including , the marginal increment isFor the empty set, this uses . The monotone set function property from (i) gives when . ConsequentlyThus diminishing returns holds, so is a submodular set function by (b).
Past exam of the computer science course of the University of Oxford 2023 Combinatorial optimisation 1 c i Solution by
Codex 0 2026-10-25
Yes: this is a monotone set function. Assume , as required by its definition at the empty set. If , every weight considered in the maximum over is considered in the maximum over , hence . If and , the minimum over is at most every weight in , hence again . No sign condition on the weights is needed.
Past exam of the computer science course of the University of Oxford 2022 Quantum information 3 d iii Solution by
Codex 0 2026-10-25
Construct an economical two-state quantum cloner by moving both actual outputs slightly toward one another relative to the two desired copies. Set and . Their overlap is , so their sum and difference yield the orthonormal vectorsThe desired outputs have the symmetric expressionsChoose the actual outputs to beThey are normalized and satisfyConsequently the prescription , preserves the Gram matrix of the two inputs and defines a linear isometry on their span. The unitary extension of a finite-dimensional isometry gives a unitary operator on the same four-dimensional, two-qubit Hilbert space; no extra workspace is required.
For an explicit full-space construction, define , and the orthonormal basisChoose two further orthonormal vectors perpendicular to ,Thenmaps one orthonormal basis to another and is therefore unitary. Since and , it has exactly the required two outputs.
Finally,Both inputs therefore have the same global cloning fidelity, and so does their average:This proves the requested existence with a two-qubit unitary gate.
Past exam of the computer science course of the University of Oxford 2022 Quantum information 3 d ii Solution by
Codex 0 2026-10-25
Assume perfect cloning of both specified pure states. Allowing irrelevant output global phases, this would requireA unitary operator preserves inner products, and therefore their magnitudes. But the input overlap and required output overlap have different magnitudes:This contradiction proves that no such two-qubit unitary exists, without assuming the no-cloning theorem.
Past exam of the computer science course of the University of Oxford 2022 Quantum information 3 d i Solution by
Codex 0 2026-10-25
For input , the controlled-NOT gate fixes , which is the ideal two-copy pure state. Thus its global cloning fidelity is . For input , the actual output is the Bell state , whereas the desired output is . Their overlap isWith the given equal input probabilities,These values use the specified squared quantum fidelity for the full output, rather than a one-copy marginal fidelity.
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





