J.P. McCarthy: Math Page

MATH7016: Spring 2020, Week 13

May 4, 2020 in MATH7016 | Leave a comment

Keep in mind at all times:

Week 13

Catch Up/Revision of Lab 8 Material

The final assessment, based on Lab 8, takes place 11:00, Tuesday 12 May.

If you have not yet done so, you will undertake the learning described in Week 10. Perhaps you should also look at the theory exercises described in Week 10.

The final assessment will ask you to do the following:

so if you want to send on this work for feedback please do so.

If you submitted a Lab 8 either back before 6 April, or after, I will invite you, if necessary, to take on board the feedback I gave to that submission, and resubmit a corrected version for further feedback.

Submit work — VBA or Theory, catch-up or revision — based on Week 10 to the Lab 8 VBA/Theory Catch-up/Revision II assignment on Canvas by midnight 9 May. If you have any further questions, I am answering emails seven days a week. Email before midnight Monday 11 May to be guaranteed a response Tuesday 12 May. I cannot guarantee that I answer emails sent on Tuesday (although of course I will try).

MATH6040: Spring 2020, Week 13

May 4, 2020 in MATH6040, MATH6040 - Night | Leave a comment

It is my advice to try and find 7 hours per week for MATH6040, and spend that time on it, working your way down through the learning in this announcement.

Keep in mind at all times:

Read the rest of this entry »

MATH7021: Spring 2020, Week 13

May 4, 2020 in MATH7021 | Leave a comment

I recommend that you find (at least) 7 hours per week for MATH7021.

Keep in mind at all times:

Week 13 to Sunday 10 May

Catch Up

ASAP you need to catch up on Week 10, Easter Week 1, and Easter Week 2 (lectures and tutorial) for:

Here is tutorial video for this test.

Chapter 2 Exercises that you should be looking at include:

p.86, Q. 1-4
p.91, Q. 1-7
p.86, Q. 5-6 (harder)

I have developed the following for you to practise your differentiation which you need for Chapter 2 here:

Revision of Differentiation for Undetermined Coefficients.

Any exercises you do can be submitted to Week 13 Exercises by midnight Friday 8 May. If you have any further questions, I am answering emails seven days a week. Email before midnight Sunday 10 May to be guaranteed a response Monday 11 May. I cannot guarantee that I answer emails sent on Monday (although of course I will try).

If possible, submit the images as a single pdf file. To do this, select all the images in a folder, right-click and press print. It will say something like How do you want to print your pictures? Press (Microsoft?) Print to PDF. If possible choose an orientation that has all the images in portrait.

Week 14 to 17 May

The 40% Test on Chapters 2, 4, and Section 3.6 will take place Monday 11 May.

In the form of the Test 1 trust pledge, instructions, and tables, practical information for Test 1 may be found here.

After this you will be invited to do revision on Linear Systems. Here is video based on Q. 1 from the Summer 2019 paper on the back of your manual.

Week 15 to 24 May

The 20% Linear Systems Test will take place Thursday 21 May.

Boxroom Mathematics: Episode I

May 2, 2020 in A1 Leaving Cert Maths, Boxroom Mathematics, Grinds, Leaving Cert | Leave a comment

The videos, here, comprise me going through a full Leaving Cert Higher Level Mathematics Paper, namely 2019, Paper 1.

They’re neither slick, perfect, nor as good as I would like them to be.

The videos are labelled in the descriptions, so if you are looking for, say, Q. 5 you can flick through the videos until you find the question you are looking for (e.g. Q. 5 starts at 17.05 here).

All students are looking for help: but perhaps the student that these videos are best placed to help is a student (eventually) going for a H1 who needs something to be explained in more depth, or to give the thought process behind attacking a more challenging problem.

A Uniqueness Problem

May 1, 2020 in General | Leave a comment

A colleague writes (extract):

Following the same argument as here we can establish that:

Fact 1

The expected number of students to share an exam is $\approx 0.00006$ .

Let the number of exams $\alpha:=6350400$ .

This is an approach that takes advantage of the fact that expectation is linear, and the probability of an event $E$ not happening is

$\displaystyle\mathbb{P}[\text{not-}E]=1-\mathbb{P}[E]$ .

Label the 20 students by $i=1,\dots,20$ and define a random variable $S_i$ by

$\displaystyle S_i=\left\{\begin{array}{cc}1&\text{ if student i has the same exam as someone elese} \\ 0 & \text{ if student i has a unique exam}\end{array}\right.$

Then $X$ , the number of students who share an exam, is given by:

$\displaystyle X=S_1+S_2+\cdots+S_{20}$ ,

and we can calculate, using the linearity of expectation.

$\mathbb{E}[X]=\mathbb{E}[S_1]+\cdots \mathbb{E}[S_{20}]$ .

The $S_i$ are not independent but the linearity of expectation holds even when the addend random variables are not independent… and each of the $S_i$ has the same expectation. Let $p$ be the probability that student $i$ does not share an exam with anyone else; then

$\displaystyle\mathbb{E}[S_i]=0\times\mathbb{P}[S_i=0]+1\times \mathbb{P}[S_i=1]$ ,

but $\displaystyle\mathbb{P}[S_i=0]=\mathbb{P}[\text{ student i does not share an exam}]=p$ , and

$\displaystyle \mathbb{P}[S_i=1]=\mathbb{P}[\text{not-}(S_i=0)]=1-\mathbb{P}[S_i=0]=1-p$ ,

and so

$\displaystyle\mathbb{E}[S_i]=1-p$ .

All of the 20 $S_i$ have this same expectation and so

$\displaystyle\mathbb{E}[X]=20\cdot (1-p)$ .

Now, what is the probability that nobody shares student $i$ ‘s exam?

We need students $1\rightarrow i-1$ and $i+1\rightarrow 20$ — 19 students — to have different exams to student $i$ , and for each there is $\alpha-1$ ways of this happening, and we do have independence here (student 1 not sharing student $i$ ‘s exam doesn’t change the probability of student 2 not sharing student $i$ ‘s exam), and so $\mathbb{P}[\text{(student j not sharing) AND (student k not sharing)}]$ is the product of the probabilities.

So we have that

$\displaystyle p=\left(\frac{\alpha-1}{\alpha}\right)^{19}$ ,

and so the answer to the question is:

$\displaystyle\mathbb{E}[X]=20\cdot \left(1-\left(\frac{\alpha-1}{\alpha}\right)^{19}\right)\approx 0.00005985\approx 0.00006$ .

We can get an estimate for the probability that two or more students share an exam using Markov’s Inequality:

$\displaystyle\mathbb{P}[X\geq 2]\leq \frac{\mathbb{E}[X]}{2}\approx 0.00003=0.003\%$

Fact 2

This estimate is tight: the probability that two or more students (out of 20) share an exam is about 0.003%.

This tallies very well with the exact probability which can be found using a standard Birthday Problem argument (see the solution to Q. 7 here) to be:

$\mathbb{P}[X\geq 2]\approx 0.0000299191\approx 0.003\%$

The probability that two given students share an exam is $1/\alpha\approx 0.00001575\%$

Fact 3

The expected number of shared questions between two students is 6.6

Take students 1 and 2. The questions are in four bins: two of ten, two of five. Let $B_i$ be the number of questions in bin $i$ that students 1 and 2 share. The expected number of shared questions, $Q$ , is:

$\displaystyle \mathbb{E}[Q]=\sum_{i=1}^4\mathbb{E}[B_i]$ ,

and the numbers are small enough to calculate the probabilities exactly using the hypergeometric distribution.

The calculations for bins 1 and 2, and bins 3 and 4 are the same. The expectation

$\displaystyle\mathbb{E}[B_1]=\sum_{j=0}^5j\mathbb{P}[B_1=j]$ .

Writing briefly $p_j=\mathbb{P}[B_1=j]$ , looking at the referenced hypergeometric distribution we find:

$\displaystyle p_j=\frac{\binom{5}{j}\binom{5}{5-j}}{\binom{10}{5}}$

and we find:

$\displaystyle\mathbb{E}[B_1]=\mathbb{E}[B_2]=\frac52$

Similarly we see that

$\displaystyle\mathbb{E}[B_3]=\mathbb{E}[B_4]=\frac{4}{5}$

and so, using linearity:

$\displaystyle\mathbb{E}[Q]=\frac52+\frac52+\frac45+\frac45=6.6$

This suggests that on average students share about 50% of the question paper. Markov’s Inequality gives:

$\displaystyle\mathbb{P}[Q\geq 7]\underset{\approx}{\leq} 0.9429$ ,

but I do not believe this is tight.

Calculating this probability exactly is tricky because there are many different ways that students can share a certain number of questions. We would be looking at something like “multiple hypergeometric”, and I would calculate it as the event not-(0 or 1 or 2 or 3 or 4 or 5 or 6).

I think the $\mathbb{E}[Q]=6.6$ result is striking enough at this time!

MATH7016: Spring 2020, Week 12

April 25, 2020 in MATH7016 | Leave a comment

Keep in mind at all times:

Week 12/13

11:00 Tuesday 28 April, Week 12: Assessment Based on Lab 7

Students can submit work — VBA or Theory, catch-up or revision — based on Week 9 Lab 7 VBA/Theory Catch-up/Revision II assignment by today, Saturday 25 April.

If you have any further questions, I am answering emails seven days a week. Email before midnight Monday 27 April to be guaranteed a response Tuesday 28 April. I cannot guarantee that I answer emails sent on Tuesday morning (although of course I will try).

Catch Up/Revision of Lab 8 Material

If you have not yet done so, you will undertake the learning described in Week 10.

If you feel like doing even more theory work on top of this, you will be asked to consider looking at the theory exercises described in Week 10.

If you have already conducted this learning, and submitted a Lab 8 either back before 6 April, or after, I will invite you, if necessary, to take on board the feedback I gave to that submission, and resubmit a corrected version for further feedback.

Students will be able submit work — VBA or Theory, catch-up or revision — based on Week 10 to a Lab 8 VBA/Theory Catch-up/Revision assignment on Canvas (due dates 3 May and 9 May).

Week 14

11:00 Tuesday 12 May, Week 14: Assessment Based on Lab 8

This assessment will ask you to do the following:

MATH6040: Spring 2020, Week 12

April 25, 2020 in MATH6040, MATH6040 - Night | Leave a comment

It is my advice to try and find 7 hours per week for MATH6040, and spend that time on it, working your way down through the learning in this announcement.

Keep in mind at all times:

Read the rest of this entry »

MATH7021: Spring 2020, Week 12

April 25, 2020 in MATH7021 | Leave a comment

I hope to have Assignment 2 corrected and the marks communicated to you within 48 hours. That is a hope not a promise.

Many of you only submitted Assignment 2 late in the day and need to find at least (in my opinion) 7 hours per week to catch up on the other material.

Keep in mind at all times:

Week 12 to Sunday 3 May

Catch Up

ASAP you need to catch up on Week 10, Easter Week 1, and Easter Week 2 (lectures and tutorial).

This learning is directed towards the 40% Test (based on Chapter 2, Section 3.6, and Chapter 4). Here is tutorial video for this test.

Chapter 2 Exercises that you should be looking at include:

p.86, Q. 1-4
p.91, Q. 1-7
p.86, Q. 5-6 (harder)

I have developed the following for you to practise your differentiation which you need for Chapter 2 here:

Revision of Differentiation for Undetermined Coefficients.

Any exercises you do can be submitted to Week 12 Exercises by midnight Sunday 3 May.

Week 13 to 10 May

You will be invited to catch up on the Week 10, Easter Week 1, and Easter Week 2 learning, as well as do revision on Chapter 2. You will be asked to submit work for feedback by midnight Friday 8 May.

Week 14 to 17 May

Provisionally, the 40% Test on Chapters 2, 4, and Section 3.6 will take place Monday 11 May.

In the form of the Test 1 trust pledge, instructions, and tables, practical information for Test 1 may be found here.

After this you will be invited to do revision on Linear Systems. Here is video based on Q. 1 from the Summer 2019 paper on the back of your manual.

Week 15 to 24 May

Provisionally, the 20% Linear Systems Test will take place Thursday 21 May.

Almost All Trees have Quantum Symmetry

April 23, 2020 in arXiv, Research | 1 comment

Some notes on this paper.

1. Introduction and Main Results

A tree has no symmetry if its automorphism group is trivial. Erdos and Rényi showed that the probability that a random tree on $n$ vertices has no symmetry goes to zero as $n\rightarrow \infty$ .

Banica (after Bichon) wrote down with clarity the quantum automorphism group of a graph. It contains the usual automorphism group. When it is larger, the graph is said to have quantum symmetry.

Lupini, Mancinska, and Roberson show that almost all graphs are quantum antisymmetric. I am fairly sure this means that almost all graphs have no quantum symmetry, and furthermore for almost all (as $n\rightarrow \infty$ ) graphs the automorphism group is trivial.

The paper in question hopes to show that almost all trees have quantum symmetry — but at this point I am not sure if this is saying that the quantum automorphism group is larger than the classical.

2. Preliminaries

2.1 Graphs and Trees

Standard definitions. No multi-edges. Undirected if the edge relation is symmetric. As it is dealing with trees, this paper is concerned with undirected graphs without loops, and identify $V=\{v_1,\dots,v_n\}\cong \{1,2,\dots,n\}$ . A path is a sequence of edges. We will not see cycles if we are discussing trees. Neither will we talk about disconnected graphs: a tree is a connected graph without cycles (this throws out loops actually.

The adjacency matrix of a graph is a matrix $A=(a_{ik})_{i,j\in V}$ with $a_{ij}=1$ iff there is an edge connected $i$ and $j$ . The adjacency matrix is symmetric.

2.2 Symmetries of Graphs

An automorphism of a graph $\Gamma$ is a permutation of $V$ that preserves adjacency and non-adjacency. The set of all such automorphisms, $\text{Aut }\Gamma$ , is a group where the group law is composition. It is a subgroup of $S_n$ , and $S_n$ itself can be embedded as permutation matrices in $M_n(\mathbb{C})$ . We then have

$\text{Aut }\Gamma=\{\sigma\in S_n\,:\,\sigma A=A\sigma\}\subseteq S_n$ .

If $\text{Aut }\Gamma=\{e\}$ , it is asymmetric. Otherwise it is or rather has symmetry.

2.3 Compact Matrix Quantum Groups

A compact matrix quantum group is a pair $(C(G),u)$ , where $C(G)$ is a unital $\mathrm{C}^\ast$ -algebra, and $u=(u_{ij})_{i,j=1}^n\in M_n(C(G))$ is such that:

$C(G)$ is generated by the $u_{ij}$ ,
There exists a morphism $\Delta:C(G)\rightarrow C(G)\otimes C(G)$ , such that $\Delta(u_{ij})=\sum_{k=1}^n u_{ik}\otimes u_{kj}$
$u$ and $u^T$ are invertible (Timmermann only asks that $\overline{u}=(u_{ij}^\ast)$ be invertible)

The classic example (indeed commutative examples all take this form) is a compact matrix group $G\subseteq U_n(\mathbb{C})$ and $u_{ij}:G\rightarrow \mathbb{C}$ the coordinates of $G$ .

Example 2.3

The algebra of continuous functions on the quantum permutation group $S_n^+$ is generated by $n^2$ projections $u_{ij}$ such that the row sums and column sums of $u=(u_{ij})$ both equal $\mathbf{1}_{S_n^+}$ .

The map $\varphi:C(S_{n}^+)\rightarrow C(S_n)$ , $u_{ij}\mapsto \mathbf{1}_{\{\sigma\in S_n\,|\,\sigma(j)=i\}}$ is a surjective morphism that is an isomorphism for $n=1,2,3$ , so that the sets $\{1\},\,\{1,2\},\,\{1,2,3\}$ have no quantum symmetries.

2.4 Quantum Symmetries of Graphs

Definition 2.4 (Banica after Bichon)

Let $\Gamma=(V,E)$ be a graph on $n$ vertices without multiple edges not loops, and let $A$ be its adjacency matrix. The quantum automorphism group $\text{QAut }\Gamma$ is defined as the compact matrix group with $\mathrm{C}^\ast$ -algebra:

$\displaystyle C(\text{QAut }\Gamma)=C(S_n^+)/\langle uA=Au\rangle$

For me, not the authors, this requires some work. Banica says that $\langle uA=Au\rangle$ is a Hopf ideal.

A Hopf ideal is a closed *-ideal $I\subset C(G)$ such that

$\Delta(I)\subset C(G)\otimes I+I\otimes C(G)$ .

Classically, $I$ the set of functions vanishing on a distinguished subgroup. The quotient map is $f\mapsto f+I$ , and $f+I=g+I$ if their difference is in $I$ , that is if they agree on the subgroup.

The classical version of $Au=uA$ ends up as $a_{ij}=a_{\sigma(i)\sigma(j)}$ … the group in question the classical $\text{Aut }\Gamma$ . In that sense perhaps $Au=uA$ might be better given as $fA=Af$ .

Easiest thing first, is it a *-ideal? Well, take the adjoint of $fA=Af\Rightarrow A^*f^*=f^*A^*$ and $A=A^*$ so $I$ is *closed. Suppose $f\in I$ and $g\in C(S_n^+)$ … I cannot prove that this is an ideal! But time to move on.

3. The Existence of Two Cherries

In this section the authors will show that almost all trees have two cherries. Definition 3.4 says with clarity what a cherry is, here I use an image [credit: www-math.ucdenver.edu]:

cherry

(3,5,4) and (7,9,8) are cherries

Remark 3.2

If a graph admits a cherry $(u_1,u_2,v)$ , the transposition $(u_1\quad u_2)$ is a non-trivial automorphism.

Theorem 3.3 (Erdos, Réyni)

Almost all trees contains at least one cherry in the sense that

$\displaystyle \lim_{n\rightarrow \infty}\mathbb{P}[C_n\geq 1]=1$ ,

where $C_n$ is #cherries in a (uniformly chosen) random tree on $n$ vertices.

Corollary 4.3

Almost all trees have symmetry.

The paper claims in fact that almost all trees have at least two cherries. This will allow some $S_4^+$ action to take place. This can be seen in this paper which is the next point of interest.

MATH7016: Spring 2020, Week 11

April 19, 2020 in MATH7016 | Leave a comment

Keep in mind at all times:

Week 11

20% VBA Assessment Based on Lab 6

Thank you to everyone for completing the assignment.

Catch Up/Revision

You are advised to catch-up on the learning described in Week 9.

If you have already conducted this learning, and submitted a Lab 7 either back before 30 March, or after, I will invite you, if necessary, to take on board the feedback I gave to that submission, and resubmit a corrected version for further feedback. If you feel like doing even more theory work on top of this, you will be asked to consider looking at the theory exercises described in Week 9.

Students can submit work — VBA or Theory, catch-up or revision — based on Week 9 to the Lab 7 VBA/Theory Catch-up/Revision I assignment on Canvas (by Sunday 19 April), or Lab 7 VBA/Theory Catch-up/Revision II assignment by Saturday 25 April.

Week 12/13

PROVISIONAL: Tuesday 28 April, Week 12: Assessment Based on Lab 7

Catch Up/Revision

If you have not yet done so, you will undertake the learning described in Week 10.

If you feel like doing even more theory work on top of this, you will be asked to consider looking at the theory exercises described in Week 10.

Students will be able submit work — VBA or Theory, catch-up or revision — based on Week 10 to a Lab 8 VBA/Theory Catch-up/Revision assignment on Canvas.

I may have two due dates. Perhaps Sunday 3 May and Saturday 9 May.

PROVISIONAL: Tuesday 12 May, Week 14: Assessment Based on Lab 8

This assessment will ask you to do the following:

	J.P. McCarthy on MATH6040: Spring 2022, Week…
	J.P. McCarthy on MATH6040: Spring 2022, Week…
	J.P. McCarthy on MATH7019: Winter 2020, Week…
	J.P. McCarthy on MATH7019: Winter 2020, Week…
	A Sufficient Conditi… on Almost All Trees have Quantum…

J.P. McCarthy: Math Page

Week 13

Catch Up/Revision of Lab 8 Material

Share this:

Share this:

Week 13 to Sunday 10 May

Catch Up

Week 14 to 17 May

Week 15 to 24 May

Share this:

Share this:

Fact 1

Fact 2

Fact 3

Share this:

Week 12/13

11:00 Tuesday 28 April, Week 12: Assessment Based on Lab 7

Catch Up/Revision of Lab 8 Material

Week 14

11:00 Tuesday 12 May, Week 14: Assessment Based on Lab 8

Share this:

Share this:

Week 12 to Sunday 3 May

Catch Up

Week 13 to 10 May

Week 14 to 17 May

Week 15 to 24 May

Share this:

1. Introduction and Main Results

2. Preliminaries

2.1 Graphs and Trees

2.2 Symmetries of Graphs

2.3 Compact Matrix Quantum Groups

Example 2.3

2.4 Quantum Symmetries of Graphs

Definition 2.4 (Banica after Bichon)

3. The Existence of Two Cherries

Remark 3.2

Theorem 3.3 (Erdos, Réyni)

Corollary 4.3

Share this:

Week 11

20% VBA Assessment Based on Lab 6

Catch Up/Revision

Week 12/13

PROVISIONAL: Tuesday 28 April, Week 12: Assessment Based on Lab 7

Catch Up/Revision

PROVISIONAL: Tuesday 12 May, Week 14: Assessment Based on Lab 8

Share this:

Recent Comments

Categories