text:
# Clutters III

A long time ago I started a series of posts abut clutters. The most recent post followed the textbook by Gérards Cornuéjols in defining several important classes, and introduced a Venn diagram, showing the relationships between them.

In this post we will spend a little more time discussing this diagram.

We let $H=(S,\mathcal{A})$ be a clutter. This means that $S$ is a finite set, and the members of $\mathcal{A}$ are subsets of $S$, none of which is properly contained in another. We let $M$ stand for the incidence matrix of $H$. This means that the columns of $M$ are labelled by the elements of $S$, and the rows are labelled by members of $\mathcal{A}$, where an entry of $M$ is one if and only if the corresponding element of $S$ is contained in the corresponding member of $\mathcal{A}$. Any entry of $M$ that is not one is zero. Let $w$ be a vector in $\mathbb{R}^{S}$ with non-negative values. We have two fundamental linear programs:

(1) Find $x\in \mathbb{R}^{S}$ that minimises $w^{T}x$ subject to the constraints $x\geq \mathbf{0}$ and $Mx\geq \mathbf{1}$.

The vectors $\mathbf{0}$ and $\mathbf{1}$ have all entries equal to zero and one, respectively. When we write that real vectors $a$ and $b$ with the same number of entries satisfy $a\geq b$, we mean that each entry of $a$ is at least equal to the corresponding entry in $b$.

(2) Find $y\in\mathbb{R}^{\mathcal{A}}$ that maximises $y^{T}\mathbf{1}$ subject to the constraints $y\geq \mathbf{0}$ and $y^{T}M\leq w$.

Lemma 1. Any clutter with the Max Flow Min Cut property also has the packing property.

Proof. Let $H$ be a clutter with the Max Flow Min Cut property. This means that for any choice of vector $w$ with non-negative integer entries, the programs (1) and (2) both have optimal solutions with integer values.

We will show that $H$ has the packing property. According to the definition in the literature, this means that for any choice of vector $w$ with entries equal to $0$, $1$, or $+\infty$, there are optimal solutions to (1) and (2) with integer entries. I think there is a problem with this definition. Assume that $r$ is a row of $M$, and every member of the support of $r$ receives a weight of $+\infty$ in the vector $w$. Then (2) cannot have an optimal solution. If $y$ is a purported optimal solution, then we can improve it by adding $1$ to the entry of $y$ that corresponds to row $r$. We are instructed that if entry $i$ in $w$ is $+\infty$, then this means when $x$ is a solution to (1), then entry $i$ of $x$ must be $0$. Again, we have a problem, for if $r$ is a row of $M$, and the entire support of $r$ is weighted $+\infty$, then (1) has no solution: if $x$ were a solution, then it would be zero in every entry in the support of $r$, meaning that $Mx$ has a zero entry.

The literature is unanimous in saying that $H$ has the packing property if (1) and (2) both have integral optimal solutions for any choice of vector $w$ with entries $0$, $1$, and $+\infty$. As far as I can see, this means that any clutter with $\mathcal{A}$ non-empty does not have the packing property: simple declare $w$ to be the vector with all entries equal to $+\infty$. Then neither (1) nor (2) has an optimal solution at all. I think the way to recover the definition is to say that whenever $w$ with entries $0$, $1$, or $+\infty$ is chosen in such a way that (1) and (2) have solutions, they both have optimal solutions that are integral. This is the definition that I will use here.

After this detour, we return to our task, and assume that $H$ has the Max Flow Min Cut property. Assume that $w$ is a vector with entries equal to $0$, $1$, or $+\infty$, and that (1) and (2) both have solutions. This means that any row in $M$ has a member of its support which is not weighted $+\infty$ by $w$. We obtain the vector $u$ by replacing each $+\infty$ entry in $w$ with an integer that is greater than $|S|$. Now because $H$ has the Max Flow Min Cut property, it follows that there are optimal integral solutions, $x$ and $y$, to (1) and (2) (relative to the vector $u$). We will show that $x$ and $y$ are also optimal solutions to (1) and (2) relative to the vector $w$.

We partition $S$ into $S_{0}$, $S_{1}$, and $S_{+\infty}$ according to whether an element of $S$ receives a weight of $0$, $1$, or $+\infty$ in $w$. We have assumed that no member of $\mathcal{A}$ is contained in $S_{+\infty}$. We note that if $z\in \mathbb{Z}^{S}$ is a vector which is equal to zero for each element of $S_{+\infty}$, and one everywhere else, then $z$ is a solution to (1), by this assumption. Moreover, $w^{T}z=u^{T}z\leq |S|$. Now it follows that $x$ must be zero in every entry in $S_{+\infty}$, for otherwise $u^{T}x>|S|$, and therefore $x$ is not an optimal solution to (1) relative to $u$. Since $x$ is integral and optimal, it follows that we can assume every entry is either one or zero. If $x$ is not an optimal solution to (1) relative to $w$, then we let $z$ be an optimal solution with $w^{T}z < w^{T}x$. But by convention, $z$ must be zero in every entry of $S_{+\infty}$. Therefore $u^{T}z=w^{T}z < w^{T}x=u^{T}z$, and we have a contradiction to the optimality of $x$. Thus $x$ is an optimal solution to (1) relative to the $\{0,1,+\infty\}$-vector $w$.

Now for problem (2). Since $y$ is integral and non-negative, and $y^{T}M\leq w$, where every member of $\mathcal{A}$ contains an element of $S_{0}$ or $S_{1}$, it follows that each entry of $y$ must be either one or zero. Let $z$ be any solution of (2) relative to $w$. Exactly the same argument shows that each entry of $z$ is between zero and one. Therefore $z^{T}\mathbf{1}\leq y^{T}\mathbf{1}$ so $y$ is an optimal solution to (2).

We have shown that relative to the vector $w$, both (1) and (2) have optimal solutions that are integral. Hence $H$ has the packing property. $\square$

Lemma 2. A clutter with the packing property packs.

Proof. This one is easy. In order to prove that $H$ packs, we merely need to show that (1) and (2) have optimal integral solutions when $w$ is the vector with all entries equal to one. But this follows immediately from our revised definition of clutters with the packing property. $\square$

The final containment we should show is that clutters with the packing property are ideal. Idealness means that (1) has an optimal integral solution for all vectors $w\in \mathbb{R}^{S}$. This proof is difficult, so I will leave it for a future post. Usually we prove it by using a theorem due to Lehman [Leh].

Theorem (Lehman). The clutter $H$ is ideal if and only if (1) has an optimal integral solution for all choices of vector $w\in\{0,1,+\infty\}^{S}$.

Question. Is there a short proof that clutters with the packing property are ideal? One that does not rely on Lehman’s (quite difficult) theorem?

We will conclude with some examples showing that various containments are proper.

Let $C_{3}^{2}$ and $C_{3}^{2+}$ be the clutters with incidence matrices
$\begin{bmatrix} 1&1&0\\ 0&1&1\\ 1&0&1 \end{bmatrix} \quad\text{and}\quad \begin{bmatrix} 1&1&0&1\\ 0&1&1&1\\ 1&0&1&1 \end{bmatrix}.$
Let $Q_{6}$ and $Q_{6}^{+}$ be the clutters with incidence matrices
$\begin{bmatrix} 1&1&0&1&0&0\\ 1&0&1&0&1&0\\ 0&1&1&0&0&1\\ 0&0&0&1&1&1 \end{bmatrix} \quad\text{and}\quad \begin{bmatrix} 1&1&0&1&0&0&1\\ 1&0&1&0&1&0&1\\ 0&1&1&0&0&1&1\\ 0&0&0&1&1&1&1 \end{bmatrix}$

Exercise. Check that:

1. $C_{3}^{2}$ is not ideal and does not pack,
2. $C_{3}^{2+}$ packs, but is not ideal,
3. $Q_{6}$ is ideal, but does not pack,
4. $Q_{6}^{+}$ is ideal and packs, but does not have the packing property.

This leaves one cell in the Venn diagram without a clutter: the clutters with the packing property that do not have the Max Flow Min Cut property. In fact, Conforti and Cornuéjols [CC] have speculated that no such clutter exists.

Conjecture (Conforti and Cornuéjols). A clutter has the packing property if and only if it has the Max Flow Min Cut property.

[CC] M. Conforti and G. Cornuéjols, Clutters that Pack and the Max Flow Min Cut Property: A Conjecture, The Fourth Bellairs Workshop on Combinatorial Optimization, W.R. Pulleyblank and F.B. Shepherd eds. (1993).

[Leh] A. Lehman, On the width-length inequality. Mathematical Programming December 1979, Volume 16, Issue 1, pp 245–259.

# SiGMa 2017 Recap

The Workshop on Structure in Graphs and Matroids (SiGMa 2017) just wrapped up a few weeks ago in Waterloo.  This was a continuation of similar workshops organized by Bert Gerards in 20082010, and 2012 and by Stefan van Zwam and Rudi Pendavingh in 2014 and 2016.

I would like to thank Jim Geelen, Peter Nelson, Luke Postle, and Stefan van Zwam (the organizers of this year’s workshop) who did an excellent job in choosing the program and making sure everything ran smoothly.  They even helped fellow Matroid Union blogger Nathan Bowler overcome Canadian Visa issues in time to give his (very nice) plenary talk (thanks also go to Alan).

This year the workshop was held in commemoration of William T. Tutte, who would have turned 100 this year.  See here for a short biography of Professor Tutte.  Some matroid theorists may not be aware of Tutte’s extremely important contributions as a code breaker at Bletchley Park during the Second World War.  The C&O Department at Waterloo has also been hosting a Distinguished Lecture Series in honour of Tutte this summer.  Click on this link for the list of speakers and to watch the videos on YouTube. SiGMa 2017 also featured a rare conference dinner speech by Jim Geelen on Tutte’s work (I will post a link if it becomes publicly available).

In case you were not able to attend, all the talks from SiGMa 2017 were recorded and will be made available online.  I will post a link when they are uploaded.  The overall quality of talks was very high.  I won’t bias you with all of my personal favourites, but for example, all the plenaries and Paul Seymour were excellent.

# The Template Theorem

Geelen, Gerards, and Whittle are still working on the write-up of their Herculean effort to build a matroid minor structure theory generalizing the work that Robertson and Seymour did for graphs. One of the consequences of their work has been published, namely a discussion of the highly connected members of a minor-closed class of matroids [1]. This work was mentioned by Peter in passing here and in more detail here. What Peter didn’t talk about was the most detailed version of that structure theorem. Today I will do just that. To keep things light, I will focus on binary matroids, but [1] has results for matroids representable over any finite field.

## 1. Low-rank perturbations

The key concept is that of a perturbation of a representable matroid. If $M = M[A]$, and $T$ is a matrix with the same dimensions as $A$, then $M[A+T]$ is a perturbation of $M$. The hope is that, if we know a lot about $M$ and $T$ has low rank, then the resulting matroid still resembles $M$ to a large extent. We will study perturbations of graphic matroids, and start with a few examples. It will be convenient to drop the restriction that the perturbed matroid has the same size as $M$, and therefore we will allow the addition of a bounded number of elements.

Let $A$ be the vertex-edge incidence matrix of a graph, and let $A’$ be the matrix obtained from $A$ by adding an arbitrary row. The matroid $M[A’]$ is known as an even-cycle matroid. It is an instance of the class of lift matroids frequently discussed on this blog, such as by Irene (here,  here, and here) and two weeks ago by Daryl (here). Note that it can be obtained from $M$ by coextending the matroid by one element, and then deleting that element. They can be visualized by coloring the edges of the graph, calling an edge even if its corresponding column in the matrix has a 0 in the new row, and odd if it has a 1. This class of matroids is closed under minors.

Let $A$ again be the vertex-edge incidence matrix of a graph, and this time let $A’$ be the matrix obtained from $A$ by adding an arbitrary column. The matroid $M[A’]$ will have one extra element, and is known as a graft. Grafts played a crucial role in the proofs of many fundamental results in matroid theory, including Seymour’s Decomposition Theorem for regular matroids [2]. They can be visualized by coloring the vertices of the graph whose corresponding matrix row has a 1 in the new column.

Note that the class of grafts is not closed under minors (contracting the graft element destroys the graphic structure). However, a closely related class, where we add an element to the graphic matroid and immediately contract that element, is closed under minors. The duals of these matroids are known as the even cut matroids. They have been extensively studied by Guenin, Pivotto, and Wollan (see, for instance, Irene’s PhD thesis [3]).

### 1.3 Adding a few elements to a low-rank flat

Let $G$ be a graph with $t$ distinguished vertices. We take the vertex-edge incidence matrix, and add a few columns, but now these columns are only allowed to have nonzero entries corresponding to the $t$ distinguished vertices. The resulting class of matroids will resemble a graphic matroid everywhere but in a low-rank set. Note that this can be seen as a variation of the “adding a column” construction, but sometimes it is useful to consider the operation separately.

## 2. Frame templates

Next, we ask ourselves what happens if we allow several of the above operations in a row. Can there be fundamentally different ways to perturb a graphic matroid? Geelen, Gerards, and Whittle answered this question in full generality through the introduction of templates.

Definition. A (binary) frame template is a tuple $\Phi = (C, X, Y_0, Y_1, A_1, \Delta, \Lambda)$ with the following elements:

1. Finite pairwise disjoint sets $C, X, Y_0, Y_1$;
2. A matrix $A_1$ with rows labeled by $X$ and columns labeled by $Y_0\cup Y_1 \cup C$;
3. A set of row vectors $\Delta$ closed under addition, with entries labeled by $Y_0 \cup Y_1 \cup C$;
4. A set of column vectors $\Lambda$ closed under addition, with entries labeled by $X$.

Definition. A matrix $A’$ is said to respect the template $\Phi$ if it is of this form:

Here, a unit column is a column with exactly one nonzero. The incidence matrix and the columns labeled by $Z$ can be of arbitrary size.

Definition. Let $A’$ be a matrix respecting the template $\Phi$. Let $A$ be obtained from $A’$ by

1. Taking each column from $Z$ and adding to it some column labeled by an element of $Y_1$;
2. Deleting the columns labeled by $Y_1$;
3. Contracting the elements labeled by $C$ in the corresponding matroid.

Then $A$ and $M[A]$ are said to conform to the template $\Phi$.

One should think about templates as recipes for constructing families of matroids.

Exercise. Describe the examples from sections 1.1 – 1.3 using templates.

The main result from [1] is that templates can be used to describe all sufficiently large, sufficiently highly connected matroids in any minor-closed class. Highly connected means the following:

Definition. A matroid $M$ is vertically $k$-connected if, for all separations $(X,Y)$ with $\lambda(X) < k$, either $r(X) = r(M)$ or $r(Y) = r(M)$. In other words, one side of the separation is spanning.

The precise result is:

Theorem (Geelen, Gerards, Whittle [1]). Let $\mathcal{M}$ be a proper minor-closed class of binary matroids. There exist constants $k, l$ and frame templates $\Phi_1, \ldots, \Phi_t, \Psi_1, \ldots, \Psi_s$ such that:

1. Every matroid conforming to $\Phi_i$ is in $\mathcal{M}$ for $i = 1, \ldots, t$;
2. Every matroid whose dual conforms to $\Psi_j$ is in $\mathcal{M}$ for $j = 1, \ldots, s$;
3. For every vertically $k$ connected matroid $M \in \mathcal{M}$ with at least $l$ elements, there either exists an $i$ such that $M$ conforms to $\Phi_i$ or a $j$ such that $M^*$ conforms to $\Psi_j$.

The third property says that the structure of the highly connected matroids in the class is completely described by a finite list of templates. The first two properties put some quite strict constraints on those templates: any matroid we can build using the template must be a member of the class!

The third property is reminiscent of the result by Robertson and Seymour that the “torsos” of a tree-decomposition are nearly-embeddable in some surface of bounded genus (see [4, Theorem 12.6.6]). But in the graph minors theorem there is no analog of the converse: most graphs nearly-embeddable on that surface won’t be members of the class being studied.

The first two properties can be used to determine the full set of templates $\Phi_1, \ldots, \Phi_t, \Psi_1, \ldots, \Psi_s$ for a given class of matroids. I have worked on several such results with my PhD student Kevin Grace [5, 6]. For instance, let’s consider Seymour’s 1-flowing conjecture, discussed by Dillon here. With Kevin I proved the following:

Theorem (Grace, vZ [5]). There exist constants $k, l$ such that every vertically $k$-connected 1-flowing matroid on at least $l$ elements is either graphic or cographic.

In other words, any counterexample to Seymour’s conjecture will have to be small, or have a low-order vertical separation. The proof proceeds by considering an arbitrary frame template, and showing that it either has to be trivial, or it can be used to build an excluded minor for the class of 1-flowing matroids. In the process we develop some tools to help with proofs by induction on templates, and to clean up the matrix $A_1$, but those will have to wait for another day.

Other applications of templates include growth rate results, and finding sufficient sets of excluded minors to characterize the highly connected members of a minor-closed class of matroids.

#### References

1. J. Geelen, B. Gerards and G. Whittle, The highly connected matroids in minor-closed classes, Ann. Comb. 19 (2015), 107–123.
2. P. D. Seymour, Decomposition of regular matroids, J. Combin. Theory Ser. B 28(3) (1980), 305-359.
3. I. Pivotto, Even Cycle and Even Cut Matroids. PhD Thesis, University of Waterloo (2011).
4. R. Diestel, Graph Theory, Springer GTM 173, 5th edition (2016).
5. K. Grace, S. H. M. van Zwam, Templates for Binary Matroids, SIAM J. Disc. Mathem. 31(1) (2017), 254 — 282.
6. K. Grace, S. H. M. van Zwam, The highly connected even-cycle and even-cut matroids, Submitted (2016).

# Three classes of graphical matroids

Guest post by Daryl Funk.

Biased graphs, and the frame and lifted-graphic (or simply, lift) matroids associated with them, have been discussed several times already in The Matroid Union blog. Irene Pivotto introduced them in a series of posts, Biased graphs and their matroids I, II, and III. In part II, Irene offered to put money on the truth of the following two conjectures.

Conjecture 1. The class of frame matroids has only a finite number of excluded minors.

Conjecture 2. The class of lift matroids has only a finite number of excluded minors.

If anyone took her up on her offer, you may now collect on your bet. In [CG17], Rong Chen and Jim Geelen exhibit an infinite family of excluded minors for the class of frame matroids, and another for the class of lift matroids. (It is unfair of me to pick on Irene like this — last I heard, bookies were giving 10:1 odds on). These families of excluded minors belong to a third class of matroids having graphical-type structure. So before discussing Rong and Jim’s counter-examples to Conjectures 1 and 2, we had better learn about this new class.

# Quasi-graphic matroids

In his post, Graphical representations of matroids, Jim Geelen discussed a preliminary formulation for a new class of “graphical” matroids, which he there called framework matroids. The goal was to define a single minor-closed class that contains both the classes of frame and lift matroids, and to do so in a way such that (1) the new class maintains or captures the fundamental underlying graphic structure of these matroids, and (2) recognising membership in the new class is tractable — that is, there should be a polynomial-time algorithm to test membership via a rank oracle.

Jim’s goal has largely been realised, with his introduction, along with Bert Gerards and Geoff Whittle, of the class of quasi-graphic matroids, in [GGW17]. There should certainly be a post wholly devoted to this wonderful class of matroids soon. Here, I will tantalise you with just the definition and an example.

Let $M$ be a matroid. A graph $G$ is a framework for $M$ if

1. $E(G)=E(M)$,
2. for each component $H$ of $G$, $r_M(E(H)) \leq |V(H)|$,
3. for each vertex $v$ of $G$, $\operatorname{cl}_M(E(G-v)) \subseteq E(G-v) \cup \{e: e\ \text{is a loop incident to}\ v\},$ and
4. for each circuit $C$ of $M$, the subgraph $G[C]$ induced by $C$ has at most two components.

A matroid is quasi-graphic if it has a framework. The definition is motivated by the following theorem of Paul Seymour, which yields a polynomial-time algorithm to test, via a rank oracle, if a given matroid is graphic. A star of a graph $G$ is the set of edges incident to a vertex $v \in V(G)$ each of whose other endpoint is in $V(G)-v$ (so while $G$ may have loops, loops are not included in any star); $c(G)$ denotes the number of components of $G$.

Theorem 1 [S81]. Let $M$ be a matroid, and let $G$ be a graph. Then $M$ is the cycle matroid of $G$ if and only if

1. $E(G)=E(M)$,
2. $r(M) \leq |V(G)| – c(G)$, and
3. every star of $G$ is a union of cocircuits of $M$.

One can readily see that the requirements for a framework are inspired by the conditions of Theorem 1. One can also see that generalising these conditions to encompass a larger minor-closed class that includes all frame and lift matroids, is not quite straightforward (hopefully, we may learn more about this in a future post). In [GGW17], Jim, Bert, and Geoff show (among other things) that the class of quasi-graphic matroids has the following nice properties:

• It is minor-closed.
• If $(G,\mathcal B)$ is a biased graph, then $G$ is a framework for the lift matroid $LM(G,\mathcal B)$, and $G$ is a framework for the frame matroid $FM(G,\mathcal B)$; thus all lift and all frame matroids are quasi-graphic.
• Given a 3-connected matroid $M$ and a graph $G$, one can check in polynomial time whether $G$ is a framework for $M$.

Jim, Bert, and Geoff conjecture in [GGW17] that there is a polynomial-time algorithm to test, via a rank oracle, if a given matroid is quasi-graphic. In contrast, Rong Chen and Geoff Whittle have recently shown that for each of the classes of frame and lift matroids, testing for membership in the class is intractable [CW16]. More on this in a moment. But first, let us try to get a bit of a feel for what a typical quasi-graphic matroid might look like.

Let us recall some required preliminary concepts. Every frame and every lift matroid may be represented by a biased graph $(G,\mathcal B)$ with $E(G)=E(M)$. For clarity’s sake, I’ll reserve the word circuit for matroids, and use the word cycle for a 2-regular connected subgraph. Recall how the circuits of frame and lift matroids appear in their biased graph representations: they are precisely the edge sets of subdivisions of certain biased subgraphs. Recall, a cycle $C$ of a graph whose edge set is a circuit of the matroid is balanced; otherwise $E(C)$ is independent and $C$ is said to be unbalanced. The figures in Sections 2 and 3 of Irene’s first post on biased graphs, reproduced here for your convenience, illustrate these biased subgraphs.

Circuits of frame matroids are subdivisions of these graphs. Unlabelled cycles are unbalanced.

Circuits of lift matroids are subdivisions of these graphs. Unlabelled cycles are unbalanced.

Let us call a subdivision of one of these five biased subgraphs (1), (2), (3F), (3L), (4), a circuit-subgraph. Note that the frame and lift matroids associated with a given biased graph differ on just one pair of these circuit-subgraphs, namely, (3F) and (3L) — a pair of vertex disjoint unbalanced cycles forms a circuit of the lift matroid, but is independent in the frame matroid. As Irene has explained in her previous posts, given a biased graph, we get a frame matroid by taking as circuits just circuit-subgraphs of the forms (1), (2), (3F), and (4), we get a lift matroid by taking as circuits just circuit-subgraphs of the forms (1), (2), (3L), and (4), and Tom Zaslavsky has shown that in fact all frame matroids, and all lift matroids, are obtained this way.

What about quasi-graphic matroids? Here is an example. The Vámos matroid (shown below left as a cube, in which the only 4-circuits are the 4 “sides” and just the one “diagonal” plane 2468) is neither a frame matroid, nor a lift matroid, but it is quasi-graphic, with the graph below right providing a framework. (Check that it satisfies the definition!)

Consider the 4-circuits of Vámos, and the subgraphs they form in the framework graph.
The four planes given by the front, back, and sides of the cube each form a circuit-subgraph of type (2), which is a circuit-subgraph for both frame and lift matroids. But together the circuit 2468 and the independent set 1357 prevent this graph from being either a frame or a lift representation for Vámos: circuit 2468 appears as a type (3L) circuit-subgraph, but so does the independent set 1357.

It turns out that (here I’m summarising results of [GGW17]), just as with biased graph representations of frame and lift matroids, the edge set of every cycle in a framework $G$ for a quasi-graphic matroid $M$ is either a circuit of $M$ or is independent in $M$. Further, declaring each cycle of $G$ to be balanced or unbalanced accordingly, just as for frame and lift matroids, yields a biased graph $(G,\mathcal B)$, where $\mathcal B$ denotes the collection of balanced cycles of $G$ (that is, the collection of balanced cycles satisfies the theta property: no theta subgraph contains exactly two balanced cycles). Moreover, every circuit of $M$ appears in $G$ as one of our five circuit-subgraphs (1), (2), (3F), (3L), (4). Conversely, the edge set of each circuit-subgraph of $G$ of one of the forms (1), (2), or (4) is a circuit of $M$, and each of the form of (3F) is either a circuit or contains a circuit of the form (3L).

Thus frameworks for matroids behave very much like biased graph representations for frame and lift matroids. Given a biased graph, taking $\{(1),(2),(3$F$),(4)\}$ as our circuit-subgraphs gives us a frame matroid, taking $\{(1),(2),(3$L$),(4)\}$ as our circuit-subgraphs gives us a lift matroid; and allowing all of $\{(1), (2), (3$F$), (3$L$), (4)\}$ as circuit-subgraphs gives the class of quasi-graphic matroids. This phenomenon is illustrated in the framework for the Vámos matroid above: 2468 is a (3L) circuit-subgraph, while each of the four circuits $1357 \cup e$ for $e \in \{2,4,6,8\}$ are (3F) circuit-subgraphs. Put another way, if a matroid $M$ has a framework having no circuit-subgraphs of type (3F), then we have a biased graph representation for $M$ as a lift matroid; if $M$ has a framework with no circuit-subgraphs of type (3L), then we have a biased graph representation for $M$ as a frame matroid; the Vámos matroid shows that (3F) and (3L) type circuit-subgraphs can coexist in a framework.

# Recognition of frame, and of lift matroids, is intractable

As mentioned above, Rong and Geoff have shown that there can be no algorithm that can determine, via a rank oracle, in time polynomial in the size of the ground set, whether or not a given matroid is a frame matroid. They also show no such algorithm can exist for recognising lift matroids. They do so using two particular families of quasi-graphic matroids, one for frame and one for lift, arising from the same infinite family of framework graphs. More precisely, they prove the following two theorems.

Theorem 2 [CW16]. For any polynomial $p(\cdot)$, there is a frame matroid $M$ such that, for any collection $\mathcal A$ of subsets of $E(M)$ with $|\mathcal A| \leq p(|E(M)|)$, there is a quasi-graphic matroid $N$ that is not frame, such that $E(N)=E(M)$ and for each $A \in \mathcal A$, $r_k(A) = r_M(A)$.

Theorem 3 [CW16]. For any polynomial $p(\cdot)$, there is a lift matroid $M$ such that, for any collection $\mathcal A$ of subsets of $E(M)$ with $|\mathcal A| \leq p(|E(M)|)$, there is a quasi-graphic matroid $N$ that is not lift, such that $E(N)=E(M)$ and for each $A \in \mathcal A$, $r_k(A) = r_M(A)$.

The proofs go like this. Construct an infinite family of biased graphs $(W_k, \emptyset)$. Relaxation of a particular circuit-hyperplane of the lift matroid $LM(W_k,\emptyset)$ yields a quasi-graphic matroid that is no longer lift, but which agrees with $LM(W_k,\emptyset)$ on almost all subsets. Performing the reverse tweak to the frame matroid $FM(W_k, \emptyset)$ yields a quasi-graphic matroid that is no longer frame, but which agrees with $FM(W_k,\emptyset)$ on almost all subsets. The operation reverse to relaxation of a circuit-hyperplane is that of tightening a free basis. A free basis of a matroid is a basis $B$ such that $B \cup e$ is a circuit for each $e \in E(M)-B$. If $B$ is a free basis of $M$, then removing $B$ from the set of bases of $M$ results in a matroid, which we say is obtained by tightening $B$.

Here is the family of biased graphs. For each even integer $k \geq 4$, let $W_k$ be the graph consisting of 4 edge-disjoint $k$-cycles on vertices $u_1, \ldots, u_k, v_1, \ldots, v_k$: one cycle on the $u_i$’s, one cycle on the $v_i$’s (the vertex disjoint pair of blue cycles in the drawing of $W_6$ at below left), and two cycles (red and green in figure) alternating between $u_i$’s and $v_i$’s hitting every second vertex of the blue cycles as shown (below left).

Call a green edge and a red edge that cross in this drawing a crossing pair. Observe that $W_k$ has $k$ crossing pairs, and that for every collection $S$ of an even number of crossing pairs, there is a pair of disjoint cycles $C_S^1, C_S^2$ which use precisely these crossing pairs, each of which has length $k$, and which between them traverse all vertices of $W_k$. (See figure below: choosing the 2nd and 4th crossing pair defines the pair of cycles highlighted green and yellow.)

The graph $W_k$ has exponentially many collections of crossing pairs: there are $2^{k-1}$ collections consisting of an even number of crossing pairs. Hence $W_k$ has $2^{k-1}$ pairs of disjoint cycles, each pair having the property that together they contain all vertices of $W_k$. Each such pair of cycles is a circuit-hyperplane of the lift matroid $LM(W_k,\emptyset)$, and a free basis of the frame matroid $FM(W_k,\emptyset)$. Let $Z$ be the edge set of a pair of cycles obtained as above from a chosen set of crossing pairs of even cardinality. Let $M_L^Z$ be the matroid obtained from $LM(W_k,\emptyset)$ by relaxing the circuit-hyperplane $Z$. Let $M_F^Z$ be the matroid obtained from $FM(W_k,\emptyset)$ by tightening the free basis $Z$. To distinguish $LM(W_k,\emptyset)$ from $M_L^Z$, and to distinguish $FM(W_k,\emptyset)$ from $M_F^Z$, requires checking the rank of $2^{k-1}$ subsets. This, of course, will be greater than any polynomial in $|E(W_k)|$ for sufficiently large $k$. Since $W_k$ remains a framework for both $M_L^Z$ and $M_F^Z$, both these matroids are quasi-graphic. The proofs are completed by showing that $M_L^Z$ is not a lift matroid, and that $M_F^Z$ is not frame (which takes just another couple of pages in Rong and Geoff’s paper).

The Chen-Whittle graph’s usefulness does not stop here.

# Excluded minors

To disprove Conjectures 1 and 2, Rong and Jim exhibit an infinite family of quasi-graphic matroids, each of which is minor-minimally not frame, and another infinite family of quasi-graphic matroids, each of which is minor-minimally not lifted-graphic. As in Rong and Geoff’s proofs of Theorems 2 and 3, these two families share a common framework. In fact, they again use the Chen-Whittle graphs!

Here is Rong and Jim’s construction. For each odd positive integer $k \geq 5$, let $G_k$ be the graph obtained from the Chen-Whittle graph $W_{k+1}$ defined above by deleting exactly one crossing pair (at right in figure above is shown the Chen-Geelen graph $G_5$). It is convenient to describe the collection of balanced cycles of $G_k$ by group-labelling (group-labelled graphs are described in Irene’s first post on biased graphs, Section 1, 4th bullet point).

For each odd positive integer $k \geq 5$, we obtain a quasi-graphic excluded minor for the class of frame matroids, with framework $G_k$, as follows. Label $G_k$ using the multiplicative group of $\mathbb R$. Referring to the drawing of $G_5$ above: orient each of $e_1$ and $e_2$ “up” from the bottom vertex to the top vertex of the vertical path making up its “side” of the crossing ladder, and assign to both $e_1$ and $e_2$ the label 2. Orient all remaining edges arbitrarily, and assign each label 1. Let $\mathcal B_k$ be the collection of balanced cycles defined by this labelling (that is, ${\mathcal B}_k$ consists of those cycles $C$ for which the product of edge labels, taken while traversing $C$ in a cyclic order, is 1, where we take the multiplicative inverse of each label whose edge is traversed against its orientation). Let $P$ be the paths forming the two vertical sides of the ladder, so $P \cup \{e_1, e_2\}$ is the pair of blue disjoint cycles in the figure, and let $Q$ be the union of the red and green paths. Then $P \cup \{e_1, e_2\}$ and $Q \cup \{e_1, e_2\}$ are free bases of $FM(G_k, \mathcal B_k)$. Let $M_k^F$ be the matroid obtained from $FM(G_k, \mathcal B_k)$ by tightening $P \cup \{e_1, e_2\}$ and $Q \cup \{e_1, e_2\}$. Then $M_k^F/\{e_1, e_2\}$, while quasi-graphic (with framework $G_k/\{e_1,e_2\}$), is an excluded minor for the class of frame matroids.

An excluded minor for the class of lift matroids is obtained in a similar manner. Again orient $e_1$ and $e_2$ up from the bottom to the top vertex of the vertical paths of the ladder. This time, label $G_k$ using elements of the additive group of integers, labelling $e_1$ with $1$, $e_2$ by $-1$, and all remaining edges with $0$. Let $\mathcal B_k$ be the collection of balanced cycles defined by this labelling (that is, $C \in \mathcal B_k$ if and only if when traversing $C$ in a chosen cyclic direction, taking the sum of the labels on its edges, subtracting the label on each edge traversed against its orientation, yields $0$). Let $P$ and $Q$ be as before. Then $P \cup \{e_1,e_2\}$ and $Q \cup \{e_1, e_2\}$ are circuit-hyperplanes of $LM(G_k, \mathcal B_k)$. Let $M_k^L$ be the matroid obtained from $LM(G_k, \mathcal B_k)$ by relaxing $P \cup \{e_1, e_2\}$ and $Q \cup \{e_1, e_2\}$. Then $M_k^L / \{e_1, e_2\}$, while quasi-graphic, is an excluded minor for the class of lift matroids.

Rong and Jim make the following conjecture.

Conjecture 3 [CG17]. The class of quasi-graphic matroids has only a finite number of excluded minors.

Dillon Mayhew and I have recently proved the following three theorems.

Theorem 4 [FM17]. The class of frame matroids has only a finite number of excluded minors of any fixed rank.

Theorem 5 [FM17]. The class of lift matroids has only a finite number of excluded minors of any fixed rank.

Theorem 6 [FM17]. The class of quasi-graphic matroids has only a finite number of excluded minors of any fixed rank.

Rong and Jim’s counterexamples to Conjecture 1 and 2 are both infinite families of excluded minors of ever increasing, arbitrarily large rank (if $G$ is a connected framework for a non-graphic quasi-graphic matroid $M$, then the rank of $M$ is $|V(G)|$). Theorems 4 and 5 say that any such collections of excluded minors for these classes must have this property. Theorem 6 provides evidence toward Conjecture 3 — though no more evidence than Theorems 4 and 5, respectively, provide toward Conjectures 1 and 2! What is perhaps interesting about Theorems 4, 5, and 6 is that — in contrast to what we’ve just seen in the results of Rong, Geoff, and Jim above — the same strategy works for all three classes. Dillon and I set out to prove Theorem 4, and having done so, realised that essentially the same proof also gives us Theorems 5 and 6. Perhaps we can take a look at this strategy in a subsequent post.

# References

[CG17] Rong Chen and Jim Geelen. Infinitly many excluded minors for frame matroids and for lifted-graphic matroids. arXiv:1703.04857

[CW16] Rong Chen and Geoff Whittle. On recognising frame and lifted-graphic matroids. arXiv:1601.01791

[FM17] Daryl Funk and Dillon Mayhew. On excluded minors for classes of graphical matroids. Forthcoming.

[GGW17] Jim Geelen, Bert Gerards, and Geoff Whittle. Quasi-graphic matroids. arXiv:1512.03005

[S81] Paul Seymour. Recognizing graphic matroids. Combinatorica (1981). MR602418


text:
# How to give a combinatorial proof for this forumula

I need to give a combinatorial argument that $$S(n,m) = \sum_{i =0} ^{n-1} {n -1 \choose i} S(i,m-1)$$

Where $S(n,m)$ is the Stirling numbers of the second kind.

Here is my attempt.

Well first thing to know here is that $S(n,m)$ is the number of ways to distribute $n$ distinct among $m$ non empty identical containers.

So If by somehow I managed to show that the right hand side of the above equation mean the same thing then I am done right !

Now for $0 \leq i \leq n-1$, let $i$ count the number of distinct objects that we actually distribute (The number of objects that got distributed from $n-1$ objects). This number of distinct objects can be chosen in ${n-1 \choose i}$ ways, Now the number of ways that we can distribute those $i$ objects among $m-1$ non empty identical container is ${n-1 \choose i} S(i,m-1)$.

But if we kept doing that we will get $S(n-1,m-1)$ and not $S(n,m)$.

I feel like I am missing something here, and something is wrong with my reasoning. How do I proceed with this proof or re correct it.

Say that the objects being distributed are the integers $1,2,\ldots,n$. Let $i$ be the number of objects that are not in the same container as $n$. Then $0\le i\le n-1$, there are $\binom{n-1}i$ ways to choose those $i$ objects, and there are $S(i,m-1)$ ways to distribute them amongst the remaining $m-1$ containers.
• ahaa, and so in total there are ${n-1 \choose i} S(i,m-1)$ ways to distribute those $i$ objects (that are not in the same container as n)) among $m-1$ identical containers. And here we have $m-1$ because we are not counting the container that $n$ is inside it right? But I have a question. Fixing this $n$ and doing this for all other $n-1$ objects will be the same as $S(n,m)$ ? is that correct ? thanks – alkabary Oct 6 '15 at 17:48
• @alkabary: Yes, you’re understanding correctly. Remember, the containers are identical, so it doesn’t matter which one $n$ is in; it’s identified only by the fact that $n$ is in it. That’s why we can fix it. – Brian M. Scott Oct 6 '15 at 17:53

format: plain


text:
# Prove that $\sin(12^\circ)\sin(48^\circ)\sin(54^\circ)=\frac18$ [closed]

Prove that $$\sin(12^\circ)\sin(48^\circ)\sin(54^\circ)=\frac18.$$ Without using a calculator. I tried all identities I know but I have no idea how to proceed. I always get stuck on finding $\sin36^\circ$.

## closed as off-topic by heropup, David H, Cookie, Adam Hughes, GinaJul 26 '14 at 6:42

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – heropup, David H, Cookie, Adam Hughes, Gina
If this question can be reworded to fit the rules in the help center, please edit the question.

• This is false as stated. Please, do mention that you measure angles in degrees, not in radians. The overwhelming majority of mathematicians will by default treat the argument of $\sin$ as being in radians. – Dan Shved Jul 26 '14 at 6:06
• Thankyou for the suggestion – Kanishk Jul 26 '14 at 6:08
• We have $$\sin12^\circ\sin48^\circ\sin54^\circ=\frac18\tag1$$ Multiplying $(1)$ by $2$ yields $$2\sin12^\circ\sin48^\circ\sin54^\circ=\frac14\tag2$$ Using identities: $2\sin a\sin b=\cos(a-b)-\cos(a+b)$ and $\sin(90^\circ-x)=\cos x$ yields $$\left(\cos36^\circ-\frac12\right)\cos36^\circ=\frac14\tag3$$ Now, setting $x=\cos36^\circ$ and multiplying $(3)$ by $4$ yields $$4x^2-2x-1=0\tag4$$ Solving $(4)$ then use identity $\sin\theta=\sqrt{1-\cos^2\theta}$. – Tunk-Fey Jul 26 '14 at 7:23
• @Tunk-Fey, $$(3)\implies\cos36^\circ-\cos72^\circ=\frac12$$ (math.stackexchange.com/questions/827540/…) – lab bhattacharjee Jul 26 '14 at 8:08

Use the following: $$\sin\theta \sin\left(\frac{\pi}{3}-\theta\right)\sin\left(\frac{\pi}{3}+\theta\right)=\frac{1}{4}\sin(3\theta)$$ Then you have: $$\sin(12^{\circ})\sin(60^{\circ}-12^{\circ})\sin(60^{\circ}+12^{\circ})=\frac{1}{4}\sin(36^{\circ})$$ $$\Rightarrow \sin(12^{\circ})\sin(48^{\circ})=\frac{1}{4}\frac{\sin(36^{\circ})}{\sin(72^{\circ})}$$ $$\Rightarrow \sin(12^{\circ})\sin(48^{\circ})\sin(54^{\circ})=\frac{1}{4}\frac{\sin(36^{\circ})}{\sin(72^{\circ})}\sin(54^{\circ})=\frac{1}{4}\frac{\sin(36^{\circ})}{\sin(72^{\circ})}\cos(36^{\circ})$$ $$\Rightarrow \sin(12^{\circ})\sin(48^{\circ})\sin(54^{\circ})=\boxed{\dfrac{1}{8}}$$
$2\sin 12\cdot \sin 48 = \cos (48 - 12) - \cos (48 + 12) = \cos 36 - \dfrac{1}{2}$. So the problem is to find $\cos 36$. Use $1 - 2x^2 = 3x - 4x^3$ to solve for $\sin 18$ ( not hard ), then find $\cos 36$, and $\sin 54$. In fact, the equation is: $4x^3 - 2x^2 - 3x + 1 = 0 \to (x-1)(4x^2 + 2x - 1) = 0$, so $\sin 18 = x = \dfrac{\sqrt{5} - 1}{4}$. You can take it from here.


text:
## Second update of aggregate notes for phy1520, Graduate Quantum Mechanics

I’ve posted a second update of my aggregate notes for PHY1520H Graduate Quantum Mechanics, taught by Prof. Arun Paramekanti. In addition to what was noted previously, this contains lecture notes up to lecture 9, my ungraded solutions for the second problem set, and some additional worked practise problems.

Most of the content was posted individually in the following locations, but those original documents will not be maintained individually any further.

## PHY1520H Graduate Quantum Mechanics. Lecture 9: Dirac equation (cont.). Taught by Prof. Arun Paramekanti

### Disclaimer

Peeter’s lecture notes from class. These may be incoherent and rough.

These are notes for the UofT course PHY1520, Graduate Quantum Mechanics, taught by Prof. Paramekanti.

### Where we left off

\label{eqn:qmLecture9:20}
-i \Hbar \PD{t}{}
\begin{bmatrix}
\psi_1 \\
\psi_2
\end{bmatrix}
=
\begin{bmatrix}
-i \Hbar c \PD{x}{} & m c^2 \\
m c^2 & i \Hbar c \PD{x}{} \\
\end{bmatrix}.

With a potential this would be

\label{eqn:qmLecture9:40}
-i \Hbar \PD{t}{}
\begin{bmatrix}
\psi_1 \\
\psi_2
\end{bmatrix}
=
\begin{bmatrix}
-i \Hbar c \PD{x}{} + V(x) & m c^2 \\
m c^2 & i \Hbar c \PD{x}{} + V(x) \\
\end{bmatrix}.

This means that the potential is raising the energy eigenvalue of the system.

### Free Particle

Assuming a form

\label{eqn:qmLecture9:60}
\begin{bmatrix}
\psi_1(x,t) \\
\psi_2(x,t)
\end{bmatrix}
=
e^{i k x}
\begin{bmatrix}
f_1(t) \\
f_2(t) \\
\end{bmatrix},

and plugging back into the Dirac equation we have

\label{eqn:qmLecture9:80}
-i \Hbar \PD{t}{}
\begin{bmatrix}
f_1 \\
f_2
\end{bmatrix}
=
\begin{bmatrix}
k \Hbar c & m c^2 \\
m c^2 & – \Hbar k c \\
\end{bmatrix}
\begin{bmatrix}
f_1 \\
f_2
\end{bmatrix}.

We can use a diagonalizing rotation

\label{eqn:qmLecture9:100}
\begin{bmatrix}
f_1 \\
f_2
\end{bmatrix}
=
\begin{bmatrix}
\cos\theta_k & -\sin\theta_k \\
\sin\theta_k & \cos\theta_k \\
\end{bmatrix}
\begin{bmatrix}
f_{+} \\
f_{-} \\
\end{bmatrix}.

Plugging this in reduces the system to the form

\label{eqn:qmLecture9:140}
-i \Hbar \PD{t}{}
\begin{bmatrix}
f_{+} \\
f_{-} \\
\end{bmatrix}
=
\begin{bmatrix}
E_k & 0 \\
0 & -E_k
\end{bmatrix}
\begin{bmatrix}
f_{+} \\
f_{-} \\
\end{bmatrix}.

Where the rotation angle is found to be given by

\label{eqn:qmLecture9:160}
\begin{aligned}
\sin(2 \theta_k) &= \frac{m c^2}{\sqrt{(\Hbar k c)^2 + m^2 c^4}} \\
\cos(2 \theta_k) &= \frac{\Hbar k c}{\sqrt{(\Hbar k c)^2 + m^2 c^4}} \\
E_k &= \sqrt{(\Hbar k c)^2 + m^2 c^4}
\end{aligned}

See fig. 1 for a sketch of energy vs momentum. The asymptotes are the limiting cases when $$m c^2 \rightarrow 0$$. The $$+$$ branch is what we usually associate with particles. What about the other energy states. For Fermions Dirac argued that the lower energy states could be thought of as “filled up”, using the Pauli principle to leave only the positive energy states available. This was called the “Dirac Sea”. This isn’t a good solution, and won’t work for example for Bosons.

fig. 1. Dirac equation solution space

Another way to rationalize this is to employ ideas from solid state theory. For example consider a semiconductor with a valence and conduction band as sketched in fig. 2.

fig. 2. Solid state valence and conduction band transition

A photon can excite an electron from the valence band to the conduction band, leaving all the valence band states filled except for one (a hole). For an electron we can use almost the same picture, as sketched in fig. 3.

fig. 3. Pair creation

A photon with energy $$E_k – (-E_k)$$ can create a positron-electron pair from the vacuum, where the energy of the electron and positron pair is $$E_k$$.

At high enough energies, we can see this pair creation occur.

### Zitterbewegung

If a particle is created at a non-eigenstate such as one on the asymptotes, then oscillations between the positive and negative branches are possible as sketched in fig. 4.

fig. 4. Zitterbewegung oscillation

Only “vertical” oscillations between the positive and negative locations on these branches is possible since those are the points that match the particle momentum. Examining this will be the aim of one of the problem set problems.

### Probability and current density

If we define a probability density

\label{eqn:qmLecture9:180}
\rho(x, t) = \Abs{\psi_1}^2 + \Abs{\psi_2}^2,

does this satisfy a probability conservation relation

\label{eqn:qmLecture9:200}
\PD{t}{\rho} + \PD{x}{j} = 0,

where $$j$$ is the probability current. Plugging in the density, we have

\label{eqn:qmLecture9:220}
\PD{t}{\rho}
=
\PD{t}{\psi_1^\conj} \psi_1
+
\psi_1^\conj \PD{t}{\psi_1}
+
\PD{t}{\psi_2^\conj} \psi_2
+
\psi_2^\conj \PD{t}{\psi_2}.

It turns out that the probability current has the form

\label{eqn:qmLecture9:240}
j(x,t) = c \lr{ \psi_1^\conj \psi_1 + \psi_2^\conj \psi_2 }.

Here the speed of light $$c$$ is the slope of the line in the plots above. We can think of this current density as right movers minus the left movers. Any state that is given can be thought of as a combination of right moving and left moving states, neither of which are eigenstates of the free particle Hamiltonian.

### Potential step

The next logical thing to think about, as in non-relativistic quantum mechanics, is to think about what occurs when the particle hits a potential step, as in fig. 5.

fig. 5. Reflection off a potential barrier

The approach is the same. We write down the wave functions for the $$V = 0$$ region (I), and the higher potential region (II).

The eigenstates are found on the solid lines above the asymptotes on the right hand movers side as sketched in fig. 6. The right and left moving designations are based on the phase velocity $$\PDi{k}{E}$$ (approaching $$\pm c$$ on the top-right and top-left quadrants respectively).

fig. 6. Right movers and left movers

For $$k > 0$$, an eigenstate for the incident wave is

\label{eqn:qmLecture9:261}
\Bpsi_{\textrm{inc}}(x) =
\begin{bmatrix}
\cos\theta_k \\
\sin\theta_k
\end{bmatrix}
e^{i k x},

For the reflected wave function, we pick a function on the left moving side of the positive energy branch.

\label{eqn:qmLecture9:260}
\Bpsi_{\textrm{ref}}(x) =
\begin{bmatrix}
? \\
?
\end{bmatrix}
e^{-i k x},

We’ll go through this in more detail next time.

## Question: Calculate the right going diagonalization

Prove (7).

To determine the relations for $$\theta_k$$ we have to solve

\label{eqn:qmLecture9:280}
\begin{bmatrix}
E_k & 0 \\
0 & -E_k
\end{bmatrix}
= R^{-1} H R.

Working with $$\Hbar = c = 1$$ temporarily, and $$C = \cos\theta_k, S = \sin\theta_k$$, that is

\label{eqn:qmLecture9:300}
\begin{aligned}
\begin{bmatrix}
E_k & 0 \\
0 & -E_k
\end{bmatrix}
&=
\begin{bmatrix}
C & S \\
-S & C
\end{bmatrix}
\begin{bmatrix}
k & m \\
m & -k
\end{bmatrix}
\begin{bmatrix}
C & -S \\
S & C
\end{bmatrix} \\
&=
\begin{bmatrix}
C & S \\
-S & C
\end{bmatrix}
\begin{bmatrix}
k C + m S & -k S + m C \\
m C – k S & -m S – k C
\end{bmatrix} \\
&=
\begin{bmatrix}
k C^2 + m S C + m C S – k S^2 & -k S C + m C^2 -m S^2 – k C S \\
-k C S – m S^2 + m C^2 – k S C & k S^2 – m C S -m S C – k C^2
\end{bmatrix} \\
&=
\begin{bmatrix}
k \cos(2 \theta_k) + m \sin(2 \theta_k) & m \cos(2 \theta_k) – k \sin(2 \theta_k) \\
m \cos(2 \theta_k) – k \sin(2 \theta_k) & -k \cos(2 \theta_k) – m \sin(2 \theta_k) \\
\end{bmatrix}.
\end{aligned}

This gives

\label{eqn:qmLecture9:320}
\begin{aligned}
E_k
\begin{bmatrix}
1 \\
0
\end{bmatrix}
&=
\begin{bmatrix}
k \cos(2 \theta_k) + m \sin(2 \theta_k) \\
m \cos(2 \theta_k) – k \sin(2 \theta_k) \\
\end{bmatrix} \\
&=
\begin{bmatrix}
k & m \\
m & -k
\end{bmatrix}
\begin{bmatrix}
\cos(2 \theta_k) \\
\sin(2 \theta_k) \\
\end{bmatrix}.
\end{aligned}

Adding back in the $$\Hbar$$’s and $$c$$’s this is

\label{eqn:qmLecture9:340}
\begin{aligned}
\begin{bmatrix}
\cos(2 \theta_k) \\
\sin(2 \theta_k) \\
\end{bmatrix}
&=
\frac{E_k}{-(\Hbar k c)^2 -(m c^2)^2}
\begin{bmatrix}
– \Hbar k c & – m c^2 \\
– m c^2 & \Hbar k c
\end{bmatrix}
\begin{bmatrix}
1 \\
0
\end{bmatrix} \\
&=
\inv{E_k}
\begin{bmatrix}
\Hbar k c \\
m c^2
\end{bmatrix}.
\end{aligned}

## Question: Verify the Dirac current relationship.

Prove \ref{eqn:qmLecture9:240}.

The components of the Schrodinger equation are

\label{eqn:qmLecture9:360}
\begin{aligned}
-i \Hbar \PD{t}{\psi_1} &= -i \Hbar c \PD{x}{\psi_1} + m c^2 \psi_2 \\
-i \Hbar \PD{t}{\psi_2} &= m c^2 \psi_1 + i \Hbar c \PD{x}{\psi_2},
\end{aligned}

The conjugates of these are
\label{eqn:qmLecture9:380}
\begin{aligned}
i \Hbar \PD{t}{\psi_1^\conj} &= i \Hbar c \PD{x}{\psi_1^\conj} + m c^2 \psi_2^\conj \\
i \Hbar \PD{t}{\psi_2^\conj} &= m c^2 \psi_1^\conj – i \Hbar c \PD{x}{\psi_2^\conj}.
\end{aligned}

This gives
\label{eqn:qmLecture9:400}
\begin{aligned}
i \Hbar \PD{t}{\rho}
&=
\lr{ i \Hbar c \PD{x}{\psi_1^\conj} + m c^2 \psi_2^\conj } \psi_1 \\
&+ \psi_1^\conj \lr{ i \Hbar c \PD{x}{\psi_1} – m c^2 \psi_2 } \\
&+ \lr{ m c^2 \psi_1^\conj – i \Hbar c \PD{x}{\psi_2^\conj} } \psi_2 \\
&+ \psi_2^\conj \lr{ -m c^2 \psi_1 – i \Hbar c \PD{x}{\psi_2} }.
\end{aligned}

All the non-derivative terms cancel leaving

\label{eqn:qmLecture9:420}
\inv{c} \PD{t}{\rho}
=
\PD{x}{\psi_1^\conj} \psi_1
+ \psi_1^\conj \PD{x}{\psi_1}
– \PD{x}{\psi_2^\conj} \psi_2
– \psi_2^\conj \PD{x}{\psi_2}
=
\PD{x}{}
\lr{
\psi_1^\conj \psi_1 –
\psi_2^\conj \psi_2
}.

## Question: Gauge transformed probability current ([1] pr. 2.37 (b))

For the gauge transformed Schrodinger equation

\label{eqn:gaugeTxCurrent:20}
\inv{2m} \BPi(\Bx) \cdot \BPi(\Bx) \psi(\Bx, t) + e \phi(\Bx) \psi(\Bx, t) = i \Hbar \PD{t}{}\psi(\Bx, t),

where

\label{eqn:gaugeTxCurrent:40}
\BPi(\Bx) = -i \Hbar \spacegrad – \frac{e}{c} \BA(\Bx),

find the probability current defined by

\label{eqn:gaugeTxCurrent:60}

Equation \ref{eqn:gaugeTxCurrent:20} and its conjugate are

\label{eqn:gaugeTxCurrent:22}
\begin{aligned}
\inv{2m} \BPi \cdot \BPi \psi + e \phi \psi &= i \Hbar \PD{t}{\psi} \\
\inv{2m} \BPi^\conj \cdot \BPi^\conj \psi^\conj + e \phi \psi^\conj &= -i \Hbar \PD{t}{\psi^\conj}
\end{aligned}

which can be used immediately in a chain rule expansion of the probability time derivative

\label{eqn:gaugeTxCurrent:80}
\begin{aligned}
i \Hbar \PD{t}{\rho}
&=
i \Hbar \psi^\conj \PD{t}{\psi} +
i \Hbar \psi \PD{t}{\psi^\conj} \\
&=
\psi^\conj \lr{ \inv{2m} \BPi \cdot \BPi \psi + e \phi \psi } –
\psi \lr{ \inv{2m} \BPi^\conj \cdot \BPi^\conj \psi^\conj + e \phi \psi^\conj
} \\
&=
\inv{2m} \lr{
\psi^\conj \BPi \cdot \BPi \psi
-\psi \BPi^\conj \cdot \BPi^\conj \psi^\conj
}.
\end{aligned}

We have a difference of conjugates, so can get away with expanding just the first term

\label{eqn:gaugeTxCurrent:100}
\begin{aligned}
\psi^\conj \BPi \cdot \BPi \psi
&=
\psi^\conj
\psi \\
&=
\psi^\conj
\lr{ -i \Hbar \spacegrad – \frac{e}{c} \BA } \cdot \lr{ -i \Hbar \spacegrad – \frac{e}{c} \BA }
\psi \\
&=
\psi^\conj
\lr{
+ \frac{e^2}{c^2} \BA^2
}
\psi.
\end{aligned}

Note that in the directional derivative terms, the gradient operates on everything to its right, including $$\BA$$. Also note that the last term has no imaginary component, so it will not contribute to the difference of conjugates.

This gives

\label{eqn:gaugeTxCurrent:120}
\begin{aligned}
\psi^\conj \BPi \cdot \BPi \psi – \psi \BPi^\conj \cdot \BPi^\conj \psi^\conj
&=
\psi^\conj
\lr{
-\Hbar^2 \spacegrad^2 \psi + \frac{i \Hbar e}{c} \lr{ \BA \cdot \spacegrad \psi + \spacegrad \cdot (\BA \psi) }
} \\
\psi
\lr{
-\Hbar^2 \spacegrad^2 \psi^\conj – \frac{i \Hbar e}{c} \lr{ \BA \cdot \spacegrad \psi^\conj + \spacegrad \cdot (\BA \psi^\conj) }
} \\
&=
\frac{i \Hbar e}{c}
\lr{
\psi^\conj
+
\psi
}
\end{aligned}

The first term is recognized as a divergence

\label{eqn:gaugeTxCurrent:140}
\begin{aligned}
&=
+

\end{aligned}

The second term can also be factored into a divergence operation

\label{eqn:gaugeTxCurrent:160}
\begin{aligned}
\psi^\conj
+
\psi
&=
}
+\lr{
} \\
&= 2 \spacegrad \cdot \lr{ \BA \psi \psi^\conj } \\
\end{aligned}

Putting all the pieces back together we have

\label{eqn:gaugeTxCurrent:180}
\begin{aligned}
\PD{t}{\rho}
&=
\inv{2m i \Hbar} \lr{
\psi^\conj \BPi \cdot \BPi \psi
-\psi \BPi^\conj \cdot \BPi^\conj \psi^\conj
} \\
&=
\inv{2m i \Hbar} \lr{
-\Hbar^2
+ \frac{ i \Hbar e}{c} 2 \BA \psi \psi^\conj
} \\
&=
\lr{
\frac{i \Hbar}{2 m} \lr{ \psi^\conj \spacegrad \psi – \psi \spacegrad \psi^\conj }
+ \frac{e}{m c} \BA \psi \psi^\conj
}.
\end{aligned}

From \ref{eqn:gaugeTxCurrent:60}, the probability current must be

\label{eqn:gaugeTxCurrent:200}
\Bj
=
\frac{\Hbar}{2 i m} \lr{ \psi^\conj \spacegrad \psi – \psi \spacegrad \psi^\conj }
– \frac{e}{m c} \BA \psi \psi^\conj,

or
\label{eqn:gaugeTxCurrent:220}
\boxed{
\Bj
=
\frac{\Hbar}{m} \textrm{Im} \lr{ \psi^\conj \spacegrad \psi }
– \frac{e}{m c} \BA \psi \psi^\conj.
}

# References

[1] Jun John Sakurai and Jim J Napolitano. Modern quantum mechanics. Pearson Higher Ed, 2014.

## Update to old phy356 (Quantum Mechanics I) notes.

It’s been a long time since I took QM I. My notes from that class were pretty rough, but I’ve cleaned them up a bit.

The main value to these notes is that I worked a number of introductory Quantum Mechanics problems.

These were my personal lecture notes for the Fall 2010, University of Toronto Quantum mechanics I course (PHY356H1F), taught by Prof. Vatche Deyirmenjian.

The official description of this course was:

The general structure of wave mechanics; eigenfunctions and eigenvalues; operators; orbital angular momentum; spherical harmonics; central potential; separation of variables, hydrogen atom; Dirac notation; operator methods; harmonic oscillator and spin.

This document contains a few things

• My lecture notes.
Typos, if any, are probably mine(Peeter), and no claim nor attempt of spelling or grammar correctness will be made. The first four lectures had chosen not to take notes for since they followed the text very closely.
• Notes from reading of the text. This includes observations, notes on what seem like errors, and some solved problems. None of these problems have been graded. Note that my informal errata sheet for the text has been separated out from this document.
• Some assigned problems. I have corrected some the errors after receiving grading feedback, and where I have not done so I at least recorded some of the grading comments as a reference.
• Some worked problems associated with exam preparation.


text:
# How to implement the timestepping in TR-BDF2 using matlab ode solver as end-points (upper bound)?

Even though i know that i cannot advance the solver ode23tb, which uses TR-BDF2 itself, in just one timestep, i want to set an upper bound on the integration period after which I do something to output and feed the modified output into ode solver again. The upper bounds serve for limiting the timesteps taken in the integration interval tspan = [t_prev ti[j]], (see below), to be as low as possible, hopefully just one. To implement it, i try to do:

    y_prev = rho0;
t_prev = 0
ti = [list of timestep in  TR-BDF2]
j = 1;
while t_prev < tf
#do something to the output
...
# integrate up to adaptive ti in  TR-BDF2 even though inside the interval ode45 has its own timestep
tspan = [t_prev ti[j]]
j = j + 1;
[T, Y] = ode23tb(dydt, tspan, y_prev);
t_prev = T(end,:)
y_prev = Y(end,:)
....
end

But, how can I know what ti is beforehand? I look at https://math.la.asu.edu/~gardner/TRBDF.pdf , but do not have an idea on how to do this.

• It is unclear to me what you are trying to achieve. Why can't you do whatever operations you need to perform in your dydt function? Or alternatively, if you want to run ode23tb in a loop, why can't you simply break tf into some predetermined number of steps? If neither of those options is acceptable, why not do your own implementation of trapezoidal rule (apparently you don't want to take advantage of the automatic time step selection in ode23tb)? Dec 3, 2016 at 13:13
• @Bill Greene Yes neither of the options work for me. Ideally I should implement my own TR-BDF2 with adaptive timestep, which uses the same timestepping as ode23tb. In this way I do not have to specify the tspan. After each timestep, I do something to the output and use this to feed into TR-BDF2 and advance in another timestep.... Dec 3, 2016 at 23:42
• @Bill Greene However, the adaptive timestep version of TR-BDF2 is a lot difficult to implement. I wonder if you know where I can find this? Dec 3, 2016 at 23:43
• @Bill Greene In dydt function, the dydt function is evaluated at every increment. In a single timestep, there are several increments, for example, in Runge–Kutta methods. So the architecture here is: increment $\subset$ timestep $\subset$ timespan Dec 4, 2016 at 3:51
• You might be able to use the event mechanism of the ode solvers to do what you want: mathworks.com/help/matlab/math/ode-event-location.html Dec 4, 2016 at 15:44


text:
# Types of Fraction

## Kinds of Fraction

Fractions are amongst the most common terms that are used in maths for determining the parts of a whole object. There are generally six types of fraction:

1. Proper fraction

2. Improper fraction

3. Mixed fraction

4. Like fraction

5. Unlike Fraction

6. Equivalent fraction

The kinds of fraction are classified depending on the numerator and the denominator of the given fraction. We will discuss here in this article about the different types of fractions and have a look at the types of fraction with example.

In the earlier classes, you came across the concept of the whole numbers to measure different quantities. However, in the real-life scenarios, all the measured quantities cannot be in the form of the perfect whole numbers. You might have to deal with the parts and portions of the whole things, and this is when the concept of the fraction comes into the picture.

### Fraction and its Types

A fraction refers to the ratio of two numbers. The upper number of the fraction is known as the numerator and the lower number of the fraction is called the denominator. When the whole of something is divided into several numbers of parts, each part is called a fraction. Consider the example given below:

Let us learn about these different types of fraction in maths in detail.

### Proper and Improper Fraction

Let us learn about what is proper and improper fraction.

Proper Fraction

A fraction in which the numerator is less than the denominator is known as a proper fraction.

1. The value of the proper fraction after the further simplification of the fraction is always less than 1.

Consider the example below:

Improper Fraction

A fraction where the numerator is greater than the denominator, then it is known as an improper fraction.

1. All the natural numbers can be easily represented in the form of fractions when the denominator is equal to 1 always.

2. The simplification of the improper fraction would result in the value that is greater than or equal to 1 but is not less than 1.

Consider the following example:

### Mixed Fraction

A mixed fraction refers to the combination of the natural number and the fraction. It is basically a kind of an improper fraction.

1. Mixed fractions are always possible to be converted into a proper fraction.

2. An improper fraction can also be converted into the mixed fraction.

3. The value of the mixed fraction is greater than 1 always.

Consider the given example:

### Like and Unlike Fractions

Like Fractions

The fractions that have the same denominators are called as the like like fractions. Consider the following example:

The simplification of the like fractions is easier since the denominators are the same. For example, you have to simplify the following equations:

$\frac{2}{5} + \frac{5}{5} + \frac{6}{5} + \frac{8}{5} + \frac{9}{5}$

= $\frac{2 + 5 + 6 + 8 + 9}{5} = \frac{30}{5} = 6$

Unlike Fractions

The fractions that have unequal denominators or different kinds of denominators are referred to as the unlike fractions. Consider the example given:

The simplification of the unlike fractions is a bit tricky and lengthy since you first need to factorize the denominators and then simplify them in the case of the addition and subtraction.

For example, you need to add $\frac{1}{2}$and $\frac{1}{3}$.

You first need to find the LCM of the two numbers 2 and 3 which is 6.

Then, multiply $\frac{1}{2}$ by 3 and $\frac{1}{3}$ by 2.

The fractions that you would get are $\frac{3}{6}$ and $\frac{2}{6}$.

When you add them together, you get

$\frac{3}{6} + \frac{2}{6} = \frac{5}{6}$

### Equivalent Fractions

When two or more than two fractions have the same result after the simplification and they represent the same portion of the whole object, then such types of fractions are equal to one another and are known as the equivalent fractions. Consider the following example:

### Solved Examples

Let us now look at some of the solved examples based on the types of fractions worksheets.

Example 1:

$\frac{4}{7}$of a number results to 84. Find out the number.

Solution:

According to the given problem,

$\frac{4}{7}$of the number = 84

Hence, the number = $84 \times \frac{7}{4}$

Solving $84 \times \frac{7}{4}$, you get,

$21 \times 7 = 147$

Hence, the given number is 147.

Example 2:

One – half of the students in a school are girls, and $\frac{3}{5}$ of these girls are studying in the lower classes. What fraction of these girls are studying in the lower classes?

Solution:

The fraction of the girls studying in a school = $\frac{1}{2}$

The fraction of the girls studying in the lower classes = $\frac{3}{5} {\text{of}} \frac{1}{2}$

= $\frac{3}{5} \times \frac{1}{2}$

Solving this, you would get,

= $\frac{3}{5} \times \frac{1}{2} = \frac{3}{10}$

Therefore, the fraction of the girls studying in the lower classes is $\frac{3}{10}$.FAQs (Frequently Asked Questions)

1. How Many Types of Fractions are There?

A fraction is a number that compares a part of a given object or a set with the whole object. The quotient of the two whole numbers is denoted in the form of x/y. The fraction is called the part of the whole or the part of the collection. The different types of fractions are as follows:

1. Proper Fractions: the fractions whose numerator is smaller than the denominator

2. Improper Fractions: the fractions whose numerator is greater than the denominator

3. Like Fractions: the fractions having the same denominators

4. Unlike Fractions: the fractions having different denominators

5. Mixed Fractions: the fractions consisting of a whole number along with a proper fraction

6. Equivalent Fractions: the fractions which when simplified, give you the same value of the portion of the whole object.

2. What is a Proper and Improper Fraction?

A proper fraction is a fraction in which its numerator is smaller than its denominator. The proper fraction is part of the whole object. Examples of a proper fraction are:

⅖, ⅓, 6/11, etc.

An improper fraction refers to a fraction in which its numerator is greater than its denominator. The improper fraction is greater than the part of the whole. Examples of an improper fraction include:

5/2, 11/3, 9/2, etc.


text:
## CryptoDB

### Paper: Private Locally Decodable Codes

Authors: Rafail Ostrovsky Omkant Pandey Amit Sahai URL: http://eprint.iacr.org/2007/025 Search ePrint Search Google We consider the problem of constructing efficient locally decodable codes in the presence of a computationally bounded adversary. Assuming the existence of one-way functions, we construct {\em efficient} locally decodable codes with positive information rate and \emph{low} (almost optimal) query complexity which can correctly decode any given bit of the message from constant channel error rate $\rho$. This compares favorably to our state of knowledge locally-decodable codes without cryptographic assumptions. For all our constructions, the probability for any polynomial-time adversary, that the decoding algorithm incorrectly decodes any bit of the message is negligible in the security parameter.
##### BibTeX
@misc{eprint-2007-13307,
title={Private Locally Decodable Codes},
booktitle={IACR Eprint archive},
keywords={Computationally Bounded Adversarial Channels, Locally Decodable Codes, Coding Theory, Reed-Muller Codes},
url={http://eprint.iacr.org/2007/025},
note={ICALP 2007 omkant@cs.ucla.edu 13628 received 25 Jan 2007, last revised 24 Apr 2007},
author={Rafail Ostrovsky and Omkant Pandey and Amit Sahai},
year=2007
}