Peer Revenue Returns subject to peer review

Papers

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

Mathematics

math Watch Mathematics (sign in to use)

Thursday 12 March

Mathematical Physics

On Exotic Materials in 3D Linear Elasticity with High Symmetry Classes

An anisotropic elastic material is referred to as exotic when, under specific loadings, its mechanical response exhibits a higher degree of symmetry than that prescribed by its intrinsic material symmetry. Such materials, which may be regarded as lying, conceptually and functionally, between two distinct symmetry classes, are of significant practical relevance. They enable the tailored design of metamaterials capable of reconciling otherwise incompatible mechanical requirements; for example, achieving directional isotropy of the Young's modulus in an intrinsically anisotropic medium. This work focuses on the systematic classification of exotic structures within the framework of three-dimensional linear elasticity. An exhaustive classification is carried out, leading to the enumeration of 18 exotic structures corresponding to symmetry classes higher than orthotropy. Representative examples of exotic elastic behaviours are analysed in detail.
Read the full abstract

Combinatorics

On the structure of the sandpile identity element on Sierpinski gasket graphs

We consider the identity of the abelian sandpile group of finite approximation graphs of the Sierpinski gasket, and we show that the second-order term in the scaling limit converges to the path distance to the nearest corner on the Sierpinski gasket. The proof relies on a decomposition of the identity of the sandpile group into the sum of a constant function and the Laplacian of the graph distance on the approximating graphs.
Read the full abstract

Analysis of PDEs

Block operator matrix techniques for stability properties of hyperbolic equations

Inspired by recent developments in the theory of stability results in the context of certain wave type phenomena, we discuss abstract damped hyperbolic type equations given in a block operator matrix form with regards to asymptotic behaviour of their solutions. Under mild conditions on the operators involved we provide criteria establishing strong or semi-uniform stability. In the particular case of Maxwell's equations, these criteria are implied under mild regularity conditions of the underlying domain causing spatial derivative operators satisfy certain compact embedding conditions and rather minimal assumptions on the damping conductivity. These assumptions improve on both regularity as well as on the structural requirements for the conductivity previously available in the literature.
Read the full abstract

Analysis of PDEs

Exponential Stability for Maxwell-type Systems Revisited

Considering a two-by-two block operator matrix system of Maxwell type, we present an elementary way of deducing exponential stability under minimal smoothness (and boundedness) requirements of the underlying domains when applications are concerned. The approach is based on resolvent estimates using block operator matrices.
Read the full abstract

Mathematical Physics · Cross-listed from hep-th

Large-$N$ Torus Knots in Lens Spaces and Their Quiver Structure

We study torus knot invariants in the lens space $S^{3}/\mathbb{Z}_{p}$ within Chern–Simons theory. Using the surgery and modular description of lens spaces, we derive a general expression for the invariant of an $(\alpha,\beta)$ torus knot in this background. In the large-$N$ limit these invariants simplify and acquire a universal form: the invariant of an $(\alpha,\beta)$ torus knot in $S^{3}/\mathbb{Z}_{p}$ can be expressed in terms of the invariant of the $(\alpha,\alpha+p\beta)$ torus knot in $S^{3}$. After an appropriate redefinition of knot variables, the generating functions of these invariants exhibit a structure analogous to quiver partition functions. Since the associated quiver is independent of the rank $N$ and level $k$ of Chern–Simons theory, the large-$N$ result provides a direct way to identify the underlying quiver, allowing us to determine the quiver structure associated with torus knots in $S^{3}/\mathbb{Z}_{p}$.
Read the full abstract

All authors Ritabrata Bhattacharya, Suvankar Dutta, Naman Pasari, Nitin Verma

Optimization and Control · Cross-listed from cs.DS

Deterministic Algorithm for Non-monotone Submodular Maximization under Matroid and Knapsack Constraints

Submodular maximization constitutes a prominent research topic in combinatorial optimization and theoretical computer science, with extensive applications across diverse domains. While substantial advancements have been achieved in approximation algorithms for submodular maximization, the majority of algorithms yielding high approximation guarantees are randomized. In this work, we investigate deterministic approximation algorithms for maximizing non-monotone submodular functions subject to matroid and knapsack constraints. For the two distinct constraint settings, we propose novel deterministic algorithms grounded in an extended multilinear extension framework. Under matroid constraints, our algorithm achieves an approximation ratio of $(0.385 - \epsilon)$, whereas for knapsack constraints, the proposed algorithm attains an approximation ratio of $(0.367 -\epsilon)$. Both algorithms run in $\mathrm{poly}(n)$ query complexity, where $n$ is the size of the ground set, and improve upon the state-of-the-art deterministic approximation ratios of $(0.367 - \epsilon)$ for matroid constraints and $0.25$ for knapsack constraints.
Read the full abstract

All authors Shengminjie Chen, Yiwei Gao, Kaifeng Lin, Xiaoming Sun, Jialin Zhang

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

What is a minimum work transition in stochastic thermodynamics?

We reassess the concept of transition at minimum work in classical stochastic finite-time thermodynamics, when the system dynamics is modelled by a diffusion process. We show that a well-posed formulation of the optimal control problem corresponding to the minimization of the mean work done on the system during a finite-time transition necessarily requires taking into account speed limits on control protocols. This fact has major qualitative consequences. First, it permits to discriminate between optimal swift engineered equilibration and transitions at minimum work. Second, it shows that in the limit when speed limits are removed, only transitions specified by generalized Schrödinger bridges admit a consistent physical interpretation. To illustrate these points, we focus on the simplest model problem: a levitating particle in a Gaussian moving trap.
Read the full abstract

Probability

On the Coalescence Time Distribution in Multi-type Supercritical Branching Processes

Consider a population evolving as a discrete-time supercritical multi-type Galton–Watson process. Suppose we run the process for $T$ generations, then sample $k$ individuals uniformly at generation $T$ and trace their genealogy backwards in time. In the limiting regime as $T \rightarrow \infty$, the expected behaviour of the sample's ancestry has been analysed extensively in the single-type case and, more recently, for multi-type processes in the critical case. In this paper, we present a formula for the distribution function of the generation $t$ of the most recent common ancestor in terms of the limiting distribution of the normalised population size. In addition, we provide effective bounds for the decay of this distribution function to 1 in terms of the harmonic moments of the population size at generation $t$. In order to better understand the behaviour of these harmonic moments, we use a multi-type generalisation of the Harris–Sevastyanov transformation to express harmonic moments at generation $t$ in terms of moments of the transformed process at the first generation. We present numerical results demonstrating that it is possible to approximate the coalescence time distribution effectively in practical settings.
Read the full abstract

Optimization and Control · Cross-listed from cs.LG

On-Average Stability of Multipass Preconditioned SGD and Effective Dimension

We study trade-offs between the population risk curvature, geometry of the noise, and preconditioning on the generalisation ability of the multipass Preconditioned Stochastic Gradient Descent (PSGD). Many practical optimisation heuristics implicitly navigate this trade-off in different ways – for instance, some aim to whiten gradient noise, while others aim to align updates with expected loss curvature. When the geometry of the population risk curvature and the geometry of the gradient noise do not match, an aggressive choice that improves one aspect can amplify instability along the other, leading to suboptimal statistical behavior. In this paper we employ on-average algorithmic stability to connect generalisation of PSGD to the effective dimension that depends on these sources of curvature. While existing techniques for on-average stability of SGD are limited to a single pass, as first contribution we develop a new on-average stability analysis for multipass SGD that handles the correlations induced by data reuse. This allows us to derive excess risk bounds that depend on the effective dimension. In particular, we show that an improperly chosen preconditioner can yield suboptimal effective dimension dependence in both optimisation and generalisation. Finally, we complement our upper bounds with matching, instance-dependent lower bounds.
Read the full abstract

All authors Simon Vary, Tyler Farghly, Ilja Kuzborskij, Patrick Rebeschini

Number Theory

On the $2$-adic valuation of $\sigma_k(n)$

For a positive integer $k$, let \[ \sigma_k(n)=\sum_{d\mid n} d^k \] be the divisor function of order $k$, and let $\nu_p(m)$ denote the $p$-adic valuation of an integer $m$. Motivated by recent work on the $p$-adic valuation of $\sigma_k(n)$, we study $\nu_2(\sigma_k(n))$ in detail. We prove that, for every integer $n\ge 2$, \[ \nu_2(\sigma_k(n)) \le \begin{cases} \lceil \log_2 n \rceil, & \text{if $k$ is odd},\\[1mm] \lfloor \log_2 n \rfloor, & \text{if $k$ is even}. \end{cases} \] These bounds are best possible. More precisely, if $k$ is odd, then equality holds if and only if $n$ is a product of distinct Mersenne primes; if $k$ is even, then equality holds if and only if $n=3$. We also obtain an explicit formula for $\nu_2(\sigma_k(n))$ in terms of the prime factorization of $n$.
Read the full abstract

Functional Analysis · Cross-listed from cs.LG

Topological DeepONets and a generalization of the Chen-Chen operator approximation theorem

Deep Operator Networks (DeepONets) provide a branch-trunk neural architecture for approximating nonlinear operators acting between function spaces. In the classical operator approximation framework, the input is a function $u\in C(K_1)$ defined on a compact set $K_1$ (typically a compact subset of a Banach space), and the operator maps $u$ to an output function $G(u)\in C(K_2)$ defined on a compact Euclidean domain $K_2\subset\mathbb{R}^d$. In this paper, we develop a topological extension in which the operator input lies in an arbitrary Hausdorff locally convex space $X$. We construct topological feedforward neural networks on $X$ using continuous linear functionals from the dual space $X^*$ and introduce topological DeepONets whose branch component acts on $X$ through such linear measurements, while the trunk component acts on the Euclidean output domain. Our main theorem shows that continuous operators $G:V\to C(K;\mathbb{R}^m)$, where $V\subset X$ and $K\subset\mathbb{R}^d$ are compact, can be uniformly approximated by such topological DeepONets. This extends the classical Chen-Chen operator approximation theorem from spaces of continuous functions to locally convex spaces and yields a branch-trunk approximation theorem beyond the Banach-space setting.
Read the full abstract

Algebraic Topology

Directed homological and cohomological operations

In this short note, we present a persistence module approach to directed cohomology, dual to the directed homology introduced by the author in a previous article. We lay out the first properties of directed cohomology and in particular of cohomological operations, partially linked to some homological operations. We treat here both the case of a specific class of precubical sets and of general directed spaces.
Read the full abstract

Optimization and Control

Asymptotically Efficient Recursive Identification Under One-Bit Communications Achieving Original CRLB

This paper develops an asymptotically efficient recursive identification algorithm for autoregressive systems with exogenous inputs under one-bit communications. In particular, the proposed method asymptotically achieves the Cramer-Rao lower bound (CRLB) based on the original data before quantization (original CRLB), whereas existing approaches typically attain only the CRLB corresponding to the quantized observations. The primary reason is that the existing methods quantize only the current system output, resulting in non-negligible information loss under one-bit quantization. To overcome this challenge, we present a novel quantization method that integrates both current and historical system outputs and inputs to provide richer parameter information in one-bit data, allowing the information loss caused by quantization to become a minor term relative to the original CRLB. Based on this technique, a corresponding remote estimation algorithm is further proposed. To address the convergence analysis challenge posed by the non-independence of the one-bit data, we establish a new framework that analyzes the tail probability of integrated data formed by combining current and historical system outputs and inputs before quantization, thereby eliminating the need for the traditional independence assumption on the quantized data. It is proven that the remote estimate achieves asymptotic normality, and the error covariance matrix converges to the original CRLB, confirming its asymptotic efficiency. Compared to existing identification algorithms under one-bit data, this method reduces the asymptotic mean squared error by at least 36%. Several numerical examples are simulated to show the effectiveness of the proposed algorithm.
Read the full abstract

All authors Xingrui Liu, Jieming Ke, Mingjie Shao, Yanlong Zhao

Numerical Analysis

Reduced Order Model for Broadband Superabsorption of Waves by Metascreens

This work presents a new design for broadband absorption of low-frequency acoustic waves using a thin coating made of subwavelength acoustic resonators arranged periodically on a reflective surface. We first study the associated scattering problem and the corresponding subwavelength resonance problem, and then derive analytical approximations for the resonant frequencies and the reflection coefficient in terms of the periodic capacitance matrix in a half-space with a Dirichlet boundary condition. These approximations yield an effective macroscopic description of the coating via an impedance boundary condition and clarify the mechanism of superabsorption through an approximate coupling condition. Moreover, they lead to a reduced order model that enables efficient evaluation of the scattered waves over a frequency band and accelerates broadband absorption design. Building on this reduced order model, we develop a gradient based shape optimization method using shape derivatives of the resonant quantities to achieve broadband absorption. Numerical experiments demonstrate the broadband performance and the effectiveness of the proposed design procedure.
Read the full abstract

Commutative Algebra

Asymptotic prime divisors and Vasconcelos invariant

Let $R$ be a Noetherian ring, $I$ an ideal of $R$, and $M$ a finitely generated $R$-module. In this article, we prove that $$\mathrm{Ass}_R(M/I^{n} M) = \mathrm{Ass}_R(0:_{M} I) \cup \mathrm{Ass}_R(I^{n-1} M/I^{n} M) \text{ for all } n \gg 0.$$ We then investigate the asymptotic behaviour of the (local) Vasconcelos invariant of $M/I^{n} M$ as a function of $n$, when $R$ is $\mathbb{N}$-graded, $I$ is homogeneous, and $M$ is $\mathbb{Z}$-graded. When $I$ is generated by elements of positive degree, we show that, for sufficiently large n, the (local) Vasconcelos invariant of $M/I^{n} M$ either coincides with that of the colon submodule $(0 :_{M} I)$, or is a polynomial in $n$ of degree one whose leading coefficient is one of the degrees of the generators of $I$. This dichotomy depends exclusively on two cases determined by $(0:_{M} I)$. Thus, we recover and considerably strengthen the main results of Fiorindo-Ghosh [Nagoya Math. J. 258 (2025), 296-310.], where asymptotic linearity was shown under the additional assumption that $(0:_{M} I)=0$.
Read the full abstract

Combinatorics

Broadcasting Agents and Adversary: A new variation on Cops and Robbers

We introduce a new game played on graphs, “Agents and Adversary". This game is reminiscent of “Cops and Robbers" but has some fundamental differences. We classify infinite families of graphs as Agents-win and Adversary-win. We then define a new type of graph symmetry and use it to define a winning strategy for Adversary. Finally, we give tight upper and lower bounds for Agents' time-to-win on several infinite families of graphs.
Read the full abstract

Rings and Algebras

Structure of Flat Quadratic Quasi-Frobenius Lie Superalgebras via Double Extensions

A flat quadratic quasi-Frobenius Lie superalgebra is a quadratic Lie superalgebra equipped with an additional symplectic structure that is flat with respect to the natural symplectic product. In this paper, we introduce the notion of a flat quadratic double extension of a flat quadratic quasi-Frobenius Lie superalgebra, in the cases where both the symplectic structure and the quadratic structure are either even or odd. We show that, over an algebraically closed field, any such Lie superalgebra can be constructed through a sequence of flat quadratic double extensions starting from the trivial algebra $\{0\}$. Moreover, when the quadratic and symplectic structures have different parity, we introduce the notion of a planar double extension, which constitutes the main novelty of this paper. In this case, we prove that such Lie superalgebras have total dimension $4n$. Finally, we classify flat quadratic quasi-Frobenius Lie superalgebras of dimension at most four and present explicit examples in dimensions six and eight.
Read the full abstract

Information Theory · Cross-listed from cs.DM

Universal cycle constructions for k-subsets and k-multisets

A universal cycle for a set S of combinatorial objects is a cyclic sequence of length |S|that contains a representation of each element in S exactly once as a substring. If S is the set of k-subsets of [n] = {1, 2, . . . , n}, it is well-known that universal cycles do not always exists when applying a simple string representation, where 12 or 21 could represent the subset {1, 2}. Similarly, if S is the set of k-multisets of [n], it is also known that universal cycles do not always exist using a similar representation, where 112, 121, or 211 could represent the multiset {1, 1, 2}. By mapping these sets to an appropriate family of labeled graphs, universal cycles are known to exist, but without a known efficient construction. In this paper we consider a new representation for k-subsets and k-multisets that leads to efficient universal cycle constructions for all n, k >=2. We provide successor-rule algorithms to construct such universal cycles in O(n) time per symbol using O(n) space and demonstrate that necklace concatenation algorithms allow the same sequences to be generated in O(1) amortized time per symbol. They are the first known efficient universal cycle constructions for k-multisets. The results are obtained by considering constructions for bounded-weight de Bruijn sequences. In particular, we demonstrate that a bounded-weight generalization of the Grandmama de Bruijn sequence can be constructed in O(1) amortized time per symbol.
Read the full abstract

Numerical Analysis

Mixed precision thin SVD algorithms based on the Gram matrix

In this work, we present a mixed precision algorithm that leverages the Gram matrix and Jacobi methods to compute the singular value decomposition (SVD) of tall-and-skinny matrices. By constructing the Gram matrix in higher precision and coupling it with a Jacobi algorithm, our theoretical analysis and numerical experiments both indicate that the singular values computed by this mixed precision thin SVD algorithm attain high relative accuracy. In practice, our mixed precision thin SVD algorithm yields speedups of over 10x on a single CPU and about 2x on distributed memory systems when compared with traditional thin SVD methods.
Read the full abstract

Analysis of PDEs

The "good" Boussinesq equation on the half-line: a Riemann-Hilbert approach

We consider the “good" Boussinesq equation on the half-line. Assuming existence of the solution, we prove that it can be recovered from the solution of a $3\times 3$ Riemann-Hilbert problem that depends only on the initial and boundary values, and whose jump contour consists of twelve half-lines.
Read the full abstract

Algebraic Topology

Homological algebra over non-unital rings and algebras, with applications to $(\infty, 1)$-categories

The article is developing homological algebra in modules over non-unital rings and algebras. The main application is the definition and study of (directed) homology of $(\infty,1)$-categories and of directed spaces, including relative homology and its exact sequence.

Information Theory · Cross-listed from cs.DM

Decoding universal cycles for t-subsets and t-multisets by decoding bounded-weight de Bruijn sequences

A universal cycle for a set S of combinatorial objects is a cyclic sequence of length |S| that contains a representative of each element in S exactly once as a substring. Despite the many universal cycle constructions known in the literature for various sets including k-ary strings of length n, permutations of order n, t-subsets of an n-set, and t-multisets of an n-set, remarkably few have efficient decoding (ranking/unranking) algorithms. In this paper we develop the first polynomial time/space decoding algorithms for bounded-weight de Bruijn sequences for strings of length nover an alphabet of size k. The results are then applied to decode universal cycles for t-subsets and t-multisets.
Read the full abstract

All authors Daniel Gabric, Wazed Imam, Lukas Janik Jones, Joe Sawada

Differential Geometry

Removable singularities of Yang-Mills-Higgs fields in higher dimensions

This paper establishes decay estimates near isolated singularities for $n$-dimensional Yang-Mills-Higgs fields defined on a fiber bundle ($n \geq 4$). These estimates yield a removable singularity theorem for Yang-Mills-Higgs fields under conformally invariant energy bounds, extending the classical results for Yang-Mills fields and harmonic maps.
Read the full abstract

Mathematical Physics · Cross-listed from quant-ph

Lectures on Open Quantum Systems

These notes are a short introduction to the mathematical theory of open quantum systems. They are meant to serve as an entry point into a broad research area which has applications across the quantum sciences dealing with systems subjected to external noise. The guiding idea is to let the key structures of the theory emerge from a concrete model. By working through the dissipative Jaynes-Cummings model the reader will dis- cover explicitly how irreversible dynamics arises from a unitary system-reservoir evolution. The notions of the continuous mode limit, correlation functions, spectral density appear in a natural manner and lead to the evolution equation of the open system in form of a master equation. This sets the stage for the more general analysis of completely positive, trace preserving (CPTP) maps and the study of quantum dynamical semigroups. We motivate and prove the Kraus representation theorem, the dilation theorem and the Gorini-Kossakowski-Sudarshan-Lindblad (GKSL) theorem. Working through the exercises (for which full solutions are supplied) will reinforce the ideas introduced in the main text.
Read the full abstract

Optimization and Control

Last-iterate Convergence of ADMM on Multi-affine Quadratic Equality Constrained Problem

In this paper, we study a class of non-convex optimization problems known as multi-affine quadratic equality constrained problems, which appear in various applications–from generating feasible force trajectories in robotic locomotion and manipulation to training neural networks. Although these problems are generally non-convex, they exhibit convexity or related properties when all variables except one are fixed. Under mild assumptions, we prove that the alternating direction method of multipliers (ADMM) converges when applied to this class of problems. Furthermore, when the "degree" of non-convexity in the constraints remains within certain bounds, we show that ADMM achieves a linear convergence rate. We validate our theoretical results through practical examples in robotic locomotion.
Read the full abstract

All authors Yutong Chao, Michal Ciebielski, Jalal Etesami, Majid Khadiv

Analysis of PDEs

Asymptotic behavior of large-amplitude solutions to the Boltzmann equation with soft interactions in $L^p_v L^\infty_x$ spaces

In this paper, we study the global well-posedness of the Boltzmann equation within the $L_{v}^{p}L_{x}^{\infty}$ framework for soft potential models with angular cutoff in a periodic box $\mathbb{T}^3$. By using a time-involved weight function, inspired by the works of [Liu-Yang,2017], [Duan-Yang-Zhao,2013], [Ko-Lee-Park,2022], we overcome the absence of a spectral gap. An analytical difficulty in the $L_v^p L_x^\infty$ setting is that the standard arguments used in [Ko-Lee-Park,2022], [Li,2022] for the nonlinear loss term are no longer applicable when dealing with time integration involving the collision frequency. To resolve this, we introduce a modified solution operator. Furthermore, we control the nonlinear gain term by deriving pointwise estimates bounded by $L_v^p$ and $L_v^\ell$ (for some $\ell <p$) norms. Thanks to the smallness of the initial relative entropy and Grönwall's inequality, we prove the global existence of unique solutions for large-amplitude initial data and obtain a sub-exponential convergence rate toward equilibrium.
Read the full abstract

Optimization and Control

New electric vehicle charging rate design : an MPEC assessment

A high penetration of electric vehicles (EVs) will deeply impact the management of electric power systems. To avoid costly grid reinforcements and the risk of load curtailment due to EV charging, indirect load control via adapted economic signals is a solution proposed by many utilities. Charging costs can be reduced with a domestic tariff applied only to EV charging using a dedicated load measurement method while enhancing the flexibility offered by EVs. We develop a game-theoretical model expressed and treated as a mathematical programme with equilibrium constraints (MPEC) to capture the interaction between a national regulatory authority (NRA) designing these tariffs and heterogeneous agents. First, we analyse the conditions in which EV-only tariffs can be applied for domestic slow charging sessions by comparing different energy profiles. Second, we study the impact of EV charging on different tariff structures to identify the most efficient way of recovering network costs. Submetering with a pure volumetric tariff can bring yearly gains varying from $64 to $110 compared to a flat rate. This depends on the share of investment in grid reinforcement that remains to be made. Finally, we derive policy implications from the results and earmark more sophisticated tariff designs for further investigation.
Read the full abstract

All authors Icaro Silvestre Freitas Gomes, Adam Abdin, Jakob Puchinger, Yannick Perez

Algebraic Geometry · Cross-listed from cs.CV

Single-View Rolling-Shutter SfM

Rolling-shutter (RS) cameras are ubiquitous, but RS SfM (structure-from-motion) has not been fully solved yet. This work suggests an approach to remedy this: We characterize RS single-view geometry of observed world points or lines. Exploiting this geometry, we describe which motion and scene parameters can be recovered from a single RS image and systematically derive minimal reconstruction problems. We evaluate several representative cases with proof-of-concept solvers, highlighting both feasibility and practical limitations.
Read the full abstract

All authors Sofía Errázuriz Muñoz, Kim Kiehn, Petr Hruby, Kathlén Kohn

Combinatorics

On the maximum number of tangencies among $1$-intersecting curves

According to a conjecture of Pach, there are $O(n)$ tangent pairs among any family of $n$ Jordan arcs in which every pair of arcs has precisely one common point and no three arcs share a common point. This conjecture was proved for two special cases, however, for the general case the currently best upper bound is only $O(n^{7/4})$. This is also the best known bound on the number of tangencies in the relaxed case where every pair of arcs has at most one common point. We improve the bounds for the latter and former cases to $O(n^{5/3})$ and $O(n^{3/2})$, respectively. We also consider a few other variants of these questions, for example, we show that if the arcs are \emph{$x$-monotone}, each pair intersects at most once and their left endpoints lie on a common vertical line, then the maximum number of tangencies is $\Theta(n^{4/3})$. Without this last condition the number of tangencies is $O(n^{4/3}(\log n)^{1/3})$, improving a previous bound of Pach and Sharir. Along the way we prove a graph-theoretic theorem which extends a result of Erdős and Simonovits and may be of independent interest.
Read the full abstract

Combinatorics

Finiteness of non-decomposable critically 4 and 5-frustrated signed graphs

A signed graph $(G,\sigma)$ is a graph $G$ with a signature $\sigma$ labeling each edge with a positive or negative sign. Two signatures of $G$ are switching equivalent if one is obtained from the other by changing the signs of all edges in an edge-cut. The frustration index of a signed graph $(G, \sigma)$ is the minimum number of negative edges among all signatures equivalent to $\sigma$. A signed graph is critically $k$-frustrated if it has frustration index $k$, and the removal of any edge decreases its frustration index. A critically $k$-frustrated signed graph is prime if it has no subdivided edge (including multiedge) and none of its subgraphs is the edge-disjoint union of critically frustrated signed graphs. Steffen and Naserasr et al. conjectured that for any positive integer $k$, there are finitely many prime critically $k$-frustrated signed graphs. The cases $k=1,2,3$ have been proved to be true recently by Cappello et al.. In this paper, we show that the conjecture holds when $k=4$ and $5$.
Read the full abstract