Search

An r -uniform hypergraph is a tight r-tree if its edges can be ordered so that every edge e contains a vertex v that does not belong to any preceding edge and the set e - v lies in some preceding edge. A conjecture of Kalai personal communication published in Frankl and Füredi, J. Combin. Theory Ser. A, 45 (1987), pp. 226--262, generalizing the Erdõs-Sós conjecture for trees, asserts that if T is a tight r -tree with t edge\bigr)s and G is an n-vertex r-uniform hypergraph containing no copy of T, then G has at most t--1/r(n r-i) edges. A trunk T' of a tight r-tree T is a tight subtree such that every edge of T - T' has r - 1 vertices in some edge of T' and a vertex outside T'. For r ≥ 3, the only nontrivial family of tight r-trees for which this conjecture has been proved is the family of r-trees with trunk size one in J. Combin. Theory Se r. A, 45 (1987), pp. 226--262. Our main result is an asymptotic version of Kalai's conjecture for all tight trees T of bounded trunk size. This follows from our upper bound on the size of a T-free r-uniform hypergraph G in terms of the size of its shadow. We also give a short proof of Kalai's conjecture for tight r-trees with at most four edges. In particular, for 3-uniform hypergraphs, our result on the tight path of length 4 implies the intersection shadow theorem of Katona Acta Math. Acad. Sci. Hungar., 15 (1964), pp. 329--337. [ABSTRACT FROM AUTHOR]

In this article we develop algorithms for data assimilation based upon a computational time dependent stable/unstable splitting. Our particular method is based upon shadowing refinement and synchronization techniques and is motivated by work on assimilation in the unstable subspace [Carrassi et al., Chaos, 18 (2008), 023112; Trevisan, D'Isidoro, and Talagrand, Q. J. R. Meteorol. Soc., 136 (2010), pp. 487--496; Palatella, Carrassi, and Trevisan, J. Phys. A, 46 (2013), 254020] and pseudo-orbit data assimilation [Judd and Smith, Phys. D, 151 (2001), pp. 125--141; Judd et al., J. Atmos. Sci., 65 (2008), pp. 1749--1772; Du and Smith, J. Atmos. Sci., 71 (2014), pp. 469--482]. The algorithm utilizes time dependent projections onto the nonstable subspace determined by employing computational techniques for Lyapunov exponents/vectors. The method is extended to parameter estimation without changing the problem dynamics and we address techniques for adapting the method when (as is commonly the case) observations are not available in the full model state space. We use a combination of analysis and numerical experiments (with the Lorenz 63 and Lorenz 96 models) to illustrate the efficacy of the techniques and show that the results compare favorably with other variational techniques. [ABSTRACT FROM AUTHOR]

Shadowing is a method of backward error analysis that plays a important role in hyperbolic dynamics. In this paper, the shadowing by containment framework is revisited, including a new shadowing theorem. This new theorem has several advantages with respect to existing shadowing theorems: It does not require injectivity or differentiability, and its hypothesis can be easily verified using interval arithmetic. As an application of this new theorem, shadowing by containment is shown to be applicable to infinite length orbits and is used to provide a computer assisted proof of the presence of chaos in the well-known noninjective Tinkerbell map. [ABSTRACT FROM AUTHOR]

Molecular dynamics refers to the computer simulation of a material at the atomic level. An open problem in numerical analysis is to explain the apparent reliability of molecular dynamics simulations. The difficulty is that individual trajectories computed in molecular dynamics are accurate for only short time intervals, whereas apparently reliable information can be extracted from very long-time simulations. It has been conjectured that long molecular dynamics trajectories have lowdimensional statistical features that accurately approximate those of the original system. Another conjecture is that numerical trajectories satisfy the shadowing property: they are close over long time intervals to exact trajectories but with different initial conditions. We prove that these two views are actually equivalent to each other, after we suitably modify the concept of shadowing. A key ingredient of our result is a general theorem that allows us to take random elements of a metric space that are close in distribution and embed them in the same probability space so that they are close in a strong sense. This result is similar to the Strassen-Dudley theorem except that a mapping is provided between the two random elements. Our results on shadowing are motivated by molecular dynamics but apply to the approximation of any dynamical system when initial conditions are selected according to a probability measure. [ABSTRACT FROM AUTHOR]

Numerical solutions to chaotic dynamical systems are suspect because the exponential divergence of nearby trajectories causes numerical errors to be exponentially magnified with time. To bolster confidence in the reliability of such numerical solutions, we turn to the study of shadowing: a shadow is an exact trajectory of a chaotic dynamical system that stays close to a numerical trajectory for a long time. Finding shadows of numerical trajectories is very computationally intensive, and until recently it has been infeasible to study shadows of higher-dimensional systems. This paper introduces several optimizations to previous algorithms, which collectively achieve an average speedup of almost two orders of magnitude with no measurable loss in effectiveness. We test the algorithm on systems with up to 180 dimensions. Its application to large gravitational N-body integrations has already led to a deeper understanding of the reliability of galaxy and cosmological simulations. The source code (available from the first author) provides to the experienced user a generic interface capable of searching for shadows of any set of ordinary differential equations. [ABSTRACT FROM AUTHOR]

An exact trajectory of a dynamical system lying close to a numerical trajectory is called a shadow. We present a general-purpose method for proving the existence of finite-time shadows of numerical ODE integrations of arbitrary dimension in which some measure of hyperbolicity is present and there are either 0 or 1 expanding modes, or 0 or 1 contracting modes. Much of the rigor is provided automatically by interval arithmetic and validated ODE integration software that is freely available. The method is a generalization of a previously published containment process that was applicable only to two-dimensional maps. We extend it to handle maps of arbitrary dimension with the above restrictions, and finally to ODEs. The method involves building n-cubes around each point of the discrete numerical trajectory through which the shadow is guaranteed to pass at appropriate times. The proof consists of two steps: first, the rigorous computational verification of a simple geometric property, which we call the inductive containment property, and second, a simple geometric argument showing that this property implies the existence of a shadow. The computational step is almost entirely automated and easily adaptable to any ODE problem. The method allows for the rescaling of time, which is a necessary ingredient for successfully shadowing ODEs. Finally, the method is local, in the sense that it builds the shadow inductively, requiring information only from the most recent integration step, rather than more global information typical of several other methods. The method produces shadows of comparable length and distance to all currently published results. Finally, we conjecture that the inductive containment property implies the existence of a shadow without restriction on the number of expanding and contracting modes, although proof currently eludes us. [ABSTRACT FROM AUTHOR]

Shadowing provides a means of obtaining global error bounds for approximate solutions of nonlinear differential equations with interesting dynamics, in particular, for initial value problems with positive Lyapunov exponents. Shadowing breaks down in the presence of zero Lya-punov exponents, although some results such as shadowing with rescaling of time have been obtained. Using a reformulation of the original differential equations and an improved fixed point result we take advantage of componentwise local error bounds to use relatively smaller error tolerances in nonhy-perbolic and contractive directions (i.e., in directions corresponding to zero and negative Lyapunov exponents). The result is a decrease in the shadowing global error. [ABSTRACT FROM AUTHOR]

Shadowing results for time discretizations of nonautonomous parabolic evolution equations z ′(t) = A(t)z(t) + f(t) are given. The analysis is performed in an abstract Banach space setting of uniformly sectorial operators A(t). Under natural assumptions on the operators A(t), it is shown that the backward Euler discretization of a smooth solution, obtained with constant stepsize h, is Ch-shadowed by a true solution of the system and, vice versa, every smooth trajectory is Ch-shadowed by a suitable backward Euler discretization. This validates numerical computations over long time intervals. It is further explained how these results extend to higher order Runge­Kutta methods. [ABSTRACT FROM AUTHOR]