@bremner apparently it's the Carleton County equivalent of "it's a whole new ballgame."

Pat Morin boosted

A counterexample to the Ringel circle problem: arxiv.org/abs/2112.05042, via gilkalai.wordpress.com/2021/12

Ringel asked whether systems of circles, tangent only in pairs, can be colored with O(1) colors so no two tangent circles have the same color. Five colors were known to be necessary but unknown to be sufficient; see the lead image of my old web page ics.uci.edu/~eppstein/junkyard

Now Davies, Keller, Kleist, Smorodinsky, and Walczak have found systems of circles requiring arbitrarily many colors.

Pat Morin boosted

TheoretiCS, a new diamond-open-access journal in all areas of theoretical computer science: theoretics.episciences.org/

It is being run as an overlay of arXiv, through the Episciences platform for such overlays, with Javier Esparza and Uri Zwick as editors-in-chief and a large and distinguished editorial board.

Just wrapping up my second week at the Banff International Research Station. This week's workshop is on Statistics and Machine Learning. The highlight, for an outsider like me, has definitely been Tselil Schramm's mini-course on the sum-of-squares algorithmic paradigm. A decade's worth of research nicely condensed into four one-hour lectures.

Reviewing my notes for my grad class on Pătrașcu's dynamic partial sums lower bound. It still makes me sad every time.

@eptf I knew about (and always use) -x, but -u is new to me, probably because I typically don't work much with environment variables. These days, though, python has mostly replaced bash scripts for me.

Five talks from CanaDAM 2021 introducing graph product structure theory and its applications:


This is probably the best / quickest introdoctrination to the topic currently available.

Today I'm heading to the clinic to receive my first dose of the AstraZeneca vaccine. Ignoring the possibility that it might save me from death by covid, the worst case estimates suggest that this increases my odds of dying in the next 365 days from 1/444 to 1/442. I can live with that.


@11011110 So that I wouldn't have to change my teaching style too much I ended up setting up a mini lecture theatre in my basement, from which I did live YouTube broadcasts.

That wasn't without its moments.


An implementation of the Product Structure Theorem for planar graphs, in Python:


Not exactly industrial-strength, and leans towards simplicity over performance. Still, it can decompose 100k-vertex triangulations in a few seconds. I'm open to feature requests.

Good to see that the pandemic hasn't affected every aspect of our lives. SoDA is still charging exorbitant registration fees:

Tip: When you "attend" an online conference, book everything off: teaching, meetings, etc. I'm currently "attending" a conference and have only gotten to see one live session since I've been in meetings or teaching the rest of the time.

@christianp Ha! I forgot that Canada and the UK share Remembrance Day.

11:00 was during my class today. It's surprisingly hard to stand still in front of a camera while waiting for a minute to elapse.

Pat Morin boosted

New blog post, Hex, books, and queues: 11011110.github.io/blog/2020/1

And new arXiv preprint, Stack-number is not bounded by queue-number (with Vida Dujmović, Robert Hickingbotham, Pat Morin, and David R. Wood), arxiv.org/abs/2011.04195

Banff Alberta, Election Day, 2016, Alan Frieze and Luc Devroye watching election results arrive.

How many integer colours are sufficient to colour an \(n\)-vertex planar graph so that the maximum colour encountered along any path of length at most 2 occurs only once along that path? It turns out that the correct answer is \(\Theta(\log n/\log\log\log n)\). The triple-log comes from the fact every planar graph is contained in the strong product of a planar 3-tree and a very simple graph.


Pat Morin boosted

Congratulations to my (now former) student, Luís Fernando Schulz Xavier da Silveira, who successfully defended his PhD thesis titled Turán Triangles, Cell Covers, Road Placement and Train Scheduling on Monday.

This is the first thesis defense I've taken part in where no two participants were in the same room.

Show older

The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!