Blog of Matthew Daws

Spectral bounds on the chromatic number

Recently Clive Elphink gave us a nice seminar where he discussed some of his "conjectures in spectral graph theory". Clive has an interesting history: after a career in business, he is now semi-retired and returned to research mathematics. By his own admission, he is more on the experimental side, and his talk said almost nothing about proofs. Here is a old result in this area:

Theorem [Hoffman]: We have that \( \chi(G) \geq 1 + \frac{\lambda_1}{-\lambda_n} \).

I explain the notation shortly, but in words, this result relates a vertex colouring of a graph to the eigenvalues of the adjacency matrix. To me, this seems hugely surprising, as why would the spectrum of \( A \) have anything to do with a vertex colouring? I want to explain the elegant arguments of Elphick and Wocjan, and also some generalisations to quantum colourings (in part 2).

Fixed points of complete positive maps

The first of hopefully a few posts about actual Mathematics, the context of which will follow. In Watrous's QIT book, Theorem 4.25 states the following:

Let \( \Phi:\mathbb M_n\rightarrow\mathbb M_n \) be a unital quantum channel with Kraus representation \( \Phi(x) = \sum_a A_a x A_a^* \). Then \( \Phi(x)=x \) if and only if \( A_a x = x A_a \) for each \( a \).

(Here I translate slightly the language). Whenever I see a statement about quantum channels, I ask myself if I can translate it into a more Operator Algebraic statement making more use of the Stinespring representation theorem, for example. After much messing about, I realised that the key property is that \( \Phi \) is trace preserving, and that this, together with multiplicative domain theory, can be used to give a simple proof. (Well, maybe not simple, but one adding some context.)

Cheap mathematics

A long-time-coming comment on a post by John Baez about "bargin-basement mathematics". (But let's not do ourselves down-- the rest of the system is more than happy enough to do that for us-- so I shall say "cheap" not quite "bargain-basement").

The setup here is a (monotone Galois connection), which consists of two posets \( X \) and \( Y \), and order-preserving maps \[ L:X\rightarrow Y, \qquad R:Y\rightarrow X, \] which satisfy \( L(x)\leq y \) if and only if \( x\leq R(y) \). The exercise, whose solution I'll give below, is that while \( L \) and \( R \) may of course fail to be mutual inverses, if we define \( X'=R(Y) \) and \( Y'=L(X) \) then \( L,R \) restrict to \( X',Y' \) respectively to become mutual inverses.

Mittag-Leffler

I spend last week at the Institute Mittag-Leffler in a suburb of Stockholm, attending the Noncommutative Harmonic Analysis and Quantum Information conference. The institute is lovely, being comprised of a large, old mansion, various accommodation blocks, a seminar building, all set in lovely grounds. The weather couldn't have been nicer (well, too hot for me, but I'd probably be happy spending the summer near the arctic circle). As the history page explains, the mansion belonged to Mittag-Leffler, and was left in his will to form a Mathematics research institute, but sadly the Great Depression eroded his legacy to the extent that the institute couldn't function as envisaged until the latter part of the 20th century, when additional funding was found. If you get the chance to visit, I highly recommend it.

The mansion also houses an amazing Mathematics library. I took a little photo:

Origami

I got roped into (okay, volunteered for) giving a talk at UClan's Japan Day on the theme of Origami. To quote Tom Lehrer, this I know from nothing. But one can learn, and I hope I said something interesting in my short talk.

Outside the office

There has, for more time than I care to think about, been a large, empty display board right outside my office. My fellow corridor occupants, being (astro)physicists, actually have a culture of making posters, which are then perfect for displaying on said boards. But what is a Mathematician to do? I have been planning this for, again, longer than I care to remember, but finally here it is:

The evenings spent watching Masterchef and cutting out bits of paper were, well, almost worth it. It occurs to me that the display of images on this site is not particularly "responsive", but who has the time?

The Collatz Conjecture is well-known, and fun to play around with (especially into an introduction to programming class). Some recent progress was Tao's work but this all is way outside my zone of expertise. Still, I think it does make for a nice use of a notice board.

Conferencing again, and how to spend time

Spending unexpected time in Poznan airport, after a cancelled flight. I have been at the Noncommutative harmonic analysis and quantum groups conference at Bedlewo palace, postponed at least once due to Covid, most recently from last year.

The conference was good, in the round. I have gotten out of the habit of travel, at least in part due to Covid, and had initially not planned to attend in person. I am trying to be more open to new experiences (to say yes to things a bit more, and perhaps say no to some other things). And, cancelled flight not withstanding, travelling in person was a good thing. I got to catch up with some people I knew already, and a chance to meet some new people. The talks were good. Even the conference outing, kayaking on the river- another chance to say yes to something I would not normally do so- was different, fun, if frustratingly hard to do well.

LaTeX editing and typing

Continuing the theme of the previous post, this time concerning latex on the desktop. But first, typing. A confession: I am a "hybrid" typist. Or, let us be optimistic, and say was a hybrid typist. I know where all the keys are, but I used to use mainly my index fingers, sometimes the middle fingers. On a old IBM keyboard, or whatever horror one of my laptops, or work, has provided for me. I had deluded myself that this was sufficient, but from observing people who can type properly, finally decided it was not.

I have also unpacked and started using this: