Papers

Fix positive integers $N,k,n$ with $n\ge k$. We seek the minimum number of members of size at least $n$ in a finite family of finite sets closed under union and containing exactly $N$ distinct sets of size $k$. This problem is a specialization of the Leck–Roberts–Simpson weighted conjecture: assign weight one to sets of size at least $n$ and zero to smaller sets. The predicted minimizer consists of the unions of nonempty subfamilies of the first $N$ $k$-subsets of the natural numbers, ordered by their largest elements and, when these agree, by their increasing lists lexicographically. For an integer $t\ge 1$, call the range \[ \binom{n+t-1}{k}<N\le\binom{n+t}{k} \] the $t$-th strip. We prove the layered conjecture throughout the first strip, and throughout the second strip for $k=3$. For arbitrary $k$, we prove the second strip for families of subsets of an $(n+2)$-element set. For $k,t\ge 3$, we prove the $t$-th strip for families of subsets of an $(n+t)$-element set whenever $n\ge(t+1)(k-1)$. With no restriction on the ground set, we prove it for $k\ge 3$ and $t\ge 2$ whenever $n>\frac{5}{2} k^2t$. For sufficiently large $k$, we obtain a sufficient bound of order $k^2t/\log k$, uniformly in $t\ge2$.

For a finite simple graph $G$ and an integer $k\ge0$, let $w_k(G)$ denote the number of walks of length $k$. We prove the conjecture of Täubig, Weihmann, Kosub, Hemmecke, and Mayr for every finite tree and determine all equality cases. If $T$ has $n\ge1$ vertices, then $n w_{k+1}(T)-2(n-1)w_k(T)\ge0$ for every $k\ge1$; for $n\ge3$, equality holds if and only if $T$ is a star and $k$ is even, whereas for $n=1$ or $n=2$, equality holds for every $k\ge1$. For non-Dynkin trees and even indices, the proof is based on a polynomial positivity cone associated with the adjacency operator of a finite graph and a positive real root of its simply-laced Coxeter system. For finite connected bipartite non-Dynkin graphs, we establish sufficient positivity conditions in terms of Coxeter orbits and inversion sets, and verify these conditions for indicator roots supported on connected induced subtrees. For non-Dynkin trees, this yields the rooted even-index inequality and, after summation, the corresponding global inequality. We also prove that if $G$ is a finite connected bipartite non-Dynkin simple graph, $\varnothing\ne U\subseteq V(G)$, and the subgraph of $G$ induced by $U$ is a tree, then $|U|w_{k+1}(G,U)-2(|U|-1)w_k(G,U)\ge0$ for every $k\ge0$, where $w_k(G,U)$ counts the length-$k$ walks in $G$ whose initial and terminal vertices lie in $U$; the intermediate vertices are unrestricted. The remaining even-index cases for finite Dynkin trees are handled by generating-function recurrences, while the odd-index cases follow from a spectral covariance identity.

We show that there is a fixed planar graph $H$, namely the $5 \times 5$ grid, such that Max Independent Set remains NP-hard in $H$-induced-minor-free graphs. This refutes the Dallard–Milanič–Štorgel conjecture and a weakening of it by Gartland and Lokshtanov, and by Korhonen.

A proper conflict-free coloring of a graph is a proper vertex coloring in which every non-isolated vertex has a color appearing exactly once in its neighborhood. A graph $G$ is proper conflict-free $(\mathrm{degree}+2)$-choosable if every list assignment $L$ with $|L(v)|\ge d_G(v)+2$ for each $v\in V(G)$ admits such a coloring from the lists. We prove that every graph with girth at least $7$ and maximum average degree less than $8/3$ is proper conflict-free $(\mathrm{degree}+2)$-choosable. Consequently, every planar graph of girth at least $8$ has this property, improving the previously established sufficient girth bound of $9$.

We prove, in $\mathsf{ZFC}$, that the $\lambda$-terraced cube relation fails whenever $\lambda$ is an uncountable cardinal. The corresponding terraced relation for quadruples fails for every $\lambda$. If $\lambda$ is $\aleph_0$ then the pretinent terraced relation has consistency strength of at least one Woodin cardinal. We prove positive polarized relations at a successor and a double successor from wondrous ideals. We show, however, that there are no such ideals over two consecutive cardinals simultaneously.

We prove commutation relations between the ordinary type A crystal operators and a sign-reversing involution on semistandard set-valued tableaux of skew shape. We describe the involution by Boolean fibers with fixed maximum entries. It commutes with every raising operator except the one indexed by the entry changed by the involution. We characterize commutation at this exceptional raising operator and for lowering operators away from the two colors involving that entry using the box where the involution acts and reduced signatures. We construct a bijection from these tableaux to decorated five-vertex states that preserves weight and excess, subject to a restriction on nontrivial bumps determined by the inner partition. Rotation with alphabet reversal yields the dual statements.

We study the expressivity of spiking neural networks, which provide a natural framework for asynchronous, event-driven computation complementary to conventional feedforward neural networks. We consider the time-to-first-spike model in a setting for which the input-output map is continuous and piecewise linear, with affine pieces governed by causal feasibility constraints that determine which presynaptic spikes occur before a neuron fires. We first show that each neuron's firing time admits a maxout-like representation with exponentially many, highly constrained affine pieces. We then formalize causal regions as polyhedral regions with fixed causal sets and derive upper and lower bounds on the maximal number of causal regions in both shallow and multilayer feedforward spiking networks. Our theoretical and experimental results show that spiking networks can generate richer partitions of the input space than conventional feedforward ReLU networks.

Our main result is a $3\sqrt{2\pi}$ bound for the Komlós signing problem: every finite family of real vectors of Euclidean norm at most one admits a signed sum of $\ell_\infty$-norm less than this constant, independently of the dimension and the family size. For any $\kappa\ge0$, if a bounded open convex set supports a probability density with directional total variation at most $\kappa$ in every unit direction, then its open-set Banaszczyk transform supports another such density with the same $\kappa$, provided the translation vector $v$ satisfies $\kappa\|v\|_2\le1/3$. As a consequence, every finite set system in which each element belongs to at most $t$ sets, where $t\ge1$ is an integer, admits a two-coloring whose imbalance in each set is less than $3\sqrt{2\pi t}$. This gives the square-root dependence predicted by the Beck-Fiala conjecture. The proof was discovered by the Odin Automatic AI Research Agent.

The recursive-line Zarankiewicz number maximizes the number of squares in a structured irreducible sum-of-squares representation encoded by an augmentation of an extremal $C_4$-free bipartite graph. We determine its four-column behavior under the strengthened recursive definition in the manuscript of Löfberg and Qi dated 9 September 2026. Combining AI-assisted discovery with exact certificate verification and finite exclusion computations, we determine eighteen of the nineteen values for $2\le m\le20$ and isolate the only unresolved case to $37\le\zr(14,4)\le38$. More significantly, we prove the first eventual exact formula in the four-column setting: \[ \zr(m,4)=\floor{\frac{5m+6}{2}}\qquad(m\ge15). \] The upper bound follows from the classical identity $z(m,4)=m+6$ and a sharp cell count. For the matching lower bound, we construct a two-row extension chain from an explicit $20\times4$ seed and derive the odd orders by a fixed deletion. Analytic propagation, together with two independently audited symbolic certificate tables, proves the construction for arbitrary chain length rather than merely for a finite computational range. Thus every extremal configuration has no holes when $m$ is even and exactly one hole when $m$ is odd, and the same exact formula holds for the second-order number $z_2(m,4)$.

For every fixed $0<\varepsilon\le1$, we give a deterministic strongly polynomial algorithm that, given a nonnegative matrix $A\in\mathbb{R}_{\ge0}^{n\times n}$, returns $Q$ satisfying $\operatorname{per} A\le Q\le(1+\varepsilon)^n\operatorname{per} A$.

Montgomery recently proved that for sufficiently large $n$, every Latin square of order $n$ has a partial transversal with $n-1$ cells, and every Steiner triple system of order $n$ has a matching with $\lfloor n/3\rfloor-1$ edges, thus confirming the Ryser–Brualdi–Stein conjecture for even $n$ and the conjecture of Brouwer. We prove sharp enumerative refinements of these results: there is an absolute constant $c>0$ such that, for sufficiently large $n$, 1) every Latin square of order $n$ has $ \left((1\pm n^{-c})\frac{n}{\mathrm {e}^2}\right)^n$ partial transversals with $n-1$ cells; 2) every Steiner triple system of order $n$ has $ \left((1\pm n^{-c})\frac{n}{2\mathrm {e}^2}\right)^{\lfloor n/3\rfloor}$ matchings with $\lfloor n/3\rfloor-1$ edges. The first estimate confirms predictions of Montgomery and Kelly.

We introduce and study a scalar $q$-deformation of the cross-ratio on $\mathbb P^1(\mathbb Q)$. Our construction is based on the notion of $q$-deformed rational numbers due to Morier-Genoud and the author. The $q$-cross-ratio is invariant under $\mathrm{PSL}(2,\mathbb{Z})$, while elements of determinant $-1$ of $\mathrm{PGL}(2,\mathbb{Z})$ act by $q\mapsto q^{-1}$. A principal result is its relation to $q$-deformed Coxeter friezes associated with rational polygons. The expansion at $q=e^h$ yields an algebraically independent sequence of modular invariants and relative invariants, although this sequence does not separate modular orbits. We compute the first two nonconstant coefficients of this expansion explicitly.

It is shown that every Eulerian digraph on $n$ vertices with more than $(t-1)n$ arcs contains every oriented tree with $t$ edges. The digraphs have no loops or repeated arcs, but opposite arcs are permitted. The bound is sharp for each fixed oriented tree, as witnessed by disjoint unions of complete bidirected graphs. Previously, such tight bounds were not known, even just for directed paths. This can be considered as a directed analog of the recently proved Erdős-Sós conjecture. The result was proved by GPT-6 Astra.

Bernshteyn, Kostochka, and Zhu (2020) introduced the notion of fractional DP-coloring, which generalizes both fractional coloring and fractional list coloring. Among several foundational results, they proved that every $d$-degenerate bipartite graph $G$ satisfies $\chi_f^{\mathrm{DP}} \le (1 + o(1))\frac{d}{\log d}$, and that this bound is optimal—a stark contrast to ordinary fractional coloring. In this paper, we extend this upper bound to all $d$-degenerate triangle-free graphs, proving that $\chi_f^{\mathrm{DP}} \le (4 + o(1))\frac{d}{\log d}$. This generalizes a recent result of Martinsson and Steiner (2025) for ordinary fractional coloring. We derive this result as a corollary of a more general upper bound concerning locally sparse graph orderings. Specifically, a $d$-degenerate graph $G$ is left $k$-locally-sparse if it admits a degeneracy ordering in which, for every vertex $v$, the subgraph induced by its back-neighbors contains at most $k$ edges. We show that if a $d$-degenerate graph $G$ is left $\frac{d^2}{f}$-locally-sparse, then \[ \chi_f^{\mathrm{DP}}(G) \le (8 + o(1))\frac{d}{\log f}. \] This immediately yields an identical upper bound on the ordinary fractional chromatic number $\chi_f(G)$, improving upon the leading constants of previously known bounds. Additionally, we establish the asymptotic sharpness of this result up to the leading constant. For any $1 \ll f \le d^2$, we construct $d$-degenerate graphs that are left $\frac{d^2}{f}$-locally-sparse and satisfy $\chi_f(G) \ge (1 - o(1))\frac{d}{\log f}$. Finally, as applications of our main theorem, we obtain improved upper bounds on the fractional DP-chromatic number of $d$-degenerate $K_{1,t,t}$-free graphs, as well as $K_{t,t,t}$-free graphs with maximum degree $\Delta$. Notably, these bounds improve upon existing results even in the setting of ordinary fractional coloring.

We study Turán problems for balanced even cycles in simple signed graphs, where signed subgraphs are considered up to switching. For every balanced bipartite signed graph, the signed and ordinary Turán numbers differ by at most a factor of two. Our main structural results concern the underlying graphs that admit a signing in which every $2k$-cycle is unbalanced. We characterize these graphs by the absence of an odd dependence among their $2k$-cycle incidence vectors, give a cohomological formulation, and construct subgraph-minimal obstructions of arbitrarily large order. In particular, there is no finite forbidden-subgraph characterization. We also give an exact closed-walk criterion for cycles in double covers and derive a direct signed breadth-first-search upper bound. As applications, we prove \[ \hex(n,C_{+4})=\left(\frac{\sqrt2}{2}+o(1)\right)n^{3/2} \] and study the signed hexagon number $R_6(n)=\hex(n,\{C_{-3},C_{+6}\})$. We characterize the underlying graphs counted by $R_6$ and express it as an extremal problem for ordinary $C_6$-free graphs with a prescribed involution. For every sufficiently large $n$, we construct examples with $\Omega(n^{4/3})$ edges, and we give an equivariant construction attaining the coefficient obtained from the Füredi–Naor–Verstraëte lower bound by double-cover transfer. Finally, we give $n$-vertex $C_{+10}$-free signed graphs with $\Omega(n^{6/5})$ edges and use octagon examples to illustrate the limitations of theta-freeness as a signing criterion.

A point set is universal for planar graphs on $n$ vertices if every such graph has a straight-line drawing without crossings whose vertices belong to the set. We construct universal point sets of size $n^{1+o(1)}$, improving the previous quadratic upper bound. Our construction uses the reduction of Bannister, Cheng, Devanny, and Eppstein from universal point sets to superpatterns for $213$-avoiding permutations. We represent these permutations by ordered rooted forests and construct a small family of intervals containing every such forest. The result follows from a straightforward bound on the size of the family of intervals. GPT-6 Astra assisted in developing the construction and proof.

We perform a numerical study of uniform meandric systems via their encoding by pairs of simple random walks and their interpretation as a model of critical percolation on random planar maps. We investigate certain natural box-crossing events and provide numerical evidence for a strong negative association between opposite open crossings and formulate conjectures on their asymptotic behavior. Our second contribution is a simple law-preserving dynamics on meandric systems, by local peak/valley flips in the walk encoding. Our simulations suggest that the percolation structure decorrelates much faster than the underlying random planar map.

We prove Fuglede's conjecture for finite cyclic groups of square-free order. Specifically, if \(N\) is square-free and \(A\subseteq \mathbb Z_N\) is nonempty with \(|A|=m\), then \(A\) is spectral if and only if it tiles \(\mathbb Z_N\); moreover, these conditions hold precisely when \(m\mid N\) and \(A\) is a complete set of representatives modulo \(m\). This gives a complete structural description of spectral and tiling sets in \(\mathbb Z_N\). The key new ingredient is a prime-coordinate elimination theorem: if \(P\nmid nm\) is an odd prime, then every \(m\)-point spectral pair in \(\mathbb Z_n\times\mathbb Z_P\) projects injectively to a spectral pair in \(\mathbb Z_n\). Its proof combines character-matrix orthogonality, cyclotomic coefficient comparison, and a \(P\)-adic divisibility argument for associated Gram matrices. Iterating this reduction yields the result for arbitrary square-free \(N\), with no restriction on the number or relative sizes of its prime factors.

The least interval diameter needed to realize every attainable cardinality of an $h$-fold sumset of a four-element integer set is $\binom{h+2}{2}+(h\bmod2)$ for $2\le h\le10$ and $d_h=(h-3)(h-1)$ for $h\ge11$. We prove the formula uniformly for $h\ge17$ and use complete finite searches, with a relation-rank coverage argument, for the remaining orders. For the lower bound, we show that every integer four-set with $\binom{h+3}{3}-17$ distinct $h$-fold sums has normalized diameter in $\{d_h,d_h+1,d_h+2\}$ when $h\ge9$, and we construct sets attaining $d_h$. For the upper bound, a relation-lattice index argument restricts larger minimum-diameter representatives to two or three active directions. Two general constructions and four special defects then provide short sets realizing every remaining cardinality.

We compare return probabilities for random walks stopped at an independent geometric time on Lubotzky–Phillips–Sarnak graphs and on the infinite regular tree, with the McKay measure giving the tree value and the Ihara zeta function describing the additional returns caused by cycles. We estimate this correction when the mean walk length is comparable to the length of the shortest cycle, a regime in which walks long enough to traverse a cycle receive non-negligible weight. Unconditionally, we prove an upper bound with a double logarithmic factor and bounded fixed moments over prime levels after multiplication by the number of vertices. Under the Generalized Riemann Hypothesis for quadratic Dirichlet $L$-functions, the correction is of the same order as the reciprocal of the number of vertices.

We study the problem of counting Italian dominating functions (IDFs) of each possible weight on paths, trees, and cycles. An Italian dominating function on a graph $G=(V,E)$ is a function $f\colon V\to\{0,1,2\}$ such that every vertex $v$ with $f(v)=0$ satisfies $\sum_{u\in N(v)}f(u)\ge 2$; the Italian domination polynomial $D_I(G,x)=\sum_k d_I(G,k)\,x^k$ records the number $d_I(G,k)$ of such functions of weight~$k$. This polynomial is the Italian analogue of the well-studied domination and Roman domination polynomials, and computing its coefficients on a fixed graph class is, in essence, a constrained integer composition problem: passing to the deficit variables $y(v)=2-f(v)$, each coefficient $d_I(G,2n-j)$ counts the number of compositions of $j$ into $n$ parts, each at most~$2$, that additionally satisfy a local adjacency capacity constraint. We make this connection explicit and use it to derive closed-form expressions for $d_I(C_n,2n-j)$, $j=0,\ldots,5$, as trinomial coefficients minus explicitly enumerated forbidden configurations. On the algorithmic side, we give dynamic programming algorithms that compute all coefficients of $D_I$ on path graphs ($O(n^2)$ time, $O(n)$ space), on general trees ($O(n^2)$ time, $O(n)$ space, via a post-order merge with a deficit parameter), and on cycle graphs ($O(n^2)$ time, $O(n)$ space, via boundary conditioning), together with formal correctness proofs and complexity analyses. The known values $\gamma_I(P_n)=\lfloor n/2\rfloor+1$ and $\gamma_I(C_n)=\lceil n/2\rceil$ are recalled with references rather than reproved. All numerical results are verified against brute-force enumeration, and complete tables are provided.

DomiRank is a node-importance algorithm for unweighted networks, defined by a dynamical model governed by a competition-strength parameter, a dominance threshold, and a decay rate. We establish three structural results. First, on symmetry. Automorphism-related vertices share the same DomiRank value, and a graph whose values are pairwise distinct must be asymmetric. The orbit count bounds the number of distinct values, and regular and vertex-transitive graphs admit closed forms. Second, on entropy. The maximum of the DomiRank entropy over connected graphs, log_2 N, is attained if and only if the graph is regular. The initial entropy derivative is the degree-log-degree edge covariance, making the decrease rigorous near vanishing competition for structurally disassortative graphs, and an assortative counterexample shows it does not extend to all graphs; a sufficient-condition theorem and a refined conjecture cover the rest. Third, on spectrum. The normalized distribution is sigma-invariant if and only if the degree vector is an adjacency-matrix eigenvector. The parameter sigma interpolates continuously between degree and smallest-eigenvector centrality within the resolvent (Bonacich-type) family, its sensitivity being a second-order suppression operator on the degree vector. Graph transformations are also characterized, including the m-product. Experiments on four real networks and synthetic families up to 10^4 vertices confirm the interpolation and exhibit monotone entropy decrease, continuous ranking interpolation, decaying positive fraction and ranking reversals; where the positive fraction has decayed far from one, the limit describes the solution vector rather than the induced ranking. DomiRank is thus a tunable complement to principal-eigenvector centrality. A companion study quantifies how much of its task-level edge over a degree baseline survives degree correction.

For a partition $\lambda$, let $G_\lambda^{(\beta)}$ be the stable $\beta$-Grothendieck polynomial attached to $\lambda$. Each homogeneous component of the $\beta = 1$ specialization $G_\lambda^{(1)}$ is Schur-positive and hence positive in the fundamental basis of quasisymmetric functions. For $m\ge|\lambda|$, let $G_{\lambda,m}^{(1)}$ be the homogeneous degree $m$ component of $G_\lambda^{(1)}$. In this paper, we first give a direct proof of an expansion of $G_{\lambda,m}^{(1)}$ in the fundamental basis in terms of standard set-valued tableaux. We then use these tableaux as a basis to define a module of the $0$-Hecke algebra and show that the quasisymmetric characteristic of the resulting module is $G_{\lambda,m}^{(1)}$. We further show that this module decomposes as a direct sum of weak Bruhat interval modules.

Using estimates established in a previous paper, we prove quantitative universality results for cokernels of products of i.i.d. random matrices and for flags associated to k-tuples of random i.i.d. matrices, over finite local rings. In the case when the ring is a quotient of $\mathbb{Z}_p$, this gives a quantitative analogue of some previous results of Huang, Nguyen and Van Peski.

We consider the cokernel corners process for an i.i.d. matrix with entries in a finite local ring. When the distribution of the entries is uniform, this process is a Markov chain, and hence the ergodic theorem for Markov chains can be applied. This implies, in particular, that for uniformly distributed p-adic random matrices, the cokernels of the corners are distributed according to the Cohen-Lenstra measure, almost surely. The purpose of this note is to show that the conclusion of the ergodic theorem also holds for i.i.d matrices, provided that the distribution of the entries is not concentrated on the translate of a subring, or the translate of an ideal. This will follow from the bounds proved in a previous paper of the author.

For every integer $n\geq 11$, we construct pairs of connected, irregular, nonisomorphic graphs on $n$ vertices that are cospectral for the adjacency, Laplacian, signless Laplacian, normalized Laplacian, and Seidel matrices, have equal independence, clique, chromatic, complement chromatic, and maximum-cut numbers, and have distinct Lovász $\vartheta$-numbers. Each pair is formed by joining $K_{n-10}$ to fixed cospectral, nonisomorphic, regular graphs on ten vertices due to van Dam and Haemers. We prove that the joins retain equality of the five spectra and listed integer-valued invariants, while preserving the respective Lovász numbers. We derive exact formulas for these numbers and prove them distinct. We also determine the cardinality-constrained maximum-cut profiles of the base graphs and their complements. They give exact formulas and prove equality of the maximum-cut numbers within each pair, both for the joins of the base graphs with $K_{n-10}$ and for those of their complements with $K_{n-10}$. For $n=10$, we first give a regular pair with all the stated properties except irregularity, then a connected, irregular, nonisomorphic pair sharing all five spectra and listed integer-valued invariants but having distinct Lovász numbers. An exhaustive SageMath computation shows that no connected, irregular, nonisomorphic pair on at most nine vertices shares all five spectra and listed integer-valued invariants. Thus, ten is the smallest possible order, and such pairs exist for every $n\geq 10$. It extends and strengthens a result for even $n\geq 14$ (Sason, '24), which did not address Seidel matrices, complement chromatic numbers, maximum-cut numbers of the graphs, or those of the corresponding joins formed from their complements. Thus, the Lovász number is a computable certificate of nonisomorphism even when all five spectra and listed integer-valued invariants coincide.

Let $\mathfrak L$ be a Frobenius maximal parabolic subalgebra of $\mathfrak{sl}_n$. For any $F\in\mathfrak L^*$ for which the Kirillov form $B_F(x,y)=F([x,y])$ is non-degenerate, let $\widehat F$ denote the associated principal element. We prove that the multiplicities of the eigenvalues of $\operatorname{ad}_{\widehat F}$ on $\mathfrak L$ form a unimodal sequence symmetric about $\frac12$. We also prove that the multiplicities of the eigenvalues of $\operatorname{ad}_{\widehat F}$ on $\mathfrak{gl}_n$ form a unimodal sequence symmetric about $0$. The proof relates the ranked meander associated to $\mathfrak L$ to the order ideals of a related fence poset through Panyushev reduction. The known unimodality of the rank polynomial of the fence poset implies that of the meander, which in turn determines a good grading of $\mathfrak{gl}_n$ in the sense of Elashvili and Kac. We prove that this grading coincides with that induced by the principal element and that the pyramid associated to this grading may be filled in such a way that its good element $e$ lies in $\mathfrak L$. The two unimodality results then follow from the injectivity properties of $\operatorname{ad}_e$ coming from the good grading and the duality induced by the bilinear form $B_F$.

The total domination number $\gamma_t(G)$ of a graph $G$ is the minimum cardinality of a set $D\subseteq V(G)$ such that every vertex of $G$ has a neighbor in $D$. The annihilation number $a(G)$ is the largest integer $k$ for which the sum of the $k$ smallest degrees of $G$ is at most $|E(G)|$. A well-known conjecture, originating from Graffiti.pc and later formulated explicitly by Desormeaux, Haynes, and Henning, asserts that $\gamma_t(G)\le a(G)+1$ for every connected nontrivial graph $G$. The conjecture is known for graphs of minimum degree at least three and for several classes of graphs having vertices of degree one or two. In this paper we settle the minimum-degree-two case. More precisely, we prove $\gamma_t(G)\le a(G)+1$ for every connected graph $G$ with $\delta(G)=2$. The proof combines two sharp bounds on the total domination number with an estimate for the annihilation number. Moreover, in some specific cases, the stronger inequality $\gamma_t(G)\le a(G)$ holds.

This is a survey on an old open problem in combinatorics called the unit distance problem, and the field of mathematics around it, called incidence geometry. What do we know about the problem? Why is it difficult? How does it connect with other parts of math?

Baste, Furst, Henning, Mohr, and Rautenbach conjectured that every finite regular graph of positive degree satisfies \(\gamma(G) \leq \gamma_e(G)\), where \(\gamma\) is the domination number and \(\gamma_e\) is the edge domination number, equivalently the minimum cardinality of a maximal matching. We show that the conjecture is false already for cubic graphs. The counterexample is a previously public 50-vertex cubic graph that had been used to refute the stronger independent-domination inequality \(i(G) \leq \gamma_e(G)\). For this graph we prove \(\gamma(G) = 16 > 15 = \gamma_e(G)\). The equality \(\gamma_e(G) = 15\) has a short counting proof, and a dominating set of order 16 is displayed explicitly. For the lower bound \(\gamma(G) \geq 16\), we give a self-contained exact reduction: after fixing which of the 20 clause vertices lie in a putative dominating set, the remaining problem is a finite set-cover problem on the 30 literal vertices. We enumerate all \(2^{20} = 1,048,576\) clause subsets, derive two explicit lower bounds, and solve exactly the 5,931 residual cases by a recurrence stated in the paper. The complete case counts and minima are displayed, and a short standard-library Python implementation is included in an appendix. A separate 893,049-node proof-tree certificate and a direct graph search provide independent verification. Thus the regular-graph conjecture is disproved. Combined with Gupta's recent theorem that every cubic graph on at most 48 vertices satisfies the conjectured inequality, the example is order-minimal among cubic counterexamples.