Mathematical Physics · Cross-listed from quant-ph
Papers
Fresh from arXiv, typeset properly. Highlighted words trade on the market.
Thursday 30 April
Kramers-Kronig (KK) relations rest on a binary premise: a response function is either analytic in the upper half-plane or it is not. We show that a single reduced-state transform organizes both outcomes into a sharp dichotomy controlled by microscopic unitarity. One closed-form function carries, simultaneously, a zero and a pole in the upper half-plane; the spectral abscissa alpha of the reduced propagator decides which is realized. For alpha < 0 (unitary reduction) the upper-half-plane object is a protected zero: KK holds, yet the zero is directly measurable from a finite-time coherence record by a damped Fourier transform (no analytic continuation), obeying a closed law Im(zeta) = 0.3092 g. For alpha > 0 (gain-driven non-unitary reduction) the zero is replaced by a genuine pole, the Blaschke winding number jumps from 0 to 1, and KK acquires a Lorentzian residue correction scaling as a power law with negative exponent nu ~ -1.08, peaking at threshold. The protected zero is not inert: any scalar single-channel kernel extraction is forced to reproduce a phantom resonance – a refractive feature with no absorptive origin, at a protocol-independent frequency – without any initial system-bath correlation. We give the closed-form criteria, a measurable terahertz signature (31-1391 GHz), and the solvable dimer and Jaynes-Cummings models that realize both sides of the boundary.
Analysis of PDEs
Formation and Behavior of Dirac Singularities in the Parabolic-Elliptic Keller-Segel System in Dimensions $n\geq 3$
We consider nonnegative radially symmetric solutions of the parabolic-elliptic Keller-Segel system \begin{align*} \left\lbrace \begin{array}{r@{}l@{\quad}l} &u_t=\Delta u-\nabla \cdot \big(u\nabla v\big),\\ &0=\Delta v -\mu + u , \\ \end{array}\right. \end{align*} where $\mu$ is the spatial average of $u$, under homogeneous Neumann boundary conditions in a ball in $\mathbb R^n$ for $n\geq 3$. In two dimensions, it is well established that solutions blowing up in finite time converge to a Dirac profile in the vague topology. In contrast, for $n\geq 3$, blow-up solutions with finite existence time do not appear to exhibit such concentration behavior. By generalizing to measure-valued solutions corresponding to accumulated densities of $u$, we extend the analysis beyond the blow-up time. Within this framework, we establish the existence of a minimal solution \[ u(t)=\theta(t)\delta_0 + \rho(\cdot,t) dx, \qquad t \geq 0, \] where $\rho$ is integrable and $\theta$ is increasing and right-continuous. We further construct a class of initial data for which $\theta(t_0)>0$ for some $t_0>0$, thereby establishing the formation of a Dirac mass at the origin. Unlike in the case $n=2$, the singular mass does not jump to a positive level instantaneously; instead, $\theta$ becomes positive continuously. Moreover, $\theta$ is strictly increasing on $[t_0,\infty)$, and the entire mass is asymptotically absorbed at the origin.
Read the full abstract
Functional Analysis
Module-valued ordinary differential equations and structure of solution spaces
We define and study ordinary differential equations (ODEs) for functions valued in a Banach module $V$ over a finite-dimensional $\Bbbk$-algebra $\mathit{\Lambda}$ by using the tensor of Banach modules. Furthermore, we show that the solution space of a homogeneous linear ODE as above is shown to be a finitely generated $\mathit{\Lambda}$-submodule.
Read the full abstract
Mathematical Physics · Cross-listed from quant-ph
A Unified Framework for Locally Stable Phases
We propose a unifying framework for characterizing pure and mixed state phases of matter across equilibrium, non equilibrium, and metastable regimes. We introduce the concept of locally stable states, defined by the operational property that any local operation (including post selection) can be reversed by a local channel. We prove that local stability is equivalent to a state being short range correlated, defined by the decay of both correlations and conditional mutual information. We demonstrate that these properties are invariant under locally reversible channels, thus defining locally stable phases. Furthermore, we prove that local stability implies both the decay of a family of nonlinear correlators, including the fidelity correlator, and the decay of correlations in the canonical purification, thus bridging the gap between mixed and pure states. Along the way, we establish two results which may be of independent interest: we show that post-selection on locally stable (short range correlated) states can be implemented via local channels and that quantum Markov chains can be characterized by the local computability of nonlinear observables.
Read the full abstract
Combinatorics
The Many Faces of Magog Matrices
Magog matrices, introduced by Holmlund and Striker in 2025, provide a matrix model for totally symmetric self-complementary plane partitions (TSSCPPs), as a natural analogue of alternating sign matrices (ASMs). In this paper, we develop several new combinatorial representations of magog matrices, mirroring classical representations of ASMs. Specifically, we define magog analogues of corner-sum matrices, height-function matrices, fully packed loop configurations, and vertex models, and establish explicit bijections among all of these objects. These constructions provide new structural insight into the combinatorics of TSSCPPs and illuminate parallels and differences between the ASM and TSSCPP frameworks.
Read the full abstract
Mathematical Physics · Cross-listed from quant-ph
Essential Duality and Quantitative Channel Composability in Algebraic Quantum Field Theory
Let \(O\mapsto A(O)\) be a local Haag–Kastler net and let \(A^d(O)=A(O')'\) be its dual net. Normal unital completely positive maps on \(B(H)\) that fix \(A(O')\) pointwise are exactly the channels with Kraus operators in \(A^d(O)\). Thus Haag duality at \(O\) is equivalent to equality with the \(A(O)\)-inner channels, while essential duality is equivalent to order-independence of the corresponding causal-complement channel classes at spacelike separation. For self-adjoint generators \(a\in M\) and \(b\in N\), the small-parameter order defect has coefficient \(\operatorname{diam}\sigma(-i[a,b])\). Uniform optimization gives \(\Gamma(M,N)=2\Delta_{\mathrm{sa}}(M,N)\), and reversible inner-channel cb balls recover the same invariant through \(\lim_{\varepsilon\downarrow0}\Omega^{\mathrm{rev}}_\varepsilon(M,N)/\varepsilon^2=\Gamma(M,N)/4\). The full inner-channel class admits a normalized coefficient with the same commutativity zero set. With a positive reference observable \(G\), the mean-input-energy-constrained coefficient \(\Gamma_{G,E}\) has the same zero criterion and increases to \(\Gamma\) as \(E\to\infty\), while no model-independent recovery rate follows from the general von Neumann-algebraic hypotheses. For bosonic second-quantization nets the spacelike defect is either \(0\) or \(4\); generalized free-field examples realize both branches. In the translation-covariant case with positive one-particle time generator, failure of essential duality admits extremal bounded witness flows that are energy-limited relative to the second-quantized time-translation energy.
Read the full abstract
Geometric Topology
Fillable structures on negative-definite Seifert fibred spaces
We classify fillable contact structures on all negative-definite star-shaped plumbings. We show that such Seifert fibred spaces admit a unique negative maximal twisting number and compute it explicitly using the Alexander filtration in lattice cohomology, providing its first Floer-theoretic interpretation. In addition, we show that all the negative-twisting tight structures on these manifolds are induced by the Stein structures on the minimal resolution of the underlying complex surface singularity. As an application, we provide a necessary condition for a negative-definite Seifert fibred space to admit a separating contact-type embedding in a strong symplectic filling of a generalised $L$-space.
Read the full abstract
Geometric Topology
The hat and plus version of the Heegaard Floer contact invariant are not equivalent
We advance Matkovič ideas, originally applied to complete the classification of tight structures on small Seifert fibred $L$-spaces, to show the existence of contact structures on Brieskorn spheres which are tight and zero-twisting. This uncovers a phenomenon that has never appeared in literature before: namely, that a contact structure $\xi$ on a 3-manifold can be such that $\widehat c(\xi)$ is non-vanishing, but $c^+(\xi)$ is zero.
Read the full abstract
Geometric Topology
Heegaard Floer homology and maximal twisting numbers
We adapt the Ozsváth-Szabó full path algorithm to every star-shaped graph and establish a correspondence between negative-twisting tight contact structures on any Seifert fibred space over $S^2$, and its Heegaard Floer homology groups equipped with the Alexander filtration induced by the regular fibre. This provides the complete classification of negative-twisting structures on these manifolds; in particular, we distinguish them by their contact invariant $c^+$. We prove that every such structure is symplectically fillable and extend a known obstruction to Stein fillability. In addition, we show that the number of negative-twisting structures can be expressed combinatorially in terms of the Seifert coefficients of the star-shaped graph, while their $d_3$-invariant and homotopy type are determined explicitly through our correspondence. Our results also complete the classification of fillable structures on any small Seifert fibred space.
Read the full abstract
Information Theory
Optimal Transmitter Placement in Realistic Urban Environments
In a wireless network, transmitter locations strongly impact achievable rates. Cellular deployment is a difficult non-convex problem, typically addressed using simplified models and heuristics. We propose a mathematically rigorous framework incorporating detailed site-specific maps, material properties, and realistic attenuation. We introduce an aggregated network-quality functional scoring receiver-weighted signal quality, impose deployment costs via cardinality and budget constraints, and establish submodularity under practical conditions. To solve the optimization problem, we propose the Interference-Aware Submodular Placement Algorithm (IA-SPA) with a theoretical approximation guarantee relative to the optimum. IA-SPA incorporates existing base stations and prohibited areas, making it applicable to clean-slate and incremental deployments. We evaluate our approach using ray-tracing simulations on 3D maps of San Francisco and Florence, comparing against known deployments by AT and T, T-Mobile, and Iliad. Our strategy achieves significant increases in mean data rate (about 2x) and edge rate (2-8x) using the same number of transmitters. These gains persist under simultaneous exclusionary zones, small-scale fading, material/geometric perturbations, and incremental densification of existing networks. The pipeline has linear computational dependence on candidate sites, and wall-clock measurements demonstrate practical runtime at city scale.
Read the full abstract
Numerical Analysis
Beyond first-order accuracy in continuous-forcing immersed boundary methods, and their well-conditioned projection-based solution
We introduce a refined immersed boundary (IB) methodology that is better-than-first-order accurate in practice, while preserving key properties of "continuous-forcing" IB approaches that retain a singular source term in the governing equations. Our method leverages a smoothed indicator (Heaviside) function, following ideas from multiphase flow and immersed layers formulations, to recast the IB solution as a composite of distinct interior and exterior fields. We demonstrate that, when cast through this composite-solution lens, prior continuous-forcing IB methods can be seen as neglecting terms in the governing and constraint equations that restrict the solution to first-order accuracy. We incorporate these terms to systematically improve accuracy without the need for heuristic corrections. In canonical Poisson problems, we empirically demonstrate second-order convergence, and in incompressible Navier-Stokes simulations the method achieves slightly sub-second-order performance. While our present study focuses on these cases, the framework suggests a path towards second-order accuracy or higher, with further extensions. This perspective reframes accuracy limitations typically attributed to IB schemes. Although continuous-forcing IB methods are often reported to be only first-order accurate, we show that neither smoothing nor interface interpolation inherently restricts attainable order. Moreover, we naturally incorporate this higher-order formulation into a projection-based solution process. The resulting algorithm simultaneously mitigates the spurious surface stresses produced by ill-conditioned linear systems and reduces sensitivity to geometric resolution, addressing both conditioning and accuracy concerns within a unified approach.
Read the full abstract
Probability
Supercriticality of the SIRS on random networks
We study how long the SIRS process persists or how quickly it reaches extinction across various network topologies. Our results provide a three-part characterization of this process: In finite sparse graphs, we prove the existence of a regime where the process survives for an exponentially long time. In heavy-tailed networks with power-law-like exponents, we show that for all range of parameters, the survival time is exponential. Finally, for infinite trees, we find sufficient conditions for strong survival, showing the root is re-infected infinitely often even for light-tailed distributions like the Poisson distribution.
Read the full abstract
Optimization and Control · Cross-listed from cs.LG
Global Optimality for Constrained Exploration via Penalty Regularization
Efficient exploration is a central problem in reinforcement learning and is often formalized as maximizing the entropy of the state-action occupancy measure. While unconstrained maximum-entropy exploration is relatively well understood, real-world exploration is often constrained by safety, resource, or imitation requirements. This constrained setting is particularly challenging because entropy maximization lacks additive structure, rendering Bellman-equation-based methods inapplicable. Moreover, scalable approaches require policy parameterization, inducing non-convexity in both the objective and the constraints. To our knowledge, the only prior model-free policy-gradient approach for this setting under general policy parameterization is due to Ying et al. (2025). Unfortunately, their guarantees are limited to weak regret and ergodic averages, which do not imply that the final output is a single deployable policy that is near-optimal and nearly feasible. In this work we take a different approach to this problem, and propose Policy Gradient Penalty (PGP) method, a single-loop policy-space method that enforces general convex occupancy-measure constraints via quadratic-penalty regularization. PGP constructs pseudo-rewards that yield gradient estimates of the penalized objective, subsequently exploiting the classical Policy Gradient Theorem. We further establish the regularity of the penalized objective, providing the smoothness properties needed to justify the convergence of PGP. Leveraging hidden convexity and strong duality, we then establish global last-iterate convergence guarantees, attaining an $\epsilon$-optimal constrained entropy value with $\epsilon$-bounded constraint violation despite policy-induced non-convexity. We validate PGP through ablations on a grid-world benchmark and further demonstrate scalability on two challenging continuous-control tasks.
Read the full abstract
Combinatorics
The proportion of permutations fixing a $k$-set
Denote by $p(k)$ the limit, as $n \rightarrow \infty$, of the probability that a random permutation on a set of size $n$ has an invariant set of size $k$. We give an asymptotic formula for $p(k)$, showing that it is asymptotically $f(\{\log_2 k\}) k^{-\delta} (\log k)^{-3/2}$ where $\delta = 1 - \frac{1 + \log \log 2}{\log 2} \approx 0.086$ and $f$ is a smooth, positive, function on $\mathbb{R}/\mathbb{Z}$, which we will describe explicitly. The function $f$ satisfies $\frac{\max f}{\min f} < 1 + 2 \times 10^{-7}$ and we conjecture that it is not constant. Estimating $p(k)$ is a model for the more well-known question which asks for an estimation of $M(n)$, the number of distinct elements in the $n$-by-$n$ multiplication table. By elaborating on the techniques in this paper, we will give an asymptotic for $M(n)$ in forthcoming work.
Read the full abstract
Mathematical Physics · Cross-listed from hep-th
BV quantization of $\phi^3$-theory on $\lambda$-Minkowski space: Tree-level correlation functions
We review the quantization of scalar field theory on $\lambda$-Minkowski space using the Batalin–Vilkovisky (BV) formalism. We consider $\phi^3$-theory in two different quantization schemes: standard and braided. While standard BV quantization is based on an ordinary $L_\infty$-algebra, braided BV quantization is based on a braided $L_\infty$-algebra. We compare the tree-level three-point and four-point correlation functions in the two approaches. For the four-point function, standard quantization leads to two inequivalent classes of diagrams with different noncommutative contributions, whereas braided quantization yields only a single class of diagrams with noncommutativity entering solely through an overall phase factor depending on the external momenta.
Read the full abstract
Optimization and Control
A Scaled Gradient Modified Non-monotone Line Search Method for Constrained Optimization Problems
In this paper, we propose a scaled gradient modified non-monotone line search method for solving constrained minimization problems, and explore several specific properties of this method, namely, its convergence analysis. We discuss the linear convergence rate of the sequence generated by the proposed algorithm to a solution of the constrained minimization problem where the objective function is strongly quasiconvex. We consider numerical examples of large-scale fractional programming and quadratic programming for the function of pseudo convex and strongly quasiconvex and compare the performance of the proposed algorithm with the existing ones for these examples.
Read the full abstract
Statistics Theory · Cross-listed from stat.ME
Kernel-based independence and mean independence tests for weakly dependent data
We provide a unified framework for independence and mean independence tests based on the Hilbert-Schmidt independence criterion, extending some previous results in the literature to hold in general topological spaces. We also present a complete theoretical analysis of the test statistic asymptotic behavior when the observed sample corresponds to a partial sample path of some stationary and ergodic stochastic process under near epoch dependence assumptions. In particular, we explore the test statistic consistency and limit distribution under both fixed and local hypothesis. The finite sample performance of the test(s) is illustrated with a succinct simulation study involving functional data.
Read the full abstract
Numerical Analysis
Bounded, Commuting, Discrete-trace Preserving Projections
We construct bounded, commuting projections for the three-dimensional de Rham complex with the additional property that the projections preserve the trace of functions/fields if the latter is a piecewise polynomial in the appropriate trace space. The projections are locally defined and stable in the graph norm. More precisely, the part of the graph norm involving the exterior derivative only involves the oscillation of this derivative in a narrow strip of elements touching the boundary and weighted by the local mesh size. Moreover, the projections are $L^2$-stable locally when acting on functions/fields whose exterior derivative is a piecewise polynomial in the appropriate space. We present two salient applications of the present bounded, commuting, discrete-trace preserving projections: the construction of stable liftings of piecewise polynomial data and an optimality result on the discrete versus continuous extension of piecewise polynomial data.
Read the full abstract
General Topology
On centered local $\pi$-bases
In 1967 Hajnal and Juhász showed that the cardinality of a first-countable Hausdorff space with the countable chain condition has cardinality at most $\mathfrak{c}$, the cardinality of the real line. We give an improvement of this celebrated theorem by replacing “first-countable" with the weaker condition “each point has a countable centered local $\pi$-base". Given a point $p$ in a topological space $X$, a local $\pi$-base $\scr{B}$ at $p$ acts like a neighborhood base at $p$ except that $p$ may not be in any member of $\scr{B}$. A local $\pi$-base $\scr{B}$ has the finite intersection property if any finite intersection of members of $\scr{B}$ is nonempty. We call this type of local $\pi$-base centered. A centered local $\pi$-base behaves even more like a neighborhood base in a sense. A space has the countable chain condition if every family of pairwise disjoint open sets is countable. We also improve a theorem of Pospi{\v s}il from 1937 using centered local $\pi$-bases. As is customary, examples are given to demonstrate these improvements are strict. Compact Hausdorff spaces are also explored in this connection, along with variations on the notion of a centered local $\pi$-base.
Read the full abstract
Analysis of PDEs
Nonlinear evolution equations with a non-Lipschitz perturbation: convergence of successive approximations and uniqueness of solutions
Algebraic Geometry
Abundance for semi log canonical compact Kähler threefolds
In this article we show that if $(X,\Delta)$ is a compact Kähler slc pair of dimension $3$ such that $K_X+\Delta$ is nef, then $K_X+\Delta$ is semiample. Moreover, we extend our result to a special subclass of Fujiki class $\mathcal{C}$ varieties, and show that in this subclass, if $(X, \Delta)$ is a slc pair and $K_X+\Delta$ is nef but not numerically trivial, then it is semiample. Moreover, we also construct a slc pair $(X, \Delta)$ in Fujiki class $\mathcal{C}$ such that $K_X+\Delta \equiv 0$ but $K_X+\Delta$ is not semiample. In particular, the slc abundance fails for Fujiki class $\mathcal C$ varieties.
Read the full abstract
Information Theory
Perfectly Private Over-the-Air Computation
This paper studies a key research question: how to achieve perfect privacy in over-the-air computation (AirComp)? The problem is particularly intriguing due to a dilemma. Real-field operations can ensure invertibility but generally introduce statistical dependence, resulting in inevitable privacy leakage. In contrast, modulo operations can decorrelate the output from the original message, but suffer from the ill-posed invertibility when applied over non-prime groups (e.g., the real field). This raises a subtle yet fundamental question: Does perfect privacy intrinsically conflict with AirComp? We show that the answer is no. By carefully leveraging the interplay between real-field and modulo operations, perfect privacy and accurate computation can, in fact, be achieved simultaneously, enabling perfectly private aggregation.
Read the full abstract
Number Theory
A torsion-intersection proof of perfect-cuboid nonexistence on 1,072 explicit master-tuple fibers
Building on the genus-3 reduction $C_A : w^2 = \lambda^8 + A \lambda^4 + 1$ established in our companion paper (arXiv:2604.09328), we give an unconditional proof of the perfect-cuboid conjecture ("Conjecture B") on $1{,}072$ explicit master-tuple fibers, excluding all rational $(a,b)$-specialisations on each such fiber. Our three main contributions are: (i) a structural classification theorem showing that every primitive Euler-brick arises from the standard $(a,b,m,n)$-parametrisation up to scaling; (ii) a torsion-intersection argument applied to the elliptic quotients $E_A'$ and $E_A''$: whenever the rank-zero hypothesis and the appropriate torsion condition hold for one of them, $|H_{m,n}(\mathbb{Q})| = 8$ is forced, with the eight points all corresponding to degenerate bricks; (iii) two complementary techniques to verify the rank-zero hypothesis algorithmically – PARI's ellrank (2-descent) and, where this is ambiguous, Sage's exact rational evaluation of $L(E,1)/\Omega_E$ via modular symbols, which combined with the modularity theorem, Kolyvagin's theorem, and Edixhoven's bound on the Manin constant for semistable curves yields an unconditional rank-zero certificate – together with an explicit lift count refining the naive torsion-intersection bound when the torsion is larger than the leading case. We exhibit $1{,}072$ such fibers with $\max(m,n) \le 100$ on which Conjecture B is thereby established unconditionally.
Read the full abstract
Probability
Mean-square Stability and Bifurcations for Dissipative SDEs
We investigate the dynamics of dissipative systems with stochastic forcing and focus in particular on mean-square stability. First we show, under a natural condition on the drift and diffusion, that the stochastic system is mean-square dissipative. Next we examine the linearised system and state conditions ensuring that perturbations of a linear system with affine noise are bounded. We then relate the mean-square dynamics of the nonlinear and linearised systems. The approach gives a straightforward deterministic method to examine the effects of stochastic forcing on the stability of equilibria of deterministic systems and to obtain bifurcation diagrams that can be included into standard numerical continuation packages. The technique is illustrated numerically on some standard and non-standard examples.
Read the full abstract
Logic
Hallucination, abstention, and computable inseparability
The impossibility of eliminating hallucination, understood here as incorrect definite answers, in sufficiently expressive yes-or-no formal domains is an immediate consequence of classical undecidability theorems. This note does not revisit that forced-answer obstruction as its main claim. Instead, it attempts to formally describe the corresponding limitation for abstaining systems. Abstention can trivially avoid hallucination if the system is allowed to abstain on every input; the substantive question is how large the domain of guaranteed correct non-abstaining answers can be. We formulate this question using separation in the arithmetical hierarchy. Given disjoint sets $A$ and $B$, any system that answers Yes on all queries indexed by $A$ and No on all queries indexed by $B$ induces a separator of $A$ from $B$. By combining this observation with the classical existence theorem of $\Delta_{n}^{0}$-inseparable pairs of $\Sigma_{n}^{0}$-sets, we yield a computability-theoretic trade-off between avoiding hallucination by abstention and maintaining a large domain of guaranteed coverage.
Read the full abstract
Combinatorics
Turán-Type Extremal Results for Distance-$k$ Graphs
We study Turán-type extremal problems for distance graphs, motivated by work of Csikvári, Bollobás, Tyomkyn, and Uzzell. We determine the maximum number of vertex pairs at distance three in an $n$-vertex graph with no triangle formed by these pairs, resolving the first case of a conjecture of Tyomkyn and Uzzell. We also determine the maximum number of vertex pairs at distance two in an $n$-vertex graph with no triangle formed by these pairs and give a complete characterization of the extremal graphs, settling another problem of Tyomkyn and Uzzell.
Read the full abstract
Numerical Analysis
A near-optimal recovery algorithm for the Stokes equations with incomplete information on the boundary conditions
We address the problem of numerically approximating the velocity and pressure governed by the Stokes system when the boundary conditions are only partially known and thus do not uniquely determine the velocity-pressure couple. We propose an algorithm that takes advantage of available linear measurements of the velocity and pressure to construct a numerical approximation. This approximation is guaranteed to be near-optimal in the sense that it approximates the velocity-pressure couple that minimizes, in the energy norm, the distance to all other solutions satisfying the measurements and the Stokes system.
Read the full abstract
Combinatorics
Hypergraph independence bounds: from maximum degree to average degree
We prove a transfer theorem for hereditary classes of $(r+1)$-uniform hypergraphs. Let $\mathcal H$ be such a class, and for $H\in\mathcal H$ write $\Delta(H)$ and $d(H)$ for the maximum degree and average degree of $H$, respectively. We show that, for every nearly logarithmic function $f$ in the sense defined below, a maximum-degree lower bound for the independence number of the form \[ \alpha(H)\ge (1-o(1))\frac{f(\Delta(H))}{\Delta(H)^{1/r}}|V(H)| \qquad\text{as }\Delta(H)\to\infty \] for all $H\in\mathcal H$ implies the corresponding average-degree lower bound \[ \alpha(H)\ge (1-o(1))\frac{f(d(H))}{d(H)^{1/r}}|V(H)| \qquad\text{as }d(H)\to\infty . \] We combine this transfer theorem with known coloring and fractional-coloring bounds to obtain consequences for graphs excluding a fixed cycle, graphs with bounded clique number, locally $q$-colorable graphs, and locally sparse uniform hypergraphs.
Read the full abstract
Information Theory · Cross-listed from cs.LG
Exponential families from a single KL identity
Exponential families encompass the distributions central to modern machine learning – softmax, Gaussians, and Boltzmann distributions – and underlie the theory of variational inference, entropy-regularized reinforcement learning, and RLHF. We isolate a simple identity for exponential families that expresses the KL difference $\mathrm{KL}(q \| p_{\lambda_2}) - \mathrm{KL}(q \| p_{\lambda_1})$ in terms of the log-partition function $A(\lambda)$ and the moment $\mu_q$. Remarkably, this identity together with the single fact that $\mathrm{KL} \geq 0$ (with equality iff $p = q$) suffices, by direct substitution and rearrangement, to derive a cluster of results that are classically obtained by separate, heavier arguments: a generalized three-point identity for arbitrary reference distributions, Pythagorean theorems for I-projections and reverse I-projections, convexity of the log-partition function, identification of its Legendre dual in KL terms, the Gibbs variational principle, and the explicit optimizer in KL-regularized reward maximization, including the exponential tilting formula underlying entropy-regularized control and RLHF. Beyond these purely algebraic consequences, standard analytic arguments recover the gradient formula for the log-partition function, the Bregman representation of within-family KL divergence, and the surjectivity of the moment map. The note is self-contained.
Read the full abstract
Combinatorics
Extremal graphs for average size of maximal matchings in bicyclic graphs
For a graph \(G\), let $avm(G)$ denote the average size of its maximal matchings. This parameter was introduced by Engbers and Erey in the study of extremal problems for maximal matchings, and they asked for extensions from trees and unicyclic graphs to \(k\)-cyclic graphs. In this paper, we solve the first non-unicyclic case by determining the minimum value of $avm(G)$ over all connected bicyclic graphs with \(n\) vertices and \(n+1\) edges. We prove that, for every connected bicyclic graph \(G\) of order \(n\ge 5\), \[ \operatorname{avm}(G)\ge \frac{4n-11}{2n-5}. \] Moreover, equality holds uniquely for the graph obtained from two triangles sharing a common edge by attaching all remaining \(n-4\) pendant edges to one of the two vertices of degree \(3\). The key point is to translate the minimization of \(\operatorname{avm}(G)\) into structural restrictions on small maximal matchings, which are then analyzed through the three possible bicyclic core types.