arXiv Math @arxiv_math@qoto.org

Colloquially, there are two groups, $n$ men and $n$ women, each man (woman) ranking women (men) as potential marriage partners. A complete matching is called stable if no unmatched pair prefer each other to their partners in the matching. If some pairs are not admissible, then such a matching may not exist, but a properly defined partial stable matching exists always, and all such matchings involve the same, equi-numerous, groups of men and women. Earlier we proved that, for the complete, random, preference lists, with high probability (whp) the total number of complete stable matchings is, roughly, of order $n^{1/2}$, at least. Here we consider the case that the preference lists are still complete, but a generic pair (man,woman) is admissible with probability $p$, independently of all other $n^2-1$ pairs. It is shown that the expected number of complete stable matchings tends to $0$ if, roughly, $p<\tfrac{\log^2 n}{n}$ and to infinity if $p>\tfrac{\log^2 n}{n}$. We show that whp: (a) there exists a complete stable matching if $p>(9/4)\tfrac{\log^2 n}{n}$, (b) the number of unmatched men and women is bounded if $p> \tfrac{\log^2n}{n}$, and (c) this number grows as a fractional power of $n$ for $p<\tfrac{\log^2 n}{n}$.

We investigate Markovian lifts of stochastic Volterra equations (SVEs) with completely monotone kernels and general coefficients within a class of weighted Sobolev spaces. Our primary focus is developing a comprehensive solution theory for a class of non-local stochastic evolution equations (SEEs) encompassing these Markovian lifts. This enables us to provide conditions for the existence of invariant measures for the lifted processes and the corresponding SVE. Another key contribution is an Ito-type formula for the stochastic Volterra equations under consideration.

The theory of products of random matrices and Lyapunov exponents have been widely studied and applied in the fields of biology, dynamical systems, economics, engineering and statistical physics. We consider the product of an i.i.d. sequence of $2\times 2$ random non-invertible matrices with real entries. Given some mild moment assumptions we prove an explicit formula for the Lyapunov exponent and prove a central limit theorem with an explicit formula for the variance in terms of the entries of the matrices. We also give examples where exact values for the Lyapunov exponent and variance are computed. An important example where non-invertible matrices are essential is the random Hill's equation, which has numerous physical applications, including the astrophysical orbit problem.

We prove that every nontrivial principal $G_m$-bundle over a complete uniformly rational variety is algebraically elliptic in the sense of Gromov.

We determine the set of polynomials $f(x)\in k[x]$, where $k$ is a finite field, such that the local system on $\mathbb G_m^2$ which parametrizes the family of exponential sums $(s,t)\mapsto\sum_{x\in k}ψ(sf(x)+tx)$ has finite monodromy, in two cases: when $f(x)=x^d+λx^e$ is a binomial and when $f(x)=(x-α)^d(x-β)^e$ is of Belyi type.

This paper presents a new method for enhancing Alternating Current Power Flow (ACPF) analysis. The method integrates the Newton-Raphson (NR) method with Enhanced-Gradient Descent (GD) and computational graphs. The integration of renewable energy sources in power systems introduces variability and unpredictability, and this method addresses these challenges. It leverages the robustness of NR for accurate approximations and the flexibility of GD for handling variable conditions, all without requiring Jacobian matrix inversion. Furthermore, computational graphs provide a structured and visual framework that simplifies and systematizes the application of these methods. The goal of this fusion is to overcome the limitations of traditional ACPF methods and improve the resilience, adaptability, and efficiency of modern power grid analyses. We validate the effectiveness of our advanced algorithm through comprehensive testing on established IEEE benchmark systems. Our findings demonstrate that our approach not only speeds up the convergence process but also ensures consistent performance across diverse system states, representing a significant advancement in power flow computation.

Let $H$ be a nonabelian finite simple group. Huppert's conjecture asserts that if $G$ is a finite group with the same set of complex character degrees as $H$, then $G\cong H\times A$ for some abelian group $A$. Over the past two decades, several specific cases of this conjecture have been addressed. Recently, attention has shifted to the analogous conjecture for character codegrees: if $G$ has the same set of character codegrees as $H$, then $G\cong H$. Unfortunately, both problems have primarily been examined on a case-by-case basis. In this paper and the companion [HM22], we present a more unified approach to the codegree conjecture and confirm it for several families of simple groups.

Suppose $k,x,$ and $b$ are positive integers, and $a$ is a nonnegative integer such that $k=a+b$. In this paper, we will prove $\binom{2k}{k} = \binom{2a}{a} \binom{x+2b}{b}$ if and only if $x=a=1$. We do this by looking at different cases depending on the values of $x$ and $k$. We use varying techniques to prove the cases, such as direct proof, verification through Maple software, and a proof technique found in Moser's paper. Previous results from Hanson, Stănică, Shanta, Shorey and Nair are also used.

This book is devoted to finite-dimensional problems of non-convex non-smooth optimization and numerical methods for their solution. The problem of nonconvexity is studied in the book on two main models of nonconvex dependencies: these are the so-called generalized differentiable functions and locally Lipschitz functions. Non-smooth functions naturally arise in various applications. In addition, they often appear in the theory of extremal problems itself due to the operations of taking the maximum and minimum, decomposition techniques, exact non-smooth penalties, and duality. The considered models of nonconvexity are quite general and cover the majority of practically important optimization problems; they clearly show all the difficulties of non-convex optimization. The method of studying the generalized differentiable functions is that for these functions a generalization of the concept of gradient is introduced, a calculus is constructed, and various properties of nonconvex problems are studied in terms of generalized gradients. As for numerical methods, it is possible to extend the theory and algorithms of subgradient descent of convex optimization to problems with generalized differentiable functions. Methods for solving Lipschitz problems are characterized by the fact that the original functions are approximated by smoothed ones and iterative minimization procedures are applied to them. With this approach, it is possible to approximate the gradients of smoothed functions by stochastic finite differences and thus to construct methods without calculating gradients. A similar approach can be justified in generalized differentiable and Lipschitz stochastic programming. In these cases, various generalizations of the classical stochastic approximation and stochastic quasi-gradient method are obtained for solving constrained nonconvex nonsmooth stochastic programming problems.

Semidefinite programs (SDPs) and their solvers are powerful tools with many applications in machine learning and data science. Designing scalable SDP solvers is challenging because by standard the positive semidefinite decision variable is an $n \times n$ dense matrix, even though the input is often an $n \times n$ sparse matrix. However, the information in the solution may not correspond to a full-rank dense matrix as shown by Bavinok and Pataki. Two decades ago, Burer and Monterio developed an SDP solver $\texttt{SDPLR}$ that optimizes over a low-rank factorization instead of the full matrix. This greatly decreases the storage cost and works well for many problems. The original solver $\texttt{SDPLR}$ tracks only the primal infeasibility of the solution, limiting the technique's flexibility to produce moderate accuracy solutions. We use a suboptimality bound for trace-bounded SDP problems that enables us to track the progress better and perform early termination. We then develop $\texttt{SDPLR+}$, which starts the optimization with an extremely low-rank factorization and dynamically updates the rank based on the primal infeasibility and suboptimality. This further speeds up the computation and saves the storage cost. Numerical experiments on Max Cut, Minimum Bisection, Cut Norm, and Lovász Theta problems with many recent memory-efficient scalable SDP solvers demonstrate its scalability up to problems with million-by-million decision variables and it is often the fastest solver to a moderate accuracy of $10^{-2}$.

We prove that the following statements are equivalent: a linear matrix equation with parameters forming a commuting set of diagonalizable matrices is consistent, a certain matrix constructed with the Drazin inverse is a solution of this matrix equation, the attached standard linear matrix equation is consistent. The number of zero components of a given matrix (the relevant matrix) gives us the dimension of the affine space of solutions. We apply this theoretical results to the Sylvester equation, the Stein equation, and the Lyapunov equation. We present a description of the set of the diagonalizing matrices for a commuting sequence of diagonalizable matrices.

The computation of matrix functions is a well-studied problem. Of special importance are the exponential and the logarithm of a matrix, where the latter also raises existence and uniqueness questions. This is particularly relevant in the context of matrix semigroups and their generators. Here, we look at matrix functions of triangular matrices, where a recursive approach is possible when the matrix has simple spectrum. The special feature is that no knowledge of eigenvectors is required, and that the same recursion applies to the computation of multiple functions or semigroups simultaneously.

Charney and Morris-Wright showed acylindrical hyperbolicity of Artin groups of infinite type associated with graphs that are not joins, by studying clique-cube complexes and the actions on them. The authors developed their study and clarified when acylindrical hyperbolicity holds for Artin groups of infinite type associated with graphs that are not cones. In this paper, we introduce reduced clique-cube complexes. By using them, we show acylindrical hyperbolicity of irreducible Artin groups associated with graphs that are not cliques, that is, irreducible Artin groups that are not free of infinity. Such Artin groups contain infinite type Artin groups of type FC. As an application, we see that the centers of such Artin groups are finite, and that actually they are trivial in many cases.

The classical Sarkisov Program aims to decompose the induced birational map between any two Mori fiber spaces obtained as end results of different minimal model program ( starting from same projective variety ), in terms of finitely many Sarkisov links. In this article we prove the Sarkisov Program for co-rank one foliation with suitable singularities on normal projective threefolds. We also relate two foliated Mori fiber spaces with rank one foliations on normal projective threeefolds in the spirit of Sarkisov Program.

We consider the long-time dynamics of focusing energy-critical Schrödinger equation perturbed by the $\dot{H}^\frac{1}{2}$-critical nonlinearity and with inverse-square potential(CNLS$_a$) in dimensions $d\in\{3,4,5\}$ \begin{equation}\label{NLS-ab} \begin{cases} i\partial_tu-\mathcal{L}_au=-|u|^{\frac{4}{d-2}}u+|u|^{\frac{4}{d-1}}u, \quad (t,x)\in\mathbb{R}\times\mathbb{R}^d,\tag{CNLS$_a$},\\ u(0,x)=u_0(x)\in H^1_a(\mathbb{R}^d), \end{cases} \end{equation} where $\mathcal{L}_a=-Δ+a|x|^{-2}$ and the energy is below and equal to the threshold $m_a$, which is given by the ground state $W_a$ satisfying $\mathcal{L}_aW_a=|W_a|^{\frac{4}{d-2}}W_a$. When the energy is below the threshold, we utilize the concentration-compactness argument as well as the variatonal analysis to characterize the scattering and blow-up region. When the energy is equal to the threshold, we use the modulation analysis associated to the equation \eqref{NLS-ab} to classify the dynamics of $H_a^1$-solution. In both regimes of scattering results, we do not need the radial assumption in $d=4,5$. Our result generalizes the scattering results of [31-33] and [3] in the setting of standard combined NLS.

Generic polyhedra are interesting mathematical objects to study in their own right. In this paper, we initialize a systematic study of two-dimensional generic polyhedra with an eye towards applications to low-dimensional topology, especially the Andrews-Curtis and Zeeman conjectures. After recalling the basic notions of generic polyhedra and fake surfaces, we derive some interesting properties of fake surfaces. Our main result is a complete classification of acyclic cellular fake surfaces up to complexity 4 and a classification of acyclic cellular fake surfaces without small disks of complexity 5. From this classification, we prove the contractibility conjecture for acyclic cellular fake surfaces of complexity 4, and the embedded disk conjecture up to complexity 5. We provide evidence for the conjectures that the probability of being a spine among fake surfaces is 0 and that every contractible fake surface has an embedded disk.

In recent years, the use of data-driven methods has provided insights into underlying patterns and principles behind culinary recipes. In this exploratory work, we introduce the use of topological data analysis, especially persistent homology, in order to study the space of culinary recipes. In particular, persistent homology analysis provides a set of recipes surrounding the multiscale "holes" in the space of existing recipes. We then propose a method to generate novel ingredient combinations using combinatorial optimization on this topological information. We made biscuits using the novel ingredient combinations, which were confirmed to be acceptable enough by a sensory evaluation study. Our findings indicate that topological data analysis has the potential for providing new tools and insights in the study of culinary recipes.

Wireless devices can be easily attacked by jammers during transmission, which is a potential security threat for wireless communications. Active reconfigurable intelligent surface (RIS) attracts considerable attention and is expected to be employed in anti-jamming systems for secure transmission to significantly enhance the anti-jamming performance. However, active RIS introduces external power load, which increases the complexity of hardware and restricts the flexible deployment of active RIS. To overcome these drawbacks, we design a innovative self-sustainable structure in this paper, where the active RIS is energized by harvesting energy from base station (BS) signals through the time dividing based simultaneous wireless information and power transfer (TD-SWIPT) scheme. Based on the above structure, we develop the BS harvesting scheme based on joint transmit and reflecting beamforming with the aim of maximizing the achievable rate of active RIS-assisted system, where the alternating optimization (AO) algorithm based on stochastic successive convex approximation (SSCA) tackles the nonconvex optimization problem in the scheme. Simulation results verified the effectiveness of our developed BS harvesting scheme, which can attain higher anti-jamming performance than other schemes when given the same maximum transmit power.

The famous Christoffel problem is possibly the oldest problem of prescribed curvatures for convex hypersurfaces in Euclidean space. Recently, this problem has been naturally formulated in the context of uniformly $h$-convex hypersurfaces in hyperbolic space by Espinar-Gálvez-Mira. Surprisingly, Espinar-Gálvez-Mira find that the Christoffel problem in hyperbolic space is essentially equivalent to the Nirenberg-Kazdan-Warner problem on prescribing scalar curvature on $\mathbb{S}^n$. This equivalence opens a new door to study the Nirenberg-Kazdan-Warner problem. In this paper, we establish a existence of solutions to the Christoffel problem in hyperbolic space by proving a full rank theorem. As a corollary, a existence of solutions to the Nirenberg-Kazdan-Warner problem follows.

Inverse optimization has received much attention in recent years, but little literature exists for solving generalized mixed integer inverse optimization. We propose a new approach for solving generalized mixed-integer inverse optimization problems based on sub-gradient methods. We characterize when a generalized inverse optimization problem can be solved using sub-gradient methods and we prove that modifications to classic sub-gradient algorithms can return exact solutions in finite time. Our best implementation improves solution time by up to 90% compared to the best performing method from the literature. We then develop custom heuristic methods for graph-based inverse problems using a combination of graph coarsening and ensemble methods. Our heuristics are able to further reduce solution time by up to 52%, while still producing near-optimal solutions. Finally, we propose a new application domain - quantitatively identifying gerrymandering - for generalized inverse integer optimization. We apply our overall solution approach to analyze the congressional districts of the State of Iowa using real-world data. We find that the accepted districting marginally improves population imbalance at the cost of a significant increase in partisan efficiency gap. We argue that our approach can produce a more nuanced data-driven argument that a proposed districting should be considered gerrymandered.