More Like this

1. What is the graph of a dynamical system?

   https://doi.org/10.1007/s11071-025-11466-9  

   Adwani, Chirag; De_Leo, Roberto; Yorke, James (July 2025, Nonlinear Dynamics)

   Some of the basic properties of any dynamical system can be summarized by a graph. The dynamical systems in our theory run from maps like the logistic map to ordinary differential equations to dissipative partial differential equations. Our goal has been to define a meaningful concept of graph of any dynamical system. As a result, we base our definition of “chain graph” on “epsilon-chains”, defining both nodes and edges of the graph in terms of chains. In particular, nodes are often maximal limit sets and there is an edge between two nodes if there is a trajectory whose forward limit set is in one node and its backward limit set is in the other. Our initial goal was to prove that every “chain graph” of a dynamical system is, in some sense, connected, and we prove connectedness under mild hypotheses. 

   more » « less
2. Skew and sphere fibrations

   https://doi.org/10.1090/tran/8953  

   Harrison, Michael (July 2023, Transactions of the American Mathematical Society)

   A great sphere fibration is a sphere bundle with total space S n S^n and fibers which are great k k -spheres. Given a smooth great sphere fibration, the central projection to any tangent hyperplane yields a nondegenerate fibration of R n \mathbb {R}^n by pairwise skew, affine copies of R k \mathbb {R}^k (though not all nondegenerate fibrations can arise in this way). Here we study the topology and geometry of nondegenerate fibrations, we show that every nondegenerate fibration satisfies a notion of Continuity at Infinity, and we prove several classification results. These results allow us to determine, in certain dimensions, precisely which nondegenerate fibrations correspond to great sphere fibrations via the central projection. We use this correspondence to reprove a number of recent results about sphere fibrations in the simpler, more explicit setting of nondegenerate fibrations. For example, we show that every germ of a nondegenerate fibration extends to a global fibration, and we study the relationship between nondegenerate line fibrations and contact structures in odd-dimensional Euclidean space. We conclude with a number of partial results, in hopes that the continued study of nondegenerate fibrations, together with their correspondence with sphere fibrations, will yield new insights towards the unsolved classification problems for sphere fibrations. 

   more » « less
3. Hardness of approximation in p via short cycle removal: cycle detection, distance oracles, and beyond

   https://doi.org/10.1145/3519935.3520066  

   Abboud, Amir; Bringmann, Karl; Khoury, Seri; Zamir, Or (June 2022, STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing)

   We present a new technique for efficiently removing almost all short cycles in a graph without unintentionally removing its triangles. Consequently, triangle finding problems do not become easy even in almost k-cycle free graphs, for any constant k≥ 4. Triangle finding is at the base of many conditional lower bounds in P, mainly for distance computation problems, and the existence of many 4- or 5-cycles in a worst-case instance had been the obstacle towards resolving major open questions. Hardness of approximation: Are there distance oracles with m1+o(1) preprocessing time and mo(1) query time that achieve a constant approximation? Existing algorithms with such desirable time bounds only achieve super-constant approximation factors, while only 3− factors were conditionally ruled out (Pătraşcu, Roditty, and Thorup; FOCS 2012). We prove that no O(1) approximations are possible, assuming the 3-SUM or APSP conjectures. In particular, we prove that k-approximations require Ω(m1+1/ck) time, which is tight up to the constant c. The lower bound holds even for the offline version where we are given the queries in advance, and extends to other problems such as dynamic shortest paths. The 4-Cycle problem: An infamous open question in fine-grained complexity is to establish any surprising consequences from a subquadratic or even linear-time algorithm for detecting a 4-cycle in a graph. This is arguably one of the simplest problems without a near-linear time algorithm nor a conditional lower bound. We prove that Ω(m1.1194) time is needed for k-cycle detection for all k≥ 4, unless we can detect a triangle in √n-degree graphs in O(n2−δ) time; a breakthrough that is not known to follow even from optimal matrix multiplication algorithms. 

   more » « less
4. Rainbow even cycles

   Dong, Zichao; Xu, Zijian (April 2024, SIAM journal on discrete mathematics)

   We prove that every family of (not necessarily distinct) even cycles D_1,...,D_{1.2n-1} on some fixed n-vertex set has a rainbow even cycle (that is, a set of edges from distinct D_i’s, forming an even cycle). This resolves an open problem of Aharoni, Briggs, Holzman and Jiang. Moreover, the result is best possible for every positive integer n. 

   more » « less
5. Page curves and typical entanglement in linear optics

   https://doi.org/10.22331/q-2023-05-23-1017  

   Iosue, Joseph T.; Ehrenberg, Adam; Hangleiter, Dominik; Deshpande, Abhinav; Gorshkov, Alexey V. (May 2023, Quantum)

   Bosonic Gaussian states are a special class of quantum states in an infinite dimensional Hilbert space that are relevant to universal continuous-variable quantum computation as well as to near-term quantum sampling tasks such as Gaussian Boson Sampling. In this work, we study entanglement within a set of squeezed modes that have been evolved by a random linear optical unitary. We first derive formulas that are asymptotically exact in the number of modes for the Rényi-2 Page curve (the average Rényi-2 entropy of a subsystem of a pure bosonic Gaussian state) and the corresponding Page correction (the average information of the subsystem) in certain squeezing regimes. We then prove various results on the typicality of entanglement as measured by the Rényi-2 entropy by studying its variance. Using the aforementioned results for the Rényi-2 entropy, we upper and lower bound the von Neumann entropy Page curve and prove certain regimes of entanglement typicality as measured by the von Neumann entropy. Our main proofs make use of a symmetry property obeyed by the average and the variance of the entropy that dramatically simplifies the averaging over unitaries. In this light, we propose future research directions where this symmetry might also be exploited. We conclude by discussing potential applications of our results and their generalizations to Gaussian Boson Sampling and to illuminating the relationship between entanglement and computational complexity. 

   more » « less