Peer Revenue Past citations are no guarantee of future returns

Papers

Fresh from arXiv, typeset properly. Highlighted words trade on the market.

Mathematics

math Watch Mathematics (sign in to use)

Thursday 24 September

Rings and Algebras

The $m$-Invariant of Fields of Characteristic 2

We study the minimal dimension of a nonsingular anisotropic universal quadratic form over a field $F$ of $\operatorname{char}(F)=2$, which we call the “$m$-invariant" of $F$. We show that every even number is the $m$-invariant of some field of characteristic 2, and consider cases when $u(F)$ and $m(F)$ are equal and when they are not.
Read the full abstract

Combinatorics · Cross-listed from quant-ph

Construction of Partial Join Graphs with Perfect State Transfer in Shunt Decomposition-Based Quantum Walks

In this paper, we define directed partial join graphs with signed couplings and construct discrete-time quantum-walk transition operators for these graphs using the shunt-decomposition framework. The resulting transition operators apply to several important graph families, including complete graphs with loops, circulant partial joins, complete bipartite graphs, tensor powers of complete bipartite graphs, all with signed couplings. For each family, we identify the corresponding structure of the transition operator and derive necessary and sufficient conditions for periodicity and perfect state transfer (PST), when one of the two directed regular graphs admits PST. Based on these results, we identify two types of state transfer; internal PST, which occurs between vertices within the same graph, and coupling PST, which occurs between two components of join graphs. We further develop a double-cover construction for directed partial join graphs and derive conditions for periodicity and PST when the associated transition operators do not necessarily commute. Using this construction, we establish PST results for double covers of complete graphs with loops. In particular, we provide an example in which the complete graph \(K_n\) does not exhibit PST for \(n\geq4\), whereas a suitable partial join of \(K_n\) exhibits PST when \(n=2^m\), \(m\geq2\). Hence, these results extend the class of graph families admitting PST in shunt-decomposition-based quantum walks and provide a unified framework for studying quantum state transfer in graph joins, products, and covers.
Read the full abstract

All authors Banita Katuwal, Y Lakshmi Naidu, Srinath M S, Supriyo Dutta

Algebraic Geometry

Demazure Models of Algebraic Tori in Dimension 4

A Demazure model of an algebraic $k$-torus $T$ split by a finite Galois extension of fields $L/k$ and splitting group $G=\text{Gal}(L/k)$ is a smooth projective $T_L$-toric variety $X_{\Sigma}$ such that the natural action of $G$ on $T_L$ extends to $X_{\Sigma}$. A smooth projective model of the algebraic $k$-torus $T$ can then be taken to be the quotient of a Demazure model by its splitting group. The existence of Demazure models of algebraic $k$-tori was determined by Brylinski and further refined by Colliot-Thélène, Harari and Skorobogatov. Voskresenskii and Kunyavskii's birational classifications of algebraic $k$-tori in dimensions 2 and 3 involved constructions of Demazure models of the algebraic $k$-tori corresponding to maximal finite subgroups of $\text{GL}(r,\mathbb{Z})$ for $r=2,3$. We discuss some explicit constructions of Demazure models of algebraic $k$-tori, making connections with the defining integral representations of their splitting groups. The constructions determine smooth projective Demazure models of the algebraic tori corresponding to maximal finite subgroups of $\text{GL}(4,\mathbb{Z})$. Since projective toric varieties are determined by lattice polytopes, our constructions focus on some highly symmetric families of polytopes, such as root polytopes and central transportation polytopes.
Read the full abstract

Analysis of PDEs

Continuous Data Assimilation for Memristive FitzHugh–Nagumo Neural Networks

In this study, we investigate continuous data assimilation for a class of partly diffusive FitzHugh–Nagumo neural networks with memristive feedback and linear synaptic coupling. The nudging algorithm implemented here only adds a feedback term to the membrane-potential equations, while the recovery and memductance variables remain unobserved. We obtain weighted energy estimates that give sufficient conditions for exponential convergence of the data-assimilated solution to the reference solution under full or coarse membrane potential observations. Moreover, we prove energy-class uniqueness in dimensions one and two. In dimension three, the uniqueness criterion is an \(L^4\) membrane-potential initial data. We also establish an observational-noise estimate for locally square-integrable forcing, yielding an asymptotic error bound when the noise energy is eventually bounded.
Read the full abstract

Statistics Theory

Scaffold-Constrained Subset Dynamic Programming for Exact SSE Clustering

Exact Euclidean \(K\)-means partitions \(n\) observations into \(K\) unlabelled clusters, but the unrestricted search is generally exponential. We use data-derived geometric graphs to precondition an exact subset dynamic program: as a result only connected vertex subsets are admitted as clusters, while sum-of-squared-errors (SSE) loss is unchanged. A remaining-set recurrence minimises fixed-\(K\) or penalised SSE, with exact factorisation over the connected components of each remaining set. The central question we study is how much computational support can be removed while preserving an unrestricted optimum. Graph inclusion gives monotone coverage and support relations, and a bottleneck threshold identifies the first covering graph in a nested hierarchy. For fixed \(K\) and dimension, under compact ball support and density bounds, retaining \(q=O(\log n)\) nearest neighbours per observation preserves an empirical SSE optimum with probability tending to one, using an \(O(\log n/n)\) fraction of complete-graph edges. Truncated Gaussian mixtures with unequal weights and covariances satisfy these conditions. The rate we provide is a sufficient upper bound rather than a result implying polynomial optimisation complexity. Objective-matched synthetic and full-data comparisons assess coverage, compression, and reference-label agreement. As a secondary application, we illustrate how the proposed scaffold preconditioning can be utilized to improve the efficiency of split-merge proposals that preserve unrestricted mixture posteriors.
Read the full abstract

Mathematical Physics · Cross-listed from hep-th

Divergences in Nonpolynomial Quantum Field Theories

The structure of divergences in several nonpolynomial scalar quantum field theories are investigated. Various $n$-point Green functions for nonpolynomial theories are calculated and their renormalization is analyzed, with special regard for the nonpolynomial $\left|\phi\right|^{3}$ theory in $4$ spacetime dimensions.
Read the full abstract

Analysis of PDEs

Isothermal hydrodynamic limit for kinetic flocking models with nonlinear velocity alignment

We study the hydrodynamic limit of kinetic flocking models with nonlinear velocity alignment and strong local Fokker–Planck forcing. In the limit of small Knudsen number the kinetic densities converge to a local Maxwellian centered around macroscopic quantities satisfying the compressible Euler system with isothermal pressure $p = \s \rho$, while macroscopic alignment is obtained by convolution of the microscopic velocity law with the standard Gaussian, resulting in a different nonlinearity. Such discrepancy has been observed already in \cite{black2025hydrodynamic}. In this note we rigorously justify the limit for admissible weak kinetic solutions and non-vacuous limiting macroscopic solution. Our analysis provides a quantitative rate of convergence in terms of relative entropy: $\cH(f_\e | \mu) \lesssim \e$ provided initially $\cH(f_\e(0) | \mu(0)) \leq \e$. In the linear case we recover the known result \cite{karper2015hydrodynamic}.
Read the full abstract

Optimization and Control · Cross-listed from eess.SY

Practical Algebraic Parameter Estimation for Noisy Data via Gaussian Process Regression

Parameter estimation for ordinary differential equation (ODE) models is a fundamental task that is often complicated by the limitations of conventional optimization-based methods. In theory, differential-algebraic approaches offer an appealing alternative: they reduce the problem to polynomial system solving and do not require user-supplied initial guesses for parameter values. In practice, however, algebraic methods have been limited by their sensitivity to measurement noise, because they require accurate derivatives of observed outputs. In this work, we integrate Gaussian Process Regression (GPR) into the differential-algebraic method and derive a first-order error analysis in terms of noise level and algebraic sensitivity. We evaluate the method across several noise levels on a benchmark of 25 dynamical systems arising in applications including mechanical engineering and systems biology. The proposed method achieves the highest aggregate performance among the methods considered, recovering all sought parameter values and initial conditions to within 10% relative error in 88.5% of runs. These results demonstrate that robust derivative estimation can make differential-algebraic parameter estimation practical for dense, noisy synthetic data while retaining key advantages of the algebraic formulation.
Read the full abstract

Rings and Algebras

The Hua identity implies alternativity

The well-known Hua identity $a - (a^{-1} + (b^{-1} - a)^{-1})^{-1} = aba$ holds in any associative division ring. We prove, in a sense, a converse: if a (nonassociative) ring with unit and multiplicative inverses satisfies the Hua identity, then it is alternative.

Category Theory

Graduated categories of presheaves

We study conditions on a small category $\mathcal{A}$ under which every finitely generated object of its presheaf category is finitely presentable. Example: this holds for a group $\mathcal{A}$ iff $\mathcal{A}$ is Noetherian. For ordinals $\mathcal{A}=\alpha$ this holds iff $\alpha\leq \omega$, whereas this always holds for $\mathcal{A}=\alpha^{op}$. Various important properties of set functors also apply to endofunctors on locally finitely presentable categories which are graduated. This means that every finitely presentable object $X$ carries a grade (in $\mathbb{N}$) and grades respect subobjects and strong quotients of $X$. We characterize presheaf categories $\mathbb{Set}^{\mathcal{A}^{op}}$ which are graduated for three types of small categories $\mathcal{A}$. If $\mathcal{A}$ is a poset, all down sets of elements must be finite. For a group $\mathcal{A}$, a finite bound on the length of a chain of subgroups must exist. In the case of cartesian categories $\mathcal{A}$, every object must carry a finite number of sieves. Example: all finitary set functors form a graduated category, here $\mathcal{A}$ is the dual of finite sets. A closely related concept is a locally finitely presentable category with the descending chain condition (a DCC category): every finitely presentable object has only finite descending chains of subobjects or strong quotients. The presheaf category on a group $G$ is $DCC$ iff $G$ has no infinite chain of subgroups. Example: presheaves on the group $\mathbb{Z}$ are not $DCC$, but finite generation implies finite presentation.
Read the full abstract

Algebraic Geometry

Symmetry and solvability: Galois groups of equivariant enumerative problems

At the genesis of Galois theory at the end of the 19th century, enumerative geometers were concerned with the solvability of various problems: for instance whether one can express lines on a cubic surface in radicals in terms of the coefficients that define it. By work of Hermite and a celebrated theorem of Harris, this is equivalent to determining whether the monodromy group of a certain finite étale cover is solvable. This problem, as well as the related problem of computing bitangents to plane quartics, are both unsolvable. When one restricts to the locus of $G$-symmetric cubic surfaces, monodromy will drop and can become solvable. In this setting there are four flavors of monodromy one can consider: the one from restricting the classical cover, the one over the GIT quotient after modding out by projective transformations, and two related notions of "monodromy" coming from the stacky cover of $G$-symmetric lines on $G$-symmetric cubic surfaces - unlike in the non-symmetric setting these are all different. In this paper we characterize the relationships between all four notions of monodromy in the general setting of quotient stacks, and use these connections to compute all these monodromy groups for all 11 possible automorphism groups of smooth cubic surfaces, as well as for all 12 possible automorphism groups for smooth planar quartics. We demonstrate that, in the presence of any symmetry whatsoever, the problem of solving for lines on cubic surfaces or bitangents to plane quartics is solvable.
Read the full abstract

Optimization and Control

Feedback Stabilization for Sampled Linear Systems with Control-linear Noise

In this paper, we consider linear stochastic systems with control-linear noise and periodically sampled measurements. We address the problem of feedback stabilization in the mean-square sense. The main contribution of the paper is to provide a necessary and sufficient condition for feedback stabilization. In particular, we relate feedback stabilizability of the stochastic system to the existence of a fixed point of a Riccati-type algebraic equation and, further, to the existence of a solution to an infinite-horizon optimal control problem.
Read the full abstract

Analysis of PDEs

Sharp critical Strichartz estimates for a resonant hyperbolic Schrödinger flow on the 3D waveguide

We study critical Strichartz estimates for the resonant hyperbolic Schrödinger flow on the waveguide $\mathbb{R} \times \mathbb{T}^2$. For initial data localized to frequencies at most $N$, we prove that the unit-time $L^2\to L^{10/3}$ operator norm has sharp order $N^{1/5}$. We further track its dependence on the observation length, obtaining sharp estimates in the short- and long-time regimes and characterizing the frequency-dependent intervals on which the critical estimate remains lossless. The precise dependence on $T$ in the intermediate regime $N^{-1}<T<1$ remains open. The upper bounds are obtained by lifting the global endpoint estimate on the elliptic cylinder $\mathbb{R} \times \mathbb{T}$ to Hilbert-valued data, preserving its time summability, and combining this with periodic Bernstein and interpolation. The lower bounds exploit an exact integer null direction in the periodic frequency lattice together with a suitably scaled Euclidean wave packet. Finally, using a Bloch–Floquet transference argument, we recover the known elliptic unit-time estimate from compact torus theory and obtain a lossless elliptic estimate on frequency-dependent short time intervals.
Read the full abstract

Algebraic Geometry

Fourier-Mukai partners and autoequivalences of moduli spaces of vector bundles

We classify the smooth projective Fourier–Mukai partners and determine the derived autoequivalence group of the moduli space $U_C(r,d)$ of stable bundles of coprime rank $r\geq2$ and degree $d$ on a smooth complex projective curve, assuming $g(C)\geq3$ and $\Aut(C)=1$. When the Jacobian $J(C)$ has endomorphism ring $\Z$, the partners are indexed by $(\Z/r\Z)^\times/\{\pm1\}$. We also prove that two coprime moduli spaces of vector bundles over complex curves of genus at least four are derived equivalent if and only if they are isomorphic.
Read the full abstract

Geometric Topology

A Concordance Invariant For Knots from $CFK^\infty$

We construct a multi-filtered smooth knot concordance invariant, $\beta(t^1, a, t^2)$, derived from the knot Floer complex $CFK^\infty$. $\beta$ is a three-variable piecewise linear function defined on $(0,2) \times \mathbb{R} \times (0,2)$. We demonstrate that $\beta$ satisfies a subadditivity relation. We apply $\beta$ to prove concordance results for a certain family of L-space knots. We show that the positive cones spanned by Teragaito's knots $K_{1,n}$ and $K_{2,n}$ are disjoint in the smooth concordance group $\mathcal{C}$. For positive L-space knots, we show $\beta$ completely determines the Alexander polynomial and distinguishes knots with identical $\Upsilon$ invariants.
Read the full abstract

Mathematical Physics · Cross-listed from cond-mat.stat-mech

Unified description of random motions and generalized Fokker-Planck equations

This review surveys diverse types of random motion within a unified framework, introducing essential mathematical tools, including special functions and fractional calculus, in a pedagogical manner. We focus on generalized random motions in one-dimensional space described by Fokker-Planck like equations, whose fundamental solutions take a universal and simple form in the Laplace-Fourier domain in terms of a generic function $\varphi(s)$. By exploring the functional forms of $\varphi(s)$ consistent with physical constraints, we derive a broad class of stochastic dynamics. This includes Brownian and active motion, simple and anomalous diffusion, and processes featuring stochastic resetting or trapping mechanisms. For each case, we provide the corresponding kinetic equation, explicit solutions (where available), and mean-square displacements alongside their asymptotic behaviors. Finally, we discuss the physical interpretation of these motions through the lens of time-changed processes and subordinators.
Read the full abstract

Algebraic Geometry

The geometry of solutions to the general sextic

We study the geometry of the three simplest known formulas for roots of a general sextic polynomial. In contrast with work of Green on the quintic, we show that no "simultaneous uniformization" of the normal forms associated to the solutions exists. This demonstrates an intrinsic qualitative complexity of sextic equations that is not present in quintic equations. Additionally, we give a formula for the roots of a general sextic in terms of Hilbert modular cusp forms and the uniformizing differential equation of the associated Hilbert modular surface.
Read the full abstract

Differential Geometry · Cross-listed from gr-qc

On the completeness of gravitational pp-wave spacetimes: A counterexample to the {Ehlers–Kundt} conjecture

This paper concerns the geometry of gravitational pp-wave spacetimes. We give a counterexample to the Ehlers–Kundt conjecture. In fact, we show that geodesic completeness is generic, in the sense of Baire category, among gravitational pp-waves. We also define a concept of “universal pp-wave”, i.e. a pp-wave whose metric approximates that of every other gravitational pp-wave arbitrarily closely on arbitrarily large compact sets, and we show that there are geodesically complete universal pp-waves. Our machinery also suffices to give a new proof of the polynomial case of the Ehlers–Kundt conjecture (previously proved by Flores and Sánchez).
Read the full abstract

Analysis of PDEs

A phase-field model for the Verigin problem: weak solutions and sharp-interface limit

We introduce a novel phase-field model approximating the Verigin problem with phase transition. For fixed interface thickness $\varepsilon>0$, we construct weak solutions through a time-discrete variational scheme combining a Wasserstein minimizing-movement for the density with Schätzle's selection procedure for the phase field, which yields strong compactness and an almost-minimizing property. We then investigate the sharp-interface limit $\varepsilon \downarrow0$. For well-prepared initial data, we establish strong compactness of the densities and phase fields, and we prove convergence of the time-integrated diffuse interfacial energy to the perimeter. The limiting evolution is identified as a weak solution of the Verigin problem with phase transition, satisfying an optimal energy dissipation inequality.
Read the full abstract

Analysis of PDEs

Nondegenerate gradient Young measures and dimension reduction for nonlinear membranes

We consider the rigorous derivation of membrane theories from three-dimensional nonlinear elasticity. A salient feature of our framework is the inclusion of an orientation-preservation constraint together with energy growth that penalizes vanishing local volume. We embed the 3D variational problem into a space of parametrized measures, and obtain a membrane $\Gamma$-limit defined on a class of nondegenerate gradient Young measures. This formulation offers a twofold advantage: first, it uniquely identifies a non-relaxed membrane energy density capable of capturing the fine oscillations (microstructure) of minimizing sequences; second, the resulting membrane density preserves the unbounded energy growth near degenerate configurations. We further show that the classical relaxed membrane energy of Le Dret and Raoult is recovered as the minimum of our functional over all measures with a prescribed barycenter. The main difficulty lies in generating such measures by maps whose gradients have rank two almost everywhere, which we address through piecewise isometric (origami-like) constructions.
Read the full abstract

Combinatorics

Density regularity of $\{x,x+y,xy\}$ in the integers

Fix $k,s\in\mathbb{N}$. We prove that there exists a subadditive density on $\mathbb{N}$ such that, for every polynomial $P\in\mathbb{Z}[y]$ of degree $k$ and with $P(0)=0$, every set of positive density contains configurations $\{x,x+P(y),xy^s\}$ for arbitrarily large $x>y\geq 2$. This provides a density strengthening of Moreira's result on partition regularity for $\{x,x+y,xy\}$.
Read the full abstract

Metric Geometry

Volume stability of plank covers

We prove a longstanding conjecture of András Bezdek on the stability of plank covers of the planar disk $D$. If a sufficiently small disk $\varepsilon D$ is removed, then every finite family of planks covering the resulting annulus can be rearranged to cover the whole disk. For the proof, we establish a stronger dimension-independent stability theorem. If $K \subset {\mathbb R}^n$ is an origin-symmetric convex body for $n \geq 2$, and the uncovered region lies in $\varepsilon K$ and has volume $v$, then the excess overlap is at least $c v/\varepsilon$, where $c>0$ is an absolute constant. The proof introduces a pruning procedure and a flattening mechanism. Pruning peels away curvature through local removals whose cumulative effect is guaranteed to be substantial. Flattening trades straightness for bounded multiplicity and geometrically exposes the overlap that pays for each pruning step.
Read the full abstract

Number Theory

Supercharacter theory and applications to Ramanujan sums over a finite Frobenius ring

The theory of Ramanujan sums has been playing a fundamental role in several subfields of mathematics. They appear in the theory of special values of zeta functions, spectral graph theory, representation theory, and analytic number theory. Recent work has shown that classical Ramanujan sums can also be interpreted as a super-Fourier transform via the theory of supercharacters for the ring $\mathbb{Z}/n$. In this article, building upon our recent work on supercharacters over an arbitrary finite Frobenius ring, we explore additional arithmetical properties of Ramanujan sums. Our approach provides a unified framework that generalizes various results in the literature regarding these sums. As a by-product, we also describe a new criterion for determining when a finite commutative ring is Frobenius, which could be of independent interest to the algebra community.
Read the full abstract

Geometric Topology

Planar Contact Structures with Calabi-Yau Fillings and Topological Quantum Computation

We study planar openbooks obtained by lifting braids through branched covers of D^2, together with the quantum operations in the Ising representation. We give a criterion for the Stein fillings to be Calabi-Yau (CY). Among positive factorizations of a fixed monodromy, a CY one has minimal length and its filling minimizes \chi and b_2. Applied to Baykur's recent examples, this gives a planar contact 3-manifold with infinitely many non-homeomorphic CY fillings, the cover there having degree \ge 6. At degree 4 a single CY filling forces every filling to be CY, and in one case the filling is unique; at degree \le 3 it is unique, and CY under a mild condition. Admissible cuts of D^2 decompose the openbook into subopenbooks. Every positive factorization then localizes, and the CY condition holds exactly when it holds locally. The state space is then a direct sum of tensor products indexed by the compatible parity choices, with at most two qubits per factor when the pieces have degree $\le 4$, the same range in which the CY condition depends only on the monodromy. For one degree 4 cover, the points, lines and flags of the two-qubit doily are realized by its subopenbooks. Fifteen liftable braids there share the same quantum operation and Stein filling, and are separated only by the subopenbook systems they admit. A choice of tensor-product structure is thus carried by the lift, not by the braid group representation, suggesting a link between contact topology and quantum entanglement.
Read the full abstract

Analysis of PDEs

Floquet instability near a stationary Euler flow in 3D

We study the three-dimensional (3D) incompressible Euler equation linearized about a smooth compactly supported stationary flow of Gavrilov type. Baldi's volume-preserving action–angle chart allows a reduction of the high-frequency amplitude equation on invariant tori. Using Baldi's chart, we identify a critical torus ensured by the compact cutoff. We show that, for a fixed axisymmetric covector with sufficiently large normal component, the reduced trace-free periodic cocycle on this torus is hyperbolic and has a positive Floquet exponent. A localized geometric-optics construction then lifts this Floquet instability to the linearized Euler equation, yielding exponential essential-norm growth in space $H^s$, $s\geq 0$.
Read the full abstract

Mathematical Physics · Cross-listed from quant-ph

Optimal noisy sequential multiparameter quantum sensing

The most general strategy for estimating parameters of a quantum channel is to probe the channel many times sequentially with the help of coherent ancillary systems. However, finding the strategy that minimizes the mean-squared error (MSE) is a notoriously hard problem, requiring optimization over the initial probe state, intermediate evolutions, final measurement, and classical postprocessing. In this work, we study how the minimum attainable MSE can be bounded from below in this setting. We propose a lower bound for the MSE of any physically implementable sequential sensing strategy that applies to estimating parameters of any physical quantum evolution, including quantum channels probed over multiple time steps under temporally correlated noise and general temporally correlated quantum processes. We show that this lower bound can be formulated as a semidefinite program (SDP). Our bound generalizes the Nagaoka-Hayashi lower bound (that applies to parameter estimation tasks with separable measurements) to the regime where the quantum channel can be accessed sequentially multiple times. For regular finite-dimensional single-parameter sequential estimation tasks admitting an optimal strategy, we show that our SDP bound is tight and provide a procedure to obtain a locally optimal strategy from the SDP optimizer. Using our optimization bound, we compute the MSE lower bound and derive new protocols for several other physically motivated problems including error-corrected quantum sensing under an unknown correlated noise model, multiparameter estimation, and estimation with qudit systems.
Read the full abstract

All authors Andrew Tanggara, Lorcán O Conlon, Alexey V. Gorshkov, Kishor Bharti

Mathematical Physics · Cross-listed from cond-mat.str-el

Disentangling the Toric Code

Commuting-projector Hamiltonians with integer spectrum such as the 1+1d Ising ferromagnet and the 2+1d toric code may be regarded as the generators of non-on-site $U(1)$ symmetries. In this paper we study whether these symmetries can be made on-site in the presence of finite and infinite-dimensional ancillae. In the finite-dimensional case, we prove that the fractionalized excitations, such as domain walls and anyons, make it impossible to on-site these Hamiltonians. On the other hand, we show that when infinite dimensional ancillae (e.g., rotors) are allowed, both the 1+1d Ising ferromagnet and the 2+1d toric code can be disentangled, yielding on-site symmetries. This is not in contradiction with the non-trivial ground state order of these Hamiltonians, since the ancilla Hamiltonians are no longer bounded from below. Our results indicate agreement between lattice and quantum field theory anomalies in the presence of infinite-dimensional ancillae, while with finite-dimensional ancillae the obstruction to on-siteability may even be non-invertible.
Read the full abstract

All authors Lei Gioia, Salvatore D. Pace, Ruben Verresen, Shu-Heng Shao, Ryan Thorngren

Combinatorics

A short note on $K_{n}$-irregular graphs

This note addresses Theorem 12 in the seminal paper “$F$-degrees in graphs” by G. Chartrand et al. (1987), which asserts the existence of $K_n$-irregular graphs for each $n \ge 3$. Although this result is widely cited in the literature as an established fact, the original text lacks a complete proof. We show that for $n = 5$ and all $n \ge 7$, the constructions as presented are not $K_n$-irregular, presumably due to typographical errors. Consequently, referencing this foundational work as containing a rigorous proof for the general case is not entirely accurate.
Read the full abstract

Combinatorics · Cross-listed from cs.DS

Spanning Trees with Many Leaves in Graphs of Minimum Degree at Least 7

We give a polynomial-time algorithm that constructs, in every connected $n$-vertex graph of minimum degree at least $7$, a spanning tree with at least $\frac{25200}{46189}n>0.5455\,n$ leaves. No bound specific to minimum degree $7$ was known: the best bound available for this class was $\frac{11}{21}n\approx0.5238\,n$, inherited from Simarova's theorem for minimum degree~$6$. The algorithm and its analysis are carried out for an arbitrary minimum degree $\delta$, and yield a recursion that gives an explicit lower bound on the number of leaves for every $\delta$. The resulting bounds improve all previously known ones for every $\delta\ge7$; for $\delta=8,9,10$ they are $0.5850\,n$, $0.6151\,n$ and $0.6413\,n$, and they are tabulated for $\delta\le25$ at the end of the paper.
Read the full abstract