Convex unit distance realizability of G_k
Open Question on Convex Unit Distance Realization of Graphs $G_k$ · arXiv:1903.11287
Status open high confidence
No follow-up work addressing the question of whether the bipartite graphs $G_k$ (with $2^{k+1}$ vertices and $(k+2)2^{k-1}$ edges) can be realized as convex unit distance graphs was found in the literature. Skomra's subsequent research has shifted entirely to stochastic games and tropical geometry, and no paper in the Erdős–Moser unit-distance literature appears to resolve or substantially progress this specific question. The open question remains open as of May 2026.
Reviewer notes. No follow-up found after 5 web calls (1 WebFetch on source paper abstract, 1 WebFetch on Skomra's homepage confirming no related follow-up, 3 WebSearches on related terms). The question is niche — connecting the specific bipartite graph family G_k from the Minkowski sum construction to convex unit distance realizability — and sits at an intersection of combinatorial geometry and forbidden-pattern theory (Aggarwal's forbidden matrices). Skomra's homepage lists no follow-up work on this topic; his research has moved to stochastic games and tropical geometry.
Context
The construction yields a family of bipartite graphs $(G_k)_{k\geq 1}$ with $2^{k+1}$ vertices and $(k+2)2^{k-1}$ edges, connected to the Erdős–Moser unit distance problem for convex $n$-gons. The authors note that if $G_k$ cannot be so realized, finding a forbidden pattern in $G_k$ would extend the list of forbidden matrices of Aggarwal [1], since none of those matrices appears in $G_k$.
Notes. Stated in running prose without a labelled environment; a secondary conditional direction (finding forbidden patterns in $G_k$) is folded into the same passage.
Source paper
Convexly independent subsets of Minkowski sums of convex polygons
Mateusz Skomra, Stéphan Thomassé · 2021-06-02
https://arxiv.org/abs/1903.11287
PDF source