Rant: Commercial publishers suck. Wiley broke my name in a recent article. Even JoCG, which leaves formatting almost entirely up to authors, avoids this.

Luckily, most of the world doesn't have access to the official version so they will see the arXiv version instead.

Pat Morin boosted
Pat Morin boosted

Planar point sets determine many pairwise crossing segments: arxiv.org/abs/1904.08845

János Pach, Natan Rubin, and Gábor Tardos make significant progress on whether every \(n\) points in the plane have a large matching where all edges cross each other. A 1994 paper by Paul Erdős and half a dozen others only managed to prove this for "large" meaning \(\Omega(\sqrt{n})\). The new paper proves a much stronger bound, \(n/2^{O(\sqrt{\log n})}\) (Ryan Williams' favorite function).

Pat Morin boosted

EU falsely calls Internet Archive's major collection pages, scholarly articles, and copies of US government publications "terrorism" and demands they be taken down from the internet: blog.archive.org/2019/04/10/of
(see also boingboing.net/2019/04/11/one-).

The EU is about to vote to require terrorism takedowns to happen within an hour, and these requests are coming on European times when all Internet Archive employees (in California) are asleep, making manual review of these bad takedowns difficult.

Another application of layered $H$-partitions: Planar graphs have bounded non-repetitive chromatic number.


Thue colourings and queue layouts of planar graphs are problems that I've thought about for several years. It's satisfying to see both problems solved, within weeks of each other.

A few weeks ago, I posted a photo of some happy people who had just proven a theorem a few minutes earlier.

That theorem appears in the arXiv today and the theorem is the title of the paper: Planar Graphs Have Bounded Queue Number.


More important than theorem though, is the tool used to prove it: layered $H$-partitions of small layered width where $H$ has small treewidth.

Expect another result tomorrow: Planar Graphs Have Bounded Nonrepetitive Chromatic Number.

Pat Morin boosted

Sandy Irani (one of my colleagues at UCI) is being given the IEEE TCMF Distinguished Service Award for her work chairing the ad hoc committee to combat harassment and discrimination in the theory of computing community, and for then getting many theory conferences to follow its recommendations: focs2019.cs.jhu.edu/awards/

For the committee and its report, see ics.uci.edu/~irani/safetoc.htm

Pat Morin boosted
Pat Morin boosted
Pat Morin boosted

Breaking news in the algorithmic/arithmetic world!

Integer multiplication in time O(n · log n). [1]

It means you can multiply two n-bits integer using roughly n log n operations. It's a *very* important problem because a lot of mathematical software rely on efficient integer multiplication.

It breaks the last best known algorithm [2] (Schönhage–Strassen), that was in O(n · log n · log log n)

[1] hal.archives-ouvertes.fr/hal-0
[2] en.wikipedia.org/wiki/Sch%C3%B

Pat Morin boosted

A comparison of two parallel Canadian grant funding tracks shows that when reviewers are told to focus on the investigator rather than the proposed investigation, they are significantly more biased against women: cbc.ca/news/health/cihr-gender

Pat Morin boosted

How to handle journal referees who ask authors to add unjustified citations to their own papers? Is their misbehavior protected by the anonymity of peer review or can they be publicly named and shamed? retractionwatch.com/2019/02/07

Pat Morin boosted

@patmorin So the most recent publication on the tripod problem itself is not the most up to date? That's disappointing but maybe, given the history of parallel rediscovery, not surprising.

Pat Morin boosted

New post: Orientations of infinite graphs, 11011110.github.io/blog/2019/0

In many cases the existence of an orientation with desired properties can be reduced to its existence in finite subgraphs, using a mathod from Rado (1949).

Recently, Bekos et al made a major breakthrough, showing that planar graphs of bounded degree have bounded queue number.


We were able to generalize this to bounded degree bounded genus graphs.


A recent arXiv preprint on robust spanners. For any \(n\)-point set in \(\mathbb{R}ᵈ\), we show how to construct spanners with \(O(n\log²n\log\log n)\) edges so that, if you remove \(k\) vertices, the remaining graph is a spanner of \(n-(1+ε)k\) of its vertices.


We called these \((1+ε)k\)-robust spanners. Buchin, Har-Peled, and Olah have a much catchier name: 'a spanner for the day after'


Pat Morin boosted

New post: Gurobi versus the no-three-in-line problem

How well can a good but generic integer linear program solver stand up against 20-year-old problem-specific search code?

Two new arXiv preprints:


The first shows that if a graph \(G\) has a non-crossing straight-line drawing (a.k.a. Fáry drawing) in which some set \(S\) of vertices is drawn on a single line then, for any point set \(X\) of size \(|S|\), \(G\) has a Fáry drawing in which the vertices in \(S\) are drawn on the points in \(X\).

The second shows that, in bounded degree planar graphs, one can always find such a set \(S\) of size \(\Omega(n^{0.8})\).


A Mastodon instance for maths people. The kind of people who make \(\pi z^2 \times a\) jokes.

Use \( and \) for inline LaTeX, and \[ and \] for display mode.