Pat Morin @patmorin@mathstodon.xyz
Professor of Computer Science at Carleton University
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.
Planar point sets determine many pairwise crossing segments: https://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).
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: https://blog.archive.org/2019/04/10/official-eu-agencies-falsely-report-more-than-550-archive-org-urls-as-terrorist-content/
(see also https://boingboing.net/2019/04/11/one-hour-service.html).
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.
https://arxiv.org/abs/1904.05269
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.
https://arxiv.org/abs/1904.04791
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.
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: http://focs2019.cs.jhu.edu/awards/
For the committee and its report, see https://www.ics.uci.edu/~irani/safetoc.html
Photos from a recent computational geometry workshop in Barbados: https://11011110.github.io/blog/2019/04/07/photos-from-barbados.html
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] https://hal.archives-ouvertes.fr/hal-02070778/document
[2] https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm
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: https://www.cbc.ca/news/health/cihr-gender-bias-1.5009611
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? https://retractionwatch.com/2019/02/07/the-case-of-the-reviewer-who-said-cite-me-or-i-wont-recommend-acceptance-of-your-work/
@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.
New post: Orientations of infinite graphs, https://11011110.github.io/blog/2019/01/17/orientations-infinite-graphs.html
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.
https://arxiv.org/abs/1811.00816
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.
https://arxiv.org/abs/1812.09913
We called these \((1+ε)k\)-robust spanners. Buchin, Har-Peled, and Olah have a much catchier name: 'a spanner for the day after'
New post: Gurobi versus the no-three-in-line problem
https://11011110.github.io/blog/2018/11/12/gurobi-vs-no.html
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:
https://arxiv.org/abs/1811.03432
https://arxiv.org/abs/1811.03427
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})\).
Professor of Computer Science at Carleton University
