Papers

Brooks' Theorem is a foundational result in graph coloring: if a graph is connected, not a clique, and has maximum degree $\Delta \geq 3$, then it admits a proper $\Delta$-coloring. In this paper, we give a new proof of a much stronger result: every such graph admits exponentially many proper $\Delta$-colorings. Exponential lower bounds have been obtained previously by applying the Combinatorial Nullstellensatz. In contrast, our proof is via a surprisingly simple and constructive analysis of a textbook greedy coloring algorithm. The entire argument is accessible to non-specialists. We extend our techniques to provide quantitative lower bounds on the number of colorings in several more general settings, namely $\Delta$-length list coloring, degree-length list coloring (degree-choosability), and degenerate partitioning. In the latter setting, one is asked to partition the vertices such that each partite set induces a subgraph of bounded degeneracy. In contrast to the other coloring variants considered, no clean Brooks-type characterization is possible, since it is known that for some combinations of parameters determining the existence of even one valid partition is NP-hard. We give a new reduction which significantly extends the parameter regime for which determining the existence of a valid partition is NP-hard. Finally, we give a new proof of the classic degree-choosability theorem, generalizing the techniques behind a recent proof of Brooks' Theorem.

Let $G$ be a finite simple graph on the vertex set $[n]$, and let $\Gamma(G)$ be the Cayley graph of the symmetric group $S_n$ generated by the transpositions corresponding to the edges of $G$. We study the inverse spectral problem for the assignment $G\mapsto \Gamma(G)$ through the group-algebra operator $A_G=\sum_{\{i,j\}\in E(G)}(ij)$ and its regular spectral moments $M_k(G)=\operatorname{tr}(A_G^k)$. The moments admit two all-order forms: a universal support expansion in non-induced subgraph counts of $G$, and a representation-theoretic expansion over the irreducible representations of $S_n$. We compute the first nontrivial moments through order six. In particular, the fourth moment already contains the Coxeter triangle relation and determines the signed local invariant $6N_{K_3}(G)-N_{P_3}(G)$, rather than $N_{P_3}(G)$ alone. Consequently, for triangle-free graphs the spectrum determines the second moment of the degree sequence. We also give a simplified sixth-moment formula for triangle-free graphs, showing that in this class the spectrum determines $5N_{K_{1,3}}(G)+2N_{P_4}(G)+12N_{C_4}(G)$. Further structural consequences include bipartiteness and spectral symmetry of $\Gamma(G)$, a precise connectedness test, and the identification of the standard irreducible component with the shifted graph Laplacian $mI-L_G$.

Let $M$ be a binary matroid of rank $r$ with no $F_7$-minor, and let $B_M^\star$ denote the maximum of its basis-generating polynomial over nonnegative weights of total mass $r$. We prove the sharp inequality $B_M^\star\leq 2^r/(r+1)$, with equality holding if and only if the nonloop simplification of $M$ is $M(K_{r+1})$. Binary matroids with no $F_7$-minor also form the largest minor-closed class of matroids on which this inequality holds.

Motivated by a recent paper where a convex portfolio optimization problem formulated by means of the entropic value-at-risk is solved via a primal-dual interior-point method, we propose an alternative way of dealing with such problems by means of splitting proximal point methods and making use of Lagrange duality. Numerical experiments where the new method is implemented for solving some portfolio optimization problems are presented as well. As byproducts, we also provide formulae for the projection on the epigraph of the weighted Shannon entropy, and the conjugate function and subdifferential of entropic value-at-risk.

We consider the future of mathematics as a profession in a world where artificial intelligence may surpass human mathematicians in essentially every technical task. Through an informal dialogue, we explore why human mathematical expertise might nevertheless remain valuable, what kinds of expertise universities should cultivate, and how graduate education might adapt. We also discuss the institutional and economic uncertainties that threaten the continued existence of a thriving mathematical profession, even if the value of human mathematical understanding endures.

We prove sharp improved Sobolev inequalities on $\mathbb S^n$, $n\ge3$, for antipodally even functions and for axially symmetric functions whose critical density $|u|^{2n/(n-2)}$ has zero barycenter. In both cases, the Dirichlet coefficient improves by the optimal factor $2^{-2/n}$, while the coefficient of the $L^2$ term remains one. Equality holds precisely for constant functions. The even case resolves a conjecture of Dolbeault (2021).

Scaling deep learning models efficiently requires predictable performance transfer across compute regimes. Establishing reliable hyperparameter transfer allows optimal training dynamics and structural choices to be discovered on low-cost proxy models, avoiding catastrophic failures during massive-scale training. Existing depth-transfer analyses are architecture-specific and heuristic: hyperparameter transfer is only justified through toy blocks, and both rely on infinite-depth dynamics, a specific initialization, and feature-learning criteria. Building on $L$-smoothness framework of Xu et al. (2026), we understand hyperparameter transfer as how do the Lipschitz and $L$-smoothness constants of the loss scale with the depth $K$? We show that inverse-depth residual branch scaling $\alpha=\Theta(1/K)$ is sufficient to make both constants depth-independent at fixed width, uniformly over the bounded parameter domain and for arbitrary $p\to q$ geometries. Because the bounds depend on each residual branch only through its Lipschitz and smoothness constants, the argument applies to general residual networks (including branches of block depth $\geq 2$ such as transformer and ResNet blocks) without assumptions on initialization or correlations between layer weights. Since the smoothness constant controls the curvature penalty in the descent inequality, our bounds motivate a learning-rate scale without an additional depth-dependent curvature correction for updates bounded in the prescribed norm. This provides a geometric explanation of inverse-depth residual scaling and its application to the operator-norm geometries associated with AdamW, Muon, and MOGA. Learning-rate sweeps on GPT-2 (depths 2–128) and CIFAR-100 ResNets (8–32 residual blocks) confirm that Muon and MOGA exhibit stable learning-rate transfer under these prescriptions, with a common optimal rate across a 64-fold increase in depth.

We prove that Choe's higher-dimensional Enneper hypersurfaces in $\mathbb R^{n+1}$, $3\le n\le6$, cannot be confined between two parallel hyperplanes, disproving his slab confinement conjecture. We further strengthen this conclusion by determining their precise height growth exponent. If $H(R)$ denotes the maximal absolute height above the asymptotic hyperplane within the horizontal ball of radius $R$, then $H(R)=R^{\alpha_1+o(1)}$ as $R\to\infty$, where $\alpha_1=\frac{\sqrt{(n-2)^2+4\lambda_1(\Omega)}-(n-2)}{2}$, $\Omega=S^{n-1}\setminus[0,\infty)^n$, and $\lambda_1(\Omega)$ is the first Dirichlet eigenvalue of the spherical Laplacian. In particular, $0<\alpha_1<1$, so the height is unbounded but grows sublinearly. The proof combines the blow-down behavior of a fundamental piece of Choe's hypersurface with the rigidity of positive harmonic functions on cones. In dimension two, the formula gives $2/3$, recovering the classical Enneper height-growth exponent.

We define a class of flows on compact metric spaces that we call \emph{$C^\alpha$ metric Anosov flows}, $0 < \alpha < 1$ or $\alpha = \mathrm{Lip}$. We give verifiable criteria for a metric Anosov flow to be $C^\alpha$. We show that $C^\alpha$ metric Anosov flows have Hölder continuous local product structure, and in particular Hölder continuous holonomies. We deduce that topological conjugacies between $C^\alpha$ metric Anosov flows are automatically Hölder continuous. We show that any $C^\alpha$ metric Anosov flow admits a strong (i.e. Hölder continuous) Markov coding. This yields strong ergodic properties for equilibrium states for Hölder potentials for $C^\alpha$ metric Anosov flows. The regularity of the local product structure is proved in a non-compact setting which applies for the geodesic flow on the universal cover of a locally CAT(-1) space. This allows us to obtain Hölder regularity results for the holonomy maps for pinched negative curvature manifolds with respect to the Sasaki metric. This contrasts with the result of Ballmann, Brin and Burns that there are examples in this class for which the dynamical distributions are not Hölder.

We propose an integrated market equilibrium model for determining the spot market prices and flow rates in a natural gas pipeline network. The traditional approach solves the market equilibrium model separately from the natural gas network flow allocation problem in a sequential manner. Our proposed framework synthesizes marketing and operations by using a bilevel optimization formulation where the market equilibrium model in the upper level is connected and simultaneously solved with the natural gas network flow model in the lower level. We introduce convex relaxations for the nonconvex Weymouth pipe pressure drop equation and a surrogate for the compressor operating cost. Furthermore, we compare multiple single level reformulations of the bilevel problem based on Karush-Kuhn-Tucker (KKT) optimality conditions, Wolfe duality, and Lagrange duality conditions. Numerical studies on a small 6-node network demonstrates the efficacy and accuracy of our model and the comparison between different duality and optimality based reformulations.

TREGO, a trust-region Bayesian optimization (BO) method for expensive blackbox problems, has convergence guarantees, but only for exact function values. In high dimension, its performance tends to deteriorate. This paper asks whether a trust-region BO method can be extended to handle noisy evaluations while being competitive in high dimension. We first generalize TREGO into a trust-region framework for noisy BO and extend its convergence analysis to noisy function estimates that are sufficiently accurate with sufficiently high probability. We then propose STREGO, a scalable implementation of this framework. Its global phase selects a batch of candidates by solving a bi-objective problem on the posterior mean of a Gaussian process and the integrated variance reduction. Unlike the predictive variance, this second objective does not favor boundary points merely because they are far from the data. Its local phase minimizes the posterior mean of a second Gaussian process, trained only on points close to the incumbent. STREGO is compared with TREGO, TURBO, BAXUS and NSMA-BO on synthetic and real-world problems of dimension $4$ to $124$, with and without noise. It gives the best average results in every synthetic setting tested and the best or tied-best solution on four of the six real-world problems. An implementation of STREGO is available at https://github.com/Mayousk/STREGO.

We establish variance upper bounds for the minimum perfect matching problem in general metric spaces under a geometric partition condition. As a principal application, let $H_n$ be the minimum perfect matching cost of $n$ independent uniform points in $[0,1]^d$, where $n$ is even and $d\ge2$. We prove $$\operatorname{Var}(H_n)\le C d n^{1-2/d},$$ where $C$ is independent of $n$ and $d$. This removes the logarithmic losses in earlier upper bounds in every dimension (Talagrand, 1995); in particular, the variance remains bounded in dimension two, answering an open question (Rhee, 1994). The proof relies on constructing a rapidly mixing Markov process with a multinomial stationary distribution.

We study decentralized bandit learning in discounted infinite-horizon, general-sum Markov games with continuous actions. Agents observe the public state, but only their own realized rewards, and use simultaneous perturbation stochastic approximation to update their actions. Under strong monotonicity of the negative running-reward gradients and sufficiently small time steps, we prove that the fully decentralized procedure converges almost surely to the unique stationary Markov perfect equilibrium. We obtain an $O(n^{-1/2})$ convergence rate and present a natural extension to episodic finite-horizon learning.

The cardinalities of Kiselman's semigroups $K_n$ are known to grow double exponentially in $n$: the sequence $2^{-n/2}\log_2|K_n|$ converges along the even and odd $n$ subsequences to positive limits $c_{\mathrm{even}}$ and $c_{\mathrm{odd}}$ that appear to coincide. In this paper we prove that they are indeed distinct. Since Kiselman's semigroups are $\mathcal{L}$-trivial, the suffix relation defines a partial order on $K_n$. We introduce the Kiselman transform $\mathsf{Kis}(P)$ of a poset $P$, a construction recovering the poset associated with $K_{n+1}$ from that associated with $K_n$. Counting strictly increasing chains in $P$ and $\mathsf{Kis}(P)$ yields a linear recurrence governed by a symmetric infinite matrix with explicit binomial entries. This can be used towards efficiently computing $|K_n|$, allowing the values listed in OEIS sequence A125625 to be extended beyond $n=14$. A generating functions analysis gives formulas for the above asymptotic limits, together with rigorous numerical bounds establishing that \[ c_{\mathrm{even}} - c_{\mathrm{odd}} = 1.9945066605\ldots\times10^{-6} \]

In this work, we show that if $K$ is a nonempty, closed, bounded, and convex subset of $X$ and $1\leq \gamma<\sqrt{N(X)},$ where $N(X)$ denotes the Bynum normal structure coefficient, then every uniformly asymptotically Hölder $\gamma$-Lipschitz mapping $T\colon K\to K$ has a fixed point. To achieve this, it was necessary to guarantee the existence of a subsequence of a bounded sequence whose asymptotic diameter is controlled by the quantity $D(\{x_n\}),$ introduced by Jiménez-Melado, while simultaneously preserving the asymptotic radii at every point of the closure of the linear span generated by the original sequence. This allowed us to remove the Hölder exponent from the calculations and obtain a Hölder-type extension of the Casini–Maluta, Lim–Xu, and, consequently, Kim–Xu theorems.

We study the inverse resonance problem for the one-dimensional Schrödinger operator on the half-line with a compactly supported complex-valued potential and a complex Robin boundary condition \[ u'(0)-a u(0)=0,\qquad a\in\mathbb C. \] The proof follows the transformation-operator, entire-function, and Fourier analytic strategy developed by Marletta, Shterenberg and Weikard for the Dirichlet problem \cite{MSW}. The Dirichlet Jost function $\psi(z,0)$ is replaced by the Robin characteristic function \[ F_a(z;q)=\psi_x(z,0;q)-a\psi(z,0;q). \] We establish the corresponding large-energy estimates, Hadamard factorization, finite-data stability, and uniqueness results. The principal new feature is that $F_a(z;q)=iz-a+O(1)$ rather than $1+O(z^{-1})$. In the transformation-operator argument the relevant boundary quantity is $B_x(0,t)-aB(0,t)$, together with the scalar term $B(0,0)$. For fixed $a\in\mathbb C$, and uniformly for $a$ in bounded subsets of $\mathbb C$, the resulting inverse resonance estimates have the same qualitative form as those proved in \cite{MSW} for the Dirichlet problem. In particular, for a fixed Robin parameter $a$, the complete set of Robin eigenvalues and resonances, counted with multiplicity, determines the potential uniquely. The text is produced with the help of AI ChatGPT for Academy.

We consider functions $u : \R^2 \rightarrow \R^N$ from the class $\Bloc$ which locally minimize the relaxed version of a variational integral with a strictly convex density being in addition of linear growth. It turns out that the boundedness of entire local minimizers $u$ implies their constancy.

We provide some extensions of the classical Calabi-Bernstein theorem to the case of entire solutions of certain nonlinear elliptic equations in two variables. Using an appropriate version of the Calabi correspondence, which formulates a duality between minimal graphs in $\mathbb{R}^3$ and maximal spacelike graphs in $\mathbb{L}^3$, our results are a consequence of recent Bernstein type results.

We develop a measure-theoretic framework for conditional multivariate total positivity of order two ($\mathrm{cmMTP}_2$), formulated through lattice inequalities without requiring the existence of probability densities. This formulation extends classical density-based notions of positive dependence to general probability measures, including singular distributions. We establish fundamental preservation properties under marginalization, monotone transformations, and weak convergence, thereby providing a unified treatment of dependence structures under distributional limits. We further investigate the behavior of conditional total positivity under Markov-kernel composition and derive characterizations for important copula families. In the Archimedean setting, the defining condition is expressed through log-convexity of generator derivatives, whereas for Gaussian distributions it corresponds to nonpositive off-diagonal entries of the precision matrix, or equivalently, nonnegative partial correlations. To connect these structural results with statistical inference, we introduce empirical lattice contrasts and establish their joint asymptotic normality. The resulting simultaneous testing procedures achieve asymptotic size control and admit a local power analysis. Our results provide a general foundation for density-free characterization, specification testing, and inference concerning positive dependence in multivariate probability models, particularly when conventional density-based methods are inapplicable or insufficient.

We study how the eigenspace associated with a fixed graph Laplacian eigenvalue changes under positive edge updates, allowing both new edges and increases in existing edge weights. We show that a preserved eigenvalue may have inherited eigenvectors from the original eigenspace and emergent eigenvectors outside it. We characterize the inherited eigenspace and show that it is independent of the update weights. We characterize its orthogonal complement within the preserved eigenspace through a symmetric matrix whose size is at most the number of updated edges, yielding a multiplicity formula and an explicit reconstruction of the updated eigenspace. For fixed updated edges, we characterize when emergence is possible and show that, whenever it is, equal update weights suffice. The exceptional weights form the zero set of a nonzero multi-affine polynomial in reciprocal variables and have Lebesgue measure zero. Finally, emergence cannot occur at either of the two smallest Laplacian eigenvalues, counting multiplicities.

We propose a coding scheme for the insertion, deletion and substitution (IDS) channel tailored to the short strands of DNA-based data storage. Instead of an inner synchronisation code, a spatially coupled LDPC (SC-LDPC) code is placed across the strands, with its coupling axis aligned to the position along the strands. Every decoded position thus becomes an anchor to synchronise the neighbouring strands. The decoding waves of the SC-LDPC code carry these anchors from both ends of the strands towards the middle. We bound the achievable rate from above by the information rate of a single strand and from below by that of a separated receiver. For strands of 100 nucleotides (the relevant regime for DNA-based data storage), our scheme outperforms a rate-matched concatenated construction.

We prove a central limit theorem for the quadratic matching cost between the uniform measure and its empirical counterpart on the flat torus in dimensions $d\ge5$. Let $\mu$ be Haar probability measure on $\mathbb{T}^d$ and let $\mu_n$ be the empirical measure of $n$ independent samples from $\mu$. Then $$ \begin{aligned} \frac{W_2^2(\mu_n,\mu)-\mathbb{E}W_2^2(\mu_n,\mu)} {\sqrt{\operatorname{Var}(W_2^2(\mu_n,\mu))}} &\Longrightarrow N(0,1),\\ c_dn^{-1-4/d} \le \operatorname{Var}(W_2^2(\mu_n,\mu)) &\le C_dn^{-1-4/d}, \end{aligned} $$ for positive constants $c_d,C_d$ depending only on $d$ and all sufficiently large $n$. The proof introduces a random-walk approach to matching fluctuations. We construct a random walk that jumps between neighboring cells of the optimal partition and use it to describe how the matching cost responds to changes in the sample. Estimates for this walk control the effect of replacing one sample point and the interaction between two replacements. These bounds yield the variance estimates and allow us to apply a martingale central limit theorem.

On a totally bounded metric space every non-contractive self-map is an isometry. For quasi-metric spaces, taken $T_1$ throughout ($d(x,y) = 0$ implies $x = y$), this fails: Zavarzina gave a hereditarily precompact counterexample and asked whether bijectivity restores rigidity; a recent example, the toll spiral, shows that it does not. We prove that compactness does: every compact quasi-metric space is expand-contract plastic, that is, each of its bijective non-contractive self-maps is an isometry. Countable compactness suffices, as does compactness of the conjugate topology. Bijectivity cannot be dropped: a compact, hereditarily precompact quasi-metric on the natural numbers makes the shift non-contractive and not an isometry. For arbitrary non-contractive self-maps we prove rigidity when the space is hereditarily precompact and its conjugate topology is sequentially compact, in particular when it is hereditarily precompact and Yoneda complete; neither hypothesis can be dropped. In both theorems the $T_1$ axiom can be weakened to $R_0$ ($d(x,y) = 0$ implies $d(y,x) = 0$), with hereditary precompactness read sequentially (every sequence has a left K-Cauchy subsequence), but not to $T_0$. We construct a $T_0$ space with all the remaining hypotheses of both theorems, Yoneda complete and compact both in its own topology and in the conjugate one, carrying a bijective non-contractive self-map that is not an isometry. Under $R_0$ the two-sided case reduces to the metric theorem, both topologies being sequentially compact exactly when the symmetrized distance is compact; the one-sided theorems do not reduce to it, and plasticity does not pass to the symmetrization even for compact spaces. The two theorems are machine-checked in Lean, and so are the counterexamples, apart from a few statements listed at the end.

This paper treats a system that performs back-to-back tasks. Each new task has a random matrix of parameters and can be processed in various processing modes. The processing mode determines the task duration and a vector of rewards (penalties are viewed as negative rewards). The reward vector can include quality, profit, or $-1$ times a penalty such as cost or energy. In wireless applications, tasks correspond to data transmissions and rewards/penalties correspond to throughput and distortion. Prior work treats the problem of maximizing the time average of a reward process subject to constraints. This paper seeks to maximize a concave function of the time average reward vector. This is difficult because it involves a multi-variable function of ratios of averages. We develop a single algorithm that does not know the probability distribution of the random task matrices. The algorithm is adaptive, meaning it responds efficiently (with optimal adaptation time) when probabilities change.

Optimization can be expensive when evaluating the objective and its gradient requires a large dataset or a costly simulation. A cheaper approximation (i.e., a surrogate) can provide a useful initial point, but the work spent on that surrogate must be justified by the saving on the original problem. We study how many iterations to perform on each surrogate before switching to a more accurate objective. For a given sequence of smooth, strongly convex objectives, we use convergence bounds and distances between minimizers to construct a model of the total iteration cost. We derive closed-form two-level budgets for Nesterov's accelerated gradient method and a convex reformulation for multiple levels. We also develop an online switching rule that updates the cost comparison using the gradient at the current point. We test the techniques on a logistic-regression problem using HIGGS data. The online rule reduces weighted iteration cost in all 27 tested configurations, with a median cost of 52.8% of direct optimization. The results illustrate why updating the switching decision can be more effective than fixing the budget from an initial convergence bound.

For a graph $G$, we investigate sufficient degree conditions under which either $G$ or its complement $\overline{G}$ is $k$-connected. Motivated by a theorem of Hellwig and Volkmann, we introduce the notion of complement connectivity admissible pairs and define the parameter $\mathcal{C}(k)$ as the minimum degree threshold guaranteeing that either $G$ or $\overline{G}$ is $k$-connected whenever $\delta(G)\ge\mathcal{C}(k)$ and $\Delta(G)\le |V(G)|-1-\mathcal{C}(k)$. We prove that $\mathcal{C}(k)=2k-2$ for every $k\ge2$, thereby determining the exact degree threshold. As an application, we derive a Nordhaus–Gaddum type product condition, showing that for $n\ge4k-5$, the condition $\delta(G)\delta(\overline{G}) \ge (2k-3)(n-2k+2)$ guarantees that either $G$ or $\overline{G}$ is $k$-connected. Finally, we show that no analogous product condition depending only on $k$ can exist.

We classify graphs of complex polynomials in one variable up to isometry, both for the inner (length) distance and for the outer (Euclidean) distance of $\mathbb{C}^2\cong\mathbb{R}^4$. For polynomials $p,q$ with $\deg p\ge 2$ we show that the graphs of $p$ and $q$ are inner isometric if and only if they are outer isometric, if and only if $p(z)=\alpha\,q(\beta z+h)+k$ or $p(z)=\alpha\,\bar q(\beta z+h)+k$ for some $\alpha,\beta,h,k\in\mathbb{C}$ with $|\alpha|=|\beta|=1$, where $\bar q$ denotes the polynomial with conjugate coefficients. Moreover, every inner isometry between such graphs is the restriction of an isometry of $\mathbb{C}^2$; in this sense graphs of complex polynomials are isometrically rigid. We contrast this with the real case, where the two distances behave very differently: the graphs of any two real polynomials are inner isometric, whereas, for degree at least $2$, outer isometries are generated by translations, reflections in horizontal and vertical lines and half-turns.

We study minimal positive cubature formulas on the two-dimensional sphere of degrees four and six, with ten and eighteen nodes, respectively. We prove the regularity of Popov's symmetric formulas and establish that their local families of deformations are two-dimensional, up to rotations. We obtain algebraic relations between the weights and pairwise inner products of the nodes. For degree four, we construct a one-parameter family with half-turn symmetry connecting the formulas of Popov and Heo–Xu. We also give a self-contained proof that eighteen nodes are minimal for degree six.

High-frequency switching and chattering are well-known problems in sliding-mode control. Although the super-twisting algorithm produces a continuous control input, the sliding variable may still cross zero repeatedly near the sliding manifold. This paper studies how fast these crossings can occur and whether they can accumulate in finite time for the scalar homogeneous super-twisting algorithm. Two lower bounds on the time required to return to zero are derived, together with a bound on the time needed to complete a full excursion. These results give minimum separation times and upper bounds on the number of crossings associated with excursions above a prescribed amplitude. Although zero crossings may accumulate in finite time, the amplitudes of the complete excursions considered here must vanish and satisfy a summability condition. Thus, crossings associated with excursions above any prescribed nonzero amplitude cannot accumulate in finite time. When the perturbation-rate bound is zero, the estimates recover the scaling imposed by homogeneity. For the classical super-twisting algorithm, the square-root scaling also holds for nonzero perturbation-rate bounds. Numerical simulations illustrate the results.

Let $ \operatorname{MaxCol}(n,d) $ denote the maximal number of nonsimultaneous elastic collisions among $n$ identical hard balls moving freely in $\mathbb{R}^d$. We give a planar construction with exponential lower bound with respect to $n$: $ \operatorname{MaxCol}(n,2)\geq 2^{\lfloor n/2\rfloor}, \quad n\geq3 $.