The maximum edit distance from hereditary graph properties

For a graph property , the edit distance of a graph G from , denoted , is the minimum number of edge modifications (additions or deletions) one needs to apply to G in order to turn it into a graph satisfying . What is the largest possible edit distance of a graph on n vertices from ? Denote this distance by .A graph property is hereditary if it is closed under removal of vertices. In a previous work, the authors show that for any hereditary property, a random graph essentially achieves the maximal distance from , proving: with high probability. The proof implicitly asserts the existence of such , but it does not supply a general tool for determining its value or the edit distance.In this paper, we determine the values of and for some subfamilies of hereditary properties including sparse hereditary properties, complement invariant properties, (r,s)-colorability and more. We provide methods for analyzing the maximum edit distance from the graph properties of being induced H-free for some graphs H, and use it to show that in some natural cases G(n,1/2) is not the furthest graph. Throughout the paper, the various tools let us deduce the asymptotic maximum edit distance from some well studied hereditary graph properties, such as being Perfect, Chordal, Interval, Permutation, Claw-Free, Cograph and more. We also determine the edit distance of G(n,1/2) from any hereditary property, and investigate the behavior of as a function of p.The proofs combine several tools in Extremal Graph Theory, including strengthened versions of the Szemerédi Regularity Lemma, Ramsey Theory and properties of random graphs.     

The Abel Lemma and the -Gosper Algorithm

Chu has recently shown that the Abel lemma on summation by parts reveals the telescoping nature of Bailey's bilateral summation formula. We present a systematic approach to compute Abel pairs for bilateral and unilateral basic hypergeometric summation formulas by using the -Gosper algorithm. It is demonstrated that Abel pairs can be derived from Gosper pairs. This approach applies to many classical summation formulas.

     

The noncommutative Wiener lemma, linear independence, and spectral properties of the algebra of time-frequency shift operators

In this paper we analyze the Banach *-algebra of time-frequency shifts with absolutely summable coefficients. We prove a noncommutative version of the Wiener lemma. We also construct a faithful tracial state on this algebra which proves the algebra contains no compact operators. As a corollary we obtain a special case of the Heil-Ramanathan-Topiwala conjecture regarding linear independence of finitely many time-frequency shifts of one function. We also estimate the coefficient decay of the inverse of finite linear combinations of time-frequency shifts.

     

Twisted cubic theta hypergeometric series

The modified Abel lemma on summation by parts is employed to examine the “twisted” cubic theta hypergeometric series through three appropriately devised difference pairs. Several remarkable summation and transformation formulae are established. The associated reversal series are also evaluated in closed forms, that extend significantly the corresponding q‐series identities.     

The Pohozaev-Schoen identity on asymptotically Euclidean manifolds: Conservation laws and their applications

The aim of this paper is to present a version of the generalized Pohozaev-Schoen identity in the context of asymptotically Euclidean manifolds. Since these kind of geometric identities have proven to be a very powerful tool when analysing different geometric problems for compact manifolds, we will present a variety of applications within this new context. Among these applications, we will show some rigidity results for asymptotically Euclidean Ricci-solitons and Codazzi-solitons. Also, we will present an almost-Schur type inequality valid in this non-compact setting which does not need restrictions on the Ricci curvature. Finally, we will show how some rigidity results related with static potentials also follow from these type of conservation principles.     

Convergence of random series and the rate of convergence of the strong law of large numbers in game-theoretic probability

We give a unified treatment of the convergence of random series and the rate of convergence of the strong law of large numbers in the framework of game-theoretic probability of Shafer and Vovk (2001) [24]. We consider games with the quadratic hedge as well as more general weaker hedges. The latter corresponds to the existence of an absolute moment of order smaller than 2 in the measure-theoretic framework. We prove some precise relations between the convergence of centered random series and the convergence of the series of prices of the hedges. When interpreted in the measure-theoretic framework, these results characterize the convergence of a martingale in terms of the convergence of the series of conditional absolute moments. In order to prove these results we derive some fundamental results on deterministic strategies of Reality, who is a player in a protocol of game-theoretic probability. It is of particular interest, since Reality’s strategies do not have any counterparts in the measure-theoretic framework, ant yet they can be used to prove results which can be interpreted in the measure-theoretic framework.     

On a characteristic equation of well-poised Bailey chains

In this paper, we find by inverse technique two solutions of a system of linear equations which together serve as a sufficient and necessary condition for well-poised Bailey chains. Using these two solutions, we establish a new well-poised Bailey chain, two usual Bailey chains, and a well-poised extension of Bailey’s lemma. Their applications to q-series are also investigated. X. Ma was supported by Natural Science Foundation of China (No. 10771156).     

Rademacher complexity in Neyman-Pearson classification

Neyman-Pearson（NP） criterion is one of the most important ways in hypothesis testing. It is also a criterion for classification. This paper addresses the problem of bounding the estimation error of NP classification, in terms of Rademacher averages. We investigate the behavior of the global and local Rademacher averages, and present new NP classification error bounds which are based on the localized averages, and indicate how the estimation error can be estimated without a priori knowledge of the class at hand.