254 results
Search Results
2. Proof of the Achievability Conjectures for the General Stochastic Block Model
- Author
-
Emmanuel Abbe and Colin Sandon
- Subjects
Discrete mathematics ,Conjecture ,Applied Mathematics ,General Mathematics ,020206 networking & telecommunications ,02 engineering and technology ,Belief propagation ,01 natural sciences ,Algebra ,010104 statistics & probability ,Operator (computer programming) ,Power iteration ,Stochastic block model ,0202 electrical engineering, electronic engineering, information engineering ,Order (group theory) ,0101 mathematics ,Cluster analysis ,Time complexity ,Mathematics - Abstract
In a paper that initiated the modern study of the stochastic block model (SBM), Decelle, Krzakala, Moore, and Zdeborova, backed by Mossel, Neeman, and Sly, conjectured that detecting clusters in the symmetric SBM in polynomial time is always possible above the Kesten-Stigum (KS) threshold, while it is possible to detect clusters information theoretically (i.e., not necessarily in polynomial time) below the KS threshold when the number of clusters k is at least 4. Massoulie, Mossel et al., and Bordenave, Lelarge, and Massoulie proved that the KS threshold is in fact efficiently achievable for k = 2, while Mossel et al. proved that it cannot be crossed at k = 2. The above conjecture remained open for k ≥ 3. This paper proves the two parts of the conjecture, further extending the results to general SBMs. For the efficient part, an approximate acyclic belief propagation (ABP) algorithm is developed and proved to detect communities for any k down to the KS threshold in quasi-linear time. Achieving this requires showing optimality of ABP in the presence of cycles, a challenge for message-passing algorithms. The paper further connects ABP to a power iteration method on a nonbacktracking operator of generalized order, formalizing the interplay between message passing and spectral methods. For the information-theoretic part, a nonefficient algorithm sampling a typical clustering is shown to break down the KS threshold at k = 4. The emerging gap is shown to be large in some cases, making the SBM a good case study for information-computation gaps. © 2017 Wiley Periodicals, Inc.
- Published
- 2017
3. How does the core sit inside the mantle?
- Author
-
Kathrin Skubch, Mihyun Kang, Oliver Cooley, and Amin Coja-Oghlan
- Subjects
FOS: Computer and information sciences ,Discrete Mathematics (cs.DM) ,General Mathematics ,05C80 ,Structure (category theory) ,0102 computer and information sciences ,Characterization (mathematics) ,01 natural sciences ,Mantle (geology) ,Combinatorics ,010104 statistics & probability ,FOS: Mathematics ,Discrete Mathematics and Combinatorics ,Mathematics - Combinatorics ,0101 mathematics ,Mathematics ,Branching process ,Discrete mathematics ,Random graph ,Series (mathematics) ,Degree (graph theory) ,Applied Mathematics ,Probability (math.PR) ,Computer Graphics and Computer-Aided Design ,Tree (graph theory) ,Vertex (geometry) ,010201 computation theory & mathematics ,Bounded function ,Core (graph theory) ,Combinatorics (math.CO) ,Combinatorial theory ,Mathematics - Probability ,Software ,Computer Science - Discrete Mathematics - Abstract
The k-core, defined as the maximal subgraph of minimum degree at least k, of the random graph G(n,p) has been studied extensively. In a landmark paper Pittel, Wormald and Spencer [J Combin Theory Ser B 67 (1996), 111–151] determined the threshold dk for the appearance of an extensive k-core. The aim of the present paper is to describe how the k-core is “embedded” into the random graph in the following sense. Let k≥3 and fix d=np>dk. Colour each vertex that belongs to the k-core of G(n,p) in black and all remaining vertices in white. Here we derive a multi-type branching process that describes the local structure of this coloured random object as n tends to infinity. This generalises prior results on, e.g., the internal structure of the k-core. In the physics literature it was suggested to characterize the core by means of a message passing algorithm called Warning Propagation. Ibrahimi, Kanoria, Kraning and Montanari [Ann Appl Probab 25 (2015), 2743–2808] used this characterization to describe the 2-core of random hypergraphs. To derive our main result we use a similar approach. A key observation is that a bounded number of iterations of this algorithm is enough to give a good approximation of the k-core. Based on this the study of the k-core reduces to the analysis of Warning Propagation on a suitable Galton-Watson tree. © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 00, 000–000, 2017
- Published
- 2017
4. A generalized theorem of Reichert for biquadratic minimum functions
- Author
-
Yun Zou, Kai Wang, and Michael Z. Q. Chen
- Subjects
Discrete mathematics ,0209 industrial biotechnology ,Series (mathematics) ,Applied Mathematics ,020208 electrical & electronic engineering ,Minimum function ,02 engineering and technology ,Computer Science Applications ,Electronic, Optical and Magnetic Materials ,law.invention ,020901 industrial engineering & automation ,law ,0202 electrical engineering, electronic engineering, information engineering ,Inerter ,RLC circuit ,Electrical and Electronic Engineering ,Resistor ,Electrical impedance ,Mathematics - Abstract
This paper is concerned with a generalized theorem of Reichert for biquadratic minimum functions, which states that any biquadratic minimum function realizable as the impedance of networks with n reactive elements and an arbitrary number of resistors can be realized with n reactive elements and two resistors. First, a series of constraints on networks realizing minimum functions are presented. Furthermore, by discussing the possible resistor edges incident with vertices of the reactive-element graphs, it is proved that any minimum function realizable as the impedance of networks with three reactive elements and an arbitrary number of resistors can be realized with three reactive elements and two resistors, from which the validity of the case of n=3 follows. Similarly, the validity of the case of n=4 is proved. Together with the Bott-Duffin realizations, the generalized theorem of Reichert for biquadratic minimum functions is finally proved. The results of this paper are motivated by passive mechanical control. Copyright © 2016 John Wiley & Sons, Ltd.
- Published
- 2016
5. On generalized Borgen plots. I: From convex to affine combinations and applications to spectral dataSpectra
- Author
-
Klaus Neymeyr, Annekathrin Jürß, and Mathias Sawall
- Subjects
Discrete mathematics ,Applied Mathematics ,Numerical analysis ,Computation ,Regular polygon ,Contrast (statistics) ,Affine transformation ,Spectral data ,Analytical Chemistry ,Mathematics ,Non-negative matrix factorization - Abstract
In 1985, Borgen and Kowalski (Anal. Chim. Acta 1985; 174: 1-26) published their landmark paper on the geometric construction of feasible regions for nonnegative factorizations of spectral data matrices for three-component systems. These geometric constructions are called Borgen plots. Borgen plots are principally restricted to nonnegative data and are sometimes considered as analytical tool. Major contributions to this theory have been given by Rajko. In contrast to these geometric constructions, numerical methods to compute the so-called area of feasible solutions (AFS) have been studied by Golshan et al. (Anal. Chem. 2011; 83 (3): 836-841) and by Sawall et al. (J. Chemom. 2013; 27: 106-116). These numerical methods can even treat spectral data, which include slightly negative components. In this work, the concept of generalized Borgen plots is introduced for spectral data, which are polluted by small negative entries. The analysis is not restricted to three-component systems but can be applied to general s-component systems. Generalized Borgen plots are identical to the classical Borgen plots for nonnegative data. The analysis in this work also bridges the gap between the different scalings (Borgen norms) used for AFS computations. The algorithmic procedure of generalized Borgen plots for three-component systems and its implementation in the FAC-PACK software are described in the second part of this paper. Copyright © 2015 John Wiley & Sons, Ltd.
- Published
- 2015
6. Meyniel's conjecture holds for random graphs
- Author
-
Nicholas C. Wormald and Paweł Prałat
- Subjects
Random graph ,Discrete mathematics ,Conjecture ,Applied Mathematics ,General Mathematics ,010102 general mathematics ,0102 computer and information sciences ,16. Peace & justice ,01 natural sciences ,Computer Graphics and Computer-Aided Design ,Graph ,Combinatorics ,010201 computation theory & mathematics ,Random regular graph ,Almost surely ,0101 mathematics ,Absolute constant ,Software ,Connectivity ,Mathematics - Abstract
In the game of cops and robber, the cops try to capture a robber moving on the vertices of the graph. The minimum number of cops required to win on a given graph G is called the cop number of G. The biggest open conjecture in this area is the one of Meyniel, which asserts that for some absolute constant C, the cop number of every connected graph G is at most C|VG|. In this paper, we show that Meyniel's conjecture holds asymptotically almost surely for the binomial random graph Gn,p, which improves upon existing results showing that asymptotically almost surely the cop number of Gn,p is Onlogn provided that pni¾?2+elogn for some e>0. We do this by first showing that the conjecture holds for a general class of graphs with some specific expansion-type properties. This will also be used in a separate paper on random d-regular graphs, where we show that the conjecture holds asymptotically almost surely when d=dni¾?3. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 396-421, 2016
- Published
- 2015
7. An Elementary Derivation of the Large Deviation Rate Function for Finite State Markov Chains
- Author
-
Mathukumalli Vidyasagar
- Subjects
Discrete mathematics ,Markov kernel ,Markov chain mixing time ,Markov chain ,Markov process ,Markov model ,Continuous-time Markov chain ,symbols.namesake ,Mathematics (miscellaneous) ,Control and Systems Engineering ,Markov renewal process ,symbols ,Applied mathematics ,Markov property ,Electrical and Electronic Engineering ,Mathematics - Abstract
Large deviation theory is a branch of probability theory that is devoted to a study of the “rate” at which empirical estimates of various quantities converge to their true values. The object of study in this paper is the rate at which estimates of the doublet frequencies of a Markov chain over a finite alphabet converge to their true values. In the case where the Markov process is actually an independent and identically distributed (i.i.d.) process, the rate function turns out to be the relative entropy (or Kullback-Leibler divergence) between the true and the estimated probability vectors. This result is a special case of a very general result known as Sanov's theorem and dates back to 1957. Moreover, since the introduction of the “method of types” by Csiszar and his co-workers during the 1980s, the Proof of this version of Sanov's theorem has been “elementary,” using some combinatorial arguments. However, when the i.i.d. process is replaced by a Markov process, the available Proofs are far more complex. The main objective of this paper is therefore to present a first-principles derivation of the LDP for finite state Markov chains, using only simple combinatorial arguments (e.g. the method of types), thus gathering in one place various arguments and estimates that are scattered over the literature. The approach presented here extends naturally to multi-step Markov chains.
- Published
- 2013
8. The bounds of the eigenvalues for rank-one modification of Hermitian matrix
- Author
-
Jia Si, Jianfeng Yang, Zhida Song, and Guanghui Cheng
- Subjects
Combinatorics ,Discrete mathematics ,Matrix differential equation ,Matrix (mathematics) ,Algebra and Number Theory ,Tridiagonal matrix ,Applied Mathematics ,Matrix function ,Positive-definite matrix ,Hermitian matrix ,Eigendecomposition of a matrix ,Eigenvalues and eigenvectors ,Mathematics - Abstract
The eigenproblems of the rank-one updates of the matrices have lots of applications in scientific computation and engineering such as the symmetric tridiagonal eigenproblems by the divide-andconquer method and Web search engine. Many researchers have well studied the algorithms for computing eigenvalues of Hermitian matrices updated by a rank-one matrix [1–6]. Recently, Ding and Zhou studied a spectral perturbation theorem for rank-one updated matrices of special structure in [7] and considered two applications. Cheng, Luo, and Li considered the bounds of the smallest and largest eigenvalues for rank-one modification of Hermitian matrices [8]. Eigenvalue bounds for perturbations of Hermitian matrices have been considered by Ipsen and Nadler in [9]. In this paper, we consider the bounds of the eigenvalues for rank-one modification of Hermitian matrices. The ideas of this paper were mainly motivated by one of [9]. We study the following form
- Published
- 2013
9. Degenerate random environments
- Author
-
Thomas S. Salisbury and Mark Holmes
- Subjects
Random graph ,Discrete mathematics ,Percolation critical exponents ,Random field ,Applied Mathematics ,General Mathematics ,Probability (math.PR) ,010102 general mathematics ,Random function ,Random element ,01 natural sciences ,Computer Graphics and Computer-Aided Design ,Directed percolation ,Combinatorics ,010104 statistics & probability ,FOS: Mathematics ,Random compact set ,Continuum percolation theory ,0101 mathematics ,Mathematics - Probability ,Software ,Mathematics - Abstract
We consider connectivity properties of certain i.i.d. random environments on i¾?d, where at each location some steps may not be available. Site percolation and oriented percolation are examples of such environments. In these models, one of the quantities most often studied is the random set of vertices that can be reached from the origin by following a connected path. More generally, for the models we consider, multiple different types of connectivity are of interest, including: the set of vertices that can be reached from the origin; the set of vertices from which the origin can be reached; the intersection of the two. As with percolation models, many of the models we consider admit, or are expected to admit phase transitions. Among the main results of the paper is a proof of the existence of phase transitions for some two-dimensional models that are non-monotone in their underlying parameter, and an improved bound on the critical value for oriented site percolation on the triangular lattice. The connectivity of the random directed graphs provides a foundation for understanding the asymptotic properties of random walks in these random environments, which we study in a second paper. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 45, 111-137, 2014
- Published
- 2012
10. Random graphs containing few disjoint excluded minors
- Author
-
Colin McDiarmid and Valentas Kurauskas
- Subjects
Discrete mathematics ,Clique-sum ,Applied Mathematics ,General Mathematics ,Robertson–Seymour theorem ,Computer Graphics and Computer-Aided Design ,1-planar graph ,Planar graph ,Combinatorics ,symbols.namesake ,Pathwidth ,Graph power ,symbols ,Cograph ,Software ,Forbidden graph characterization ,Mathematics - Abstract
The Erdos-Pósa theorem (1965) states that in each graph G which contains at most k disjoint cycles, there is a 'blocking' set B of at most f(k) vertices such that the graph G - B is acyclic. Robertson and Seymour (1986) give an extension concerning any minor-closed class \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document} of graphs, as long as \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document} does not contain all planar graphs: in each graph G which contains at most k disjoint excluded minors for \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document}, there is a set B of at most g(k) vertices such that G - B is in \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document}. In an earlier paper (Kurauskas and McDiarmid, Combin, Probab Comput 20 (2011) 763-775), we showed that, amongst all graphs on vertex set [n] = {1,...,n} which contain at most k disjoint cycles, all but an exponentially small proportion contain a blocking set of just k vertices. In the present paper we build on the previous work, and give an extension concerning any minor-closed graph class \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document} with 2-connected excluded minors, as long as \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document} does not contain all fans (here a 'fan' is a graph consisting of a path together with a vertex joined to each vertex on the path). We show that amongst all graphs G on [n] which contain at most k disjoint excluded minors for \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document}, all but an exponentially small proportion contain a set B of k vertices such that G - B is in \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document}. (This is not the case when \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document} contains all fans.) For a random graph R sampled uniformly from the graphs on [n] with at most k disjoint excluded minors for \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document}, we consider also vertex degrees and the uniqueness of small blockers, the clique number and chromatic number, and the probability of being connected. © 2012 Wiley Periodicals, Inc.
- Published
- 2012
11. The diameter of a random subgraph of the hypercube
- Author
-
Tomáš Kulich
- Subjects
Random graph ,Discrete mathematics ,Applied Mathematics ,General Mathematics ,Dimension (graph theory) ,Sampling (statistics) ,Computer Graphics and Computer-Aided Design ,Upper and lower bounds ,Combinatorics ,Random regular graph ,Almost surely ,struct ,Hypercube ,Software ,Mathematics - Abstract
In this paper we present an estimation for the diameter of random subgraph of a hypercube. In the article by A. V. Kostochka (Random Struct Algorithms 4 (1993) 215–229) the authors obtained lower and upper bound for the diameter. According to their work, the inequalities n + mp ≤ D(Gn) ≤ n + mp + 8 almost surely hold as n → ∞, where n is dimension of the hypercube and mp depends only on sampling probabilities. It is not clear from their work, whether the values of the diameter are really distributed on these 9 values, or whether the inequality can be sharpened. In this paper we introduce several new ideas, using which we are able to obtain an exact result: D(Gn) = n + mp (almost surely). © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012 © 2012 Wiley Periodicals, Inc.
- Published
- 2012
12. Counting strongly-connected, moderately sparse directed graphs
- Author
-
Boris Pittel
- Subjects
Discrete mathematics ,Strongly connected component ,Degree (graph theory) ,Applied Mathematics ,General Mathematics ,Directed graph ,Term (logic) ,Computer Graphics and Computer-Aided Design ,Combinatorics ,Modular decomposition ,Indifference graph ,Chordal graph ,Asymptotic formula ,Software ,Mathematics - Abstract
A sharp asymptotic formula for the number of strongly connected digraphs on n labelled vertices with m arcs, under the condition m - n ≫ n2/3, m = O(n), is obtained; this provides a partial solution of a problem posed by Wright back in 1977. This formula is a counterpart of a classic asymptotic formula, due to Bender, Canfield and McKay, for the total number of connected undirected graphs on n vertices with m edges. A key ingredient of their proof was a recurrence equation for the connected graphs count due to Wright. No analogue of Wright's recurrence seems to exist for digraphs. In a previous paper with Nick Wormald we rederived the BCM formula by counting first connected graphs among the graphs of minimum degree 2, at least. In this paper, using a similar embedding for directed graphs, we find an asymptotic formula, which includes an explicit error term, for the fraction of strongly-connected digraphs with parameters m and n among all such digraphs with positive in/out-degrees. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013
- Published
- 2012
13. A study on semiflows generated by cooperative full-range CNNs
- Author
-
Mauro Forti, M. Grazzini, Mauro Di Marco, Luca Pancioni, and Paolo Nistri
- Subjects
Discrete mathematics ,Pure mathematics ,Generalization ,Applied Mathematics ,Monotonic function ,Strongly monotone ,Computer Science Applications ,Electronic, Optical and Magnetic Materials ,Monotone polygon ,Differential inclusion ,Cellular neural network ,Ordinary differential equation ,Irreducibility ,Electrical and Electronic Engineering ,Mathematics - Abstract
The paper considers the full-range (FR) model of cellular neural networks (CNNs) characterized by ideal hard-limiter nonlinearities with two vertical segments in the current–voltage characteristic. It is shown that when the FRCNNs are cooperative, i.e., there are excitatory interconnections between distinct neurons, the generated solution semiflow is monotone and that monotonicity implies some fundamental restrictions on the geometry of omega-limit sets. The result on monotonicity is a generalization to the class of differential inclusions describing the dynamics of FRCNNs of a classic result due to Kamke for cooperative ordinary differential equations. The paper also points out difficulties to use the standard theory of eventually strongly monotone (ESM) semiflows for addressing convergence of FRCNNs. By means of counterexamples, it is shown that, even assuming the irreducibility of the interconnections, the semiflow generated by a cooperative FRCNN is not ESM; furthermore, also the limit set dichotomy can be violated. Copyright © 2012 John Wiley & Sons, Ltd.
- Published
- 2012
14. Operator-based interpolation for bootstrap algebraic multigrid
- Author
-
Thomas A. Manteuffel, Steve F. McCormick, John W. Ruge, and Minho Park
- Subjects
Discrete mathematics ,Algebra and Number Theory ,Multigrid method ,Iterative method ,Homogeneous differential equation ,Applied Mathematics ,Scalar (mathematics) ,Applied mathematics ,Of the form ,Solver ,Mathematics - Abstract
Bootstrap algebraic multigrid (BAMG) is a multigrid-based solver for matrix equations of the form Ax=b. Its aim is to automatically determine the interpolation weights used in algebraic multigrid (AMG) by locally fitting a set of test vectors that have been relaxed as solutions to the corresponding homogeneous equation, Ax=0, and are then possibly improved later using a multilevel eigensolver. This paper introduces a flexible variant of BAMG that determines the interpolation weights indirectly by ‘collapsing’ the unwanted connections in ‘operator interpolation’. Compared to BAMG, this indirect BAMG approach (iBAMG) is more in the spirit of classical AMG, which collapses unwanted connections in operator interpolation based on the (restrictive) assumption that smooth error is locally constant. This paper studies the numerical performance of iBAMG and establishes an equivalence, under certain assumptions, between it and a slightly modified (standard) BAMG scheme. To focus on camparing BAMG and iBAMG and exposing their behavior as the problem size grows, the numerical experiments concentrate on Poisson-like scalar problems. Copyright © 2010 John Wiley & Sons, Ltd.
- Published
- 2010
15. On the successive supersymmetric rank-1 decomposition of higher-order supersymmetric tensors
- Author
-
Liqun Qi and Yiju Wang
- Subjects
Discrete mathematics ,Pure mathematics ,Algebra and Number Theory ,Rank (linear algebra) ,Applied Mathematics ,High Energy Physics::Phenomenology ,Diagonalizable matrix ,Supersymmetry ,High Energy Physics::Theory ,Decomposition (computer science) ,Symmetric matrix ,Tensor ,Greedy algorithm ,Eigendecomposition of a matrix ,Mathematics - Abstract
SUMMARY In this paper, a successive supersymmetric rank-1 decomposition of a real higher-order supersymmetric tensor is considered. To obtain such a decomposition, we design a greedy method based on iteratively computing the best supersymmetric rank-1 approximation of the residual tensors. We further show that a supersymmetric canonical decomposition could be obtained when the method is applied to an orthogonally diagonalizable supersymmetric tensor, and in particular, when the order is 2, this method generates the eigenvalue decomposition for symmetric matrices. Details of the algorithm designed and the numerical results are reported in this paper. Copyright q 2007 John Wiley & Sons, Ltd.
- Published
- 2007
16. Augmented canonical forms and factorization of graphs
- Author
-
M. A. Sayarinejad and Ali Kaveh
- Subjects
Discrete mathematics ,Numerical Analysis ,Applied Mathematics ,Symmetric graph ,General Engineering ,Graph theory ,Matrix decomposition ,Algebra ,Factorization ,Homogeneous space ,Canonical form ,Laplace operator ,Eigenvalues and eigenvectors ,Mathematics - Abstract
The main aim of this paper is to generalize the previously developed canonical forms by different types of alterations and/or augmentations. These forms provide suitable tools for the decomposition of the matrices of special patterns and lead to efficient aproaches for calculating their eigenvalues. Methods were developed for factorization of symmetric graphs into smaller subgraphs using decompostion and healings (Commun. Numer. Meth. Engng 2003; 19:125–136, 2004; 20:133–146, 2004; 20:889–910; Comput. Struct. 2004; 18:2229–2240). Further factorization was possible only when further symmetries were available. The main drawback was associated with non-decomposiblity of some of the factors in early stages of decomposition, and in particular healing which often destroyed the symmetry. In this paper, the mathematical concepts related to certain symmetric and unsymmetric graphs are developed, making refined factorization of the graphs feasible. Examples are included to show the simplicity of the operations being involved. Copyright © 2005 John Wiley & Sons, Ltd.
- Published
- 2006
17. On the componentwise stability of linear systems
- Author
-
Mihail Voicu and Octavian Pastravanu
- Subjects
Discrete mathematics ,Mechanical Engineering ,General Chemical Engineering ,Linear system ,Biomedical Engineering ,Aerospace Engineering ,Industrial and Manufacturing Engineering ,Exponential function ,System dynamics ,Formalism (philosophy of mathematics) ,Operator (computer programming) ,Exponential stability ,Control and Systems Engineering ,Applied mathematics ,Electrical and Electronic Engineering ,Mutatis mutandis ,Mathematics - Abstract
The componentwise asymptotic stability (CWAS) and componentwise exponential asymptotic stability (CWEAS) represent stronger types of asymptotic stability, which were first defined for symmetrical bounds constraining the flow of the state-space trajectories, and then, were generalized for arbitrary bounds, not necessarily symmetrical. Our paper explores the links between the symmetrical and the general case, proving that the former contains all the information requested by the characterization of the CWAS/CWEAS as qualitative properties. Complementary to the previous approaches to CWAS/CWEAS that were based on the construction of special operators, we incorporate the flow-invariance condition into the classical framework of stability analysis. Consequently, we show that the componentwise stability can be investigated by using the operator defining the system dynamics, as well as the standard e−δ formalism. Although this paper explicitly refers only to continuous-time linear systems, the key elements of our work also apply, mutatis mutandis, to discrete-time linear systems. Copyright © 2004 John Wiley & Sons, Ltd.
- Published
- 2004
18. Regularity properties for triple systems
- Author
-
Vojtech Rödl and Brendan Nagle
- Subjects
Discrete mathematics ,Combinatorics ,Applied Mathematics ,General Mathematics ,Graph theory ,Computer Graphics and Computer-Aided Design ,Software ,Graph ,Mathematics ,Extremal graph theory - Abstract
Szemeredi's Regularity Lemma proved to be a powerful tool in the area of extremal graph theory [J. Komlos and M. Simonovits, Szemeredi's Regularity Lemma and its applications in graph theory, Combinatorics 2 (1996), 295-352]. Many of its applications are based on the following technical fact: If G is a k-partite graph with V(G) = ∪ki=1 Vi, |Vi| = n for all i ∈ [k], and all pairs {Vi, Vj}, 1 ≤ i < j ≤ k, are e-regular of density d, then G contains d??nk(1 + f(e)) cliques K(2)k, where f(e) → 0 as e → 0. The aim of this paper is to establish the analogous statement for 3-uniform hypergraphs. Our result, to which we refer as The Counting Lemma, together with Theorem 3.5 of P. Frankl and V. Rodl [Extremal problems on set systems, Random Structures Algorithms 20(2) (2002), 131-164), a Regularity Lemma for Hypergraphs, can be applied in various situations as Szemeredi's Regularity Lemma is for graphs. Some of these applications are discussed in previous papers, as well as in upcoming papers, of the authors and others.
- Published
- 2003
19. Characterizing the solution set of polynomial systems in terms of homogeneous forms: an LMI approach
- Author
-
Antonio Vicino, Andrea Garulli, Graziano Chesi, and Alberto Tesi
- Subjects
Discrete mathematics ,Mechanical Engineering ,General Chemical Engineering ,Companion matrix ,Biomedical Engineering ,Aerospace Engineering ,Industrial and Manufacturing Engineering ,Polynomial matrix ,Matrix polynomial ,Symmetric polynomial ,Control and Systems Engineering ,Stable polynomial ,Minimal polynomial (linear algebra) ,Polynomial kernel ,Applied mathematics ,Electrical and Electronic Engineering ,Characteristic polynomial ,Mathematics - Abstract
This paper considers the problem of determining the solution set of polynomial systems, a well-known problem in control system analysis and design. A novel approach is developed as a viable alternative to the commonly employed algebraic geometry and homotopy methods. The first result of the paper shows that the solution set of the polynomial system belongs to the kernel of a suitable symmetric matrix. Such a matrix is obtained via the solution of a linear matrix inequality (LMI) involving the maximization of the minimum eigenvalue of an affine family of symmetric matrices. The second result concerns the computation of the solution set from the kernel of the obtained matrix. For polynomial systems of degree m in n variables, a basic procedure is available if the kernel dimension does not exceed m+1, while an extended procedure can be applied if the kernel dimension is less than n(m−1)+2. Finally, some application examples are illustrated to show the features of the approach and to make a brief comparison with polynomial resultant techniques. Copyright © 2003 John Wiley & Sons, Ltd.
- Published
- 2003
20. On characterizing hypergraph regularity
- Author
-
Penny Haxell, V. Rödl, Yulia Dementieva, and Brendan Nagle
- Subjects
Discrete mathematics ,Hypergraph ,Lemma (mathematics) ,Mathematics::Combinatorics ,Applied Mathematics ,General Mathematics ,010102 general mathematics ,Graph theory ,Szemerédi regularity lemma ,0102 computer and information sciences ,01 natural sciences ,Computer Graphics and Computer-Aided Design ,Graph ,Extremal graph theory ,Combinatorics ,010201 computation theory & mathematics ,Bipartite graph ,Verifiable secret sharing ,0101 mathematics ,Software ,Mathematics - Abstract
Szemeredi's Regularity Lemma is a well-known and powerful tool in modern graph theory. This result led to a number of interesting applications, particularly in extremal graph theory. A regularity lemma for 3-uniform hypergraphs developed by Frankl and Rodl [8] allows some of the Szemeredi Regularity Lemma graph applications to be extended to hypergraphs. An important development regarding Szemeredi's Lemma showed the equivalence between the property of e-regularity of a bipartite graph G and an easily verifiable property concerning the neighborhoods of its vertices (Alon et al. [1]; cf. [6]). This characterization of e-regularity led to an algorithmic version of Szemeredi's lemma [1]. Similar problems were also considered for hypergraphs. In [2], [9], [13], and [18], various descriptions of quasi-randomness of k-uniform hypergraphs were given. As in [1], the goal of this paper is to find easily verifiable conditions for the hypergraph regularity provided by [8]. The hypergraph regularity of [8] renders quasi-random "blocks of hyperedges" which are very sparse. This situation leads to technical difficulties in its application. Moreover, as we show in this paper, some easily verifiable conditions analogous to those considered in [2] and [18] fail to be true in the setting of [8]. However, we are able to find some necessary and sufficient conditions for this hypergraph regularity. These conditions enable us to design an algorithmic version of a hypergraph regularity lemma in [8]. This algorithmic version is presented by the authors in [5].
- Published
- 2002
21. Hamilton cycles containing randomly selected edges in random regular graphs
- Author
-
Nicholas C. Wormald and Robert W. Robinson
- Subjects
Discrete mathematics ,Distribution (number theory) ,Applied Mathematics ,General Mathematics ,Contiguity ,Computer Graphics and Computer-Aided Design ,Hamiltonian path ,Combinatorics ,symbols.namesake ,Random regular graph ,symbols ,Cubic graph ,Probability distribution ,Almost surely ,Hamiltonian (quantum mechanics) ,Software ,Mathematics - Abstract
In previous papers the authors showed that almost all d-regular graphs for d≤3 are hamiltonian. In the present paper this result is generalized so that a set of j oriented root edges have been randomly specified for the cycle to contain. The Hamilton cycle must be orientable to agree with all of the orientations on the j root edges. It is shown that the requisite Hamilton cycle almost surely exists if and the limiting probability distribution at the threshold is determined when d=3. It is a corollary (in view of results elsewhere) that almost all claw-free cubic graphs are hamiltonian. There is a variation in which an additional cyclic ordering on the root edges is imposed which must also agree with their ordering on the Hamilton cycle. In this case, the required Hamilton cycle almost surely exists if j=o(n2/5). The method of analysis is small subgraph conditioning. This gives results on contiguity and the distribution of the number of Hamilton cycles which imply the facts above. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19: 128–147, 2001
- Published
- 2001
22. Coloring nonuniform hypergraphs: A new algorithmic approach to the general Lov�sz local lemma
- Author
-
Artur Czumaj and Christian Schiedeler
- Subjects
Discrete mathematics ,Polynomial ,Class (set theory) ,Mathematics::Combinatorics ,Applied Mathematics ,General Mathematics ,Sieve (category theory) ,Mathematical proof ,Computer Graphics and Computer-Aided Design ,Randomized algorithm ,Combinatorics ,Time complexity ,Lovász local lemma ,Software ,Algorithmic Lovász local lemma ,Mathematics - Abstract
The Lovasz local lemma is a sieve method to prove the existence of certain structures with certain prescribed properties. In most of its applications the Lovasz local lemma does not supply a polynomial-time algorithm for finding these structures. Beck was the first who gave a method of converting some of these existence proofs into efficient algorithmic procedures, at the cost of losing a little in the estimates. He applied his technique to the symmetric form of the Lovasz local lemma and, in particular, to the problem of 2-coloring uniform hypergraphs. In this paper we investigate the general form of the Lovasz local lemma. Our main result is a randomized algorithm for 2-coloring nonuniform hypergraphs that runs in expected linear time. Even for uniform hypergraphs no algorithm with such a runtime bound was previously known, and no polynomial-time algorithm was known at all for the class of nonuniform hypergraphs we will consider in this paper. Our algorithm and its analysis provide a novel approach to the general Lovasz local lemma that may be of independent interest. We also show how to extend our result to the c-coloring problem. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 17: 213–237, 2000
- Published
- 2000
23. Approximating the unsatisfiability threshold of random formulas
- Author
-
Yannis C. Stamatiou, Danny Krizanc, Lefteris M. Kirousis, and Evangelos Kranakis
- Subjects
Discrete mathematics ,Sequence ,True quantified Boolean formula ,Applied Mathematics ,General Mathematics ,Zero (complex analysis) ,Expected value ,Computer Graphics and Computer-Aided Design ,Upper and lower bounds ,Satisfiability ,Combinatorics ,Random variable ,Software ,Mathematics ,Real number - Abstract
Let f be a random Boolean formula that is an instance of 3-SAT. We consider the problem of computing the least real number k such that if the ratio of the number of clauses over the number of variables of f strictly exceeds k , then f is almost certainly unsatisfiable. By a well-known and more or less straightforward argument, it can be shown that kF5.191. This upper bound was improved by Kamath et al. to 4.758 by first providing new improved bounds for the occupancy problem. There is strong experimental evidence that the value of k is around 4.2. In this work, we define, in terms of the random formula f, a decreasing sequence of random variables such that, if the expected value of any one of them converges to zero, then f is almost certainly unsatisfiable. By letting the expected value of the first term of the sequence converge to zero, we obtain, by simple and elementary computations, an upper bound for k equal to 4.667. From the expected value of the second term of the sequence, we get the value 4.601q . In general, by letting the U This work was performed while the first author was visiting the School of Computer Science, Carleton Ž University, and was partially supported by NSERC Natural Sciences and Engineering Research Council . of Canada , and by a grant from the University of Patras for sabbatical leaves. The second and third Ž authors were supported in part by grants from NSERC Natural Sciences and Engineering Research . Council of Canada . During the last stages of this research, the first and last authors were also partially Ž . supported by EU ESPRIT Long-Term Research Project ALCOM-IT Project No. 20244 . †An extended abstract of this paper was published in the Proceedings of the Fourth Annual European Ž Symposium on Algorithms, ESA’96, September 25]27, 1996, Barcelona, Spain Springer-Verlag, LNCS, . pp. 27]38 . That extended abstract was coauthored by the first three authors of the present paper. Correspondence to: L. M. Kirousis Q 1998 John Wiley & Sons, Inc. CCC 1042-9832r98r030253-17 253
- Published
- 1998
24. Maximal full subspaces in random projective spaces-thresholds and Poisson approximation
- Author
-
Wojciech Kordecki
- Subjects
Random graph ,Discrete mathematics ,Generalization ,Applied Mathematics ,General Mathematics ,Poisson distribution ,Mathematical proof ,Computer Graphics and Computer-Aided Design ,Linear subspace ,Matroid ,Combinatorics ,symbols.namesake ,symbols ,Rank (graph theory) ,Projective test ,Software ,Mathematics - Abstract
Let Gn, p denote a random graph on n vertices. It is an interesting problem when small cliques arise and what distributions of the number of small cliques may occur. Matroids are natural generalization of graphs; therefore, we can try to investigate maximal flats of a small rank in random matroids. The most studied and most interesting seem to be “random projective geometries” introduced by Kelly and Oxley. Many of the theorems in our paper are based on the results published in a long paper of Barbour, Janson, Karoski, and Ruciski. However, proofs for projective geometries generally are more complicated. © 1995 Wiley Periodicals, Inc.
- Published
- 1995
25. Szemerédi's partition and quasirandomness
- Author
-
Miklós Simonovits and Vera T. Sós
- Subjects
Discrete mathematics ,Pseudorandom number generator ,Random graph ,Hypergraph ,Applied Mathematics ,General Mathematics ,Computer Graphics and Computer-Aided Design ,Combinatorics ,Probability space ,Probability theory ,If and only if ,Random regular graph ,Partition (number theory) ,Software ,Mathematics - Abstract
In this paper we shall investigate the connection between the SzemerCdi Regularity Lemma and quasirandom graph sequences, defined by Chung, Graham, and Wilson, and also, slightly differently, by Thomason. We prove that a graph sequence (G,) is quasirandom if and only if in the SzemerCdi partitions of G, almost all densities are $ + o(1). Many attempts have been made to clarify when an individual event could be called random and in what sense. Both the fundamental problems of probability theory and some practical application need this clarification very much. For example, in applications of the Monte-Carlo method one needs to know if the random number generator used yields a sequence which can be regarded “pseudorandom” or not. The literature on this question is extremely extensive. Thomason [6-81 and Chung, Graham, and Wilson [2,3], and also Frankl, Rodl, and Wilson [4] started a new line of investigation, where (instead of regarding numerical sequences) they gave some characterizations of “randomlike” graph sequences, matrix sequences, and hypergraph sequences. The aim of this paper is to contribute to this question in case of graphs, continuing the above line of investigation. Let %(n, p) denote the probability space of labelled graphs on n vertices, where the edges are chosen independently and at random, with probability p. We shall say that “a random graph sequence (G,) has property P”
- Published
- 1991
26. Multicolor containers, extremal entropy, and counting
- Author
-
Victor Falgas-Ravry, Andrew J. Uzzell, and Kelly O'Connell
- Subjects
Discrete mathematics ,Hypergraph ,010201 computation theory & mathematics ,Applied Mathematics ,General Mathematics ,0102 computer and information sciences ,Hereditary property ,01 natural sciences ,Computer Graphics and Computer-Aided Design ,Software ,Extremal graph theory ,Mathematics - Abstract
In breakthrough results, Saxton-Thomason and Balogh-Morris-Samotij developed powerful theories of hypergraph containers. In this paper, we explore some consequences of these theories. We use a simp ...
- Published
- 2018
27. A new combinatorial representation of the additive coalescent
- Author
-
Jean-François Marckert, Minmin Wang, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Université Pierre et Marie Curie - Paris 6 (UPMC), Consejo Nacional de Investigaciones Científicas y Técnicas [Buenos Aires] (CONICET), ANR-14-CE25-0014,GRAAL,GRaphes et Arbres ALéatoires(2014), Marckert, Jean-François, and Appel à projets générique - GRaphes et Arbres ALéatoires - - GRAAL2014 - ANR-14-CE25-0014 - Appel à projets générique - VALID
- Subjects
[MATH.MATH-PR] Mathematics [math]/Probability [math.PR] ,parking ,General Mathematics ,68R05 Key Words: additive coalescent ,Markov process ,0102 computer and information sciences ,01 natural sciences ,increasing trees ,Coalescent theory ,Combinatorics ,symbols.namesake ,60J25 ,60F05 ,Representation (mathematics) ,ComputingMilieux_MISCELLANEOUS ,construction Mathematics Subject Classification (2000) 60C05 ,Mathematics ,Block (data storage) ,Discrete mathematics ,Applied Mathematics ,Probabilistic logic ,Cayley trees ,Computer Graphics and Computer-Aided Design ,Tree (graph theory) ,[MATH.MATH-PR]Mathematics [math]/Probability [math.PR] ,random walks on trees ,60K35 ,010201 computation theory & mathematics ,symbols ,Node (circuits) ,Variety (universal algebra) ,Software - Abstract
The standard additive coalescent starting with n particles is a Markov process which owns several combinatorial representations, one by Pitman as a process of coalescent forests, and one by Chassaing & Louchard as the block sizes in a parking scheme. In the coalescent forest representation, some edges are added successively between a random node and a random root. In this paper, we investigate an alternative construction by adding edges between the roots. This construction induces the same process at the level of cluster sizes, but allows one to make numerous connections with some combinatorial and probabilistic models that were not known to be connected with additive coalescent. The variety of the combinatorial objects involved here – size biased percolation, parking scheme in a tree, increasing trees, random cuts of trees – justifies our interests in this Acknowledgement : The research has been supported by ANR-14-CE25-0014 (ANR GRAAL).
- Published
- 2018
28. The random connection model: Connectivity, edge lengths, and degree distributions
- Author
-
Srikanth K. Iyer
- Subjects
Random graph ,Discrete mathematics ,Unit sphere ,Applied Mathematics ,General Mathematics ,Degree distribution ,01 natural sciences ,Computer Graphics and Computer-Aided Design ,Vertex (geometry) ,Combinatorics ,010104 statistics & probability ,Connection model ,0103 physical sciences ,Poisson point process ,0101 mathematics ,010306 general physics ,Random geometric graph ,Software ,Mathematics - Abstract
Consider the random graph G(Pn,r) whose vertex set Pn is a Poisson point process of intensity n on (-12,12]d,d2. Any two vertices Xi,XjPn are connected by an edge with probability g(d(Xi,Xj)r), independently of all other edges, and independent of the other points of Pn. d is the toroidal metric, r > 0 and g:0,)0,1] is non-increasing and =dg(|x|)dx ) does not have any isolated nodes satisfies lim?nnMndlog?n=1. Let =inf?{x > 0:xg(x)> 1}, and be the volume of the unit ball in d. Then for all >, G(Pn,(log?nn)1d) is connected with probability approaching one as n. The bound can be seen to be tight for the usual random geometric graph obtained by setting g=10,1]. We also prove some useful results on the asymptotic behavior of the length of the edges and the degree distribution in the connectivity regime. The results in this paper work for connection functions g that are not necessarily compactly supported but satisfy g(r)=o(r-c).
- Published
- 2017
29. Coloring graphs of various maximum degree from random lists
- Author
-
Carl Johan Casselgren
- Subjects
FOS: Computer and information sciences ,Discrete mathematics ,Discrete Mathematics (cs.DM) ,Applied Mathematics ,General Mathematics ,010102 general mathematics ,0102 computer and information sciences ,01 natural sciences ,Computer Graphics and Computer-Aided Design ,Graph ,Vertex (geometry) ,Combinatorics ,010201 computation theory & mathematics ,coloring from random lists ,list coloring ,random list ,FOS: Mathematics ,Mathematics - Combinatorics ,Sannolikhetsteori och statistik ,Combinatorics (math.CO) ,0101 mathematics ,Probability Theory and Statistics ,Software ,Computer Science - Discrete Mathematics ,Mathematics ,List coloring - Abstract
Let $G=G(n)$ be a graph on $n$ vertices with maximum degree $\Delta=\Delta(n)$. Assign to each vertex $v$ of $G$ a list $L(v)$ of colors by choosing each list independently and uniformly at random from all $k$-subsets of a color set $\mathcal{C}$ of size $\sigma= \sigma(n)$. Such a list assignment is called a \emph{random $(k,\mathcal{C})$-list assignment}. In this paper, we are interested in determining the asymptotic probability (as $n \to \infty$) of the existence of a proper coloring $\varphi$ of $G$, such that $\varphi(v) \in L(v)$ for every vertex $v$ of $G$, a so-called $L$-coloring. We give various lower bounds on $\sigma$, in terms of $n$, $k$ and $\Delta$, which ensures that with probability tending to 1 as $n \to \infty$ there is an $L$-coloring of $G$. In particular, we show, for all fixed $k$ and growing $n$, that if $\sigma(n) = \omega(n^{1/k^2} \Delta^{1/k})$ and $\Delta=O\left(n^{\frac{k-1}{k(k^3+ 2k^2 - k +1)}}\right)$, then the probability that $G$ has an $L$-coloring tends to 1 as $n \rightarrow \infty$. If $k\geq 2$ and $\Delta= \Omega(n^{1/2})$, then the same conclusion holds provided that $\sigma=\omega(\Delta)$. We also give related results for other bounds on $\Delta$, when $k$ is constant or a strictly increasing function of $n$.
- Published
- 2017
30. Stability of the Greedy Algorithm on the Circle
- Author
-
Leonardo T. Rolla and Vladas Sidoravicius
- Subjects
Service (business) ,Discrete mathematics ,Conjecture ,Matemáticas ,Applied Mathematics ,General Mathematics ,Probability (math.PR) ,010102 general mathematics ,purl.org/becyt/ford/1.1 [https] ,Stability (learning theory) ,01 natural sciences ,Matemática Pura ,Exponential function ,purl.org/becyt/ford/1 [https] ,010104 statistics & probability ,Value (economics) ,FOS: Mathematics ,Point (geometry) ,0101 mathematics ,Routing (electronic design automation) ,Greedy algorithm ,CIENCIAS NATURALES Y EXACTAS ,Mathematics - Probability ,Mathematics - Abstract
We consider a single-server system with service stations in each point of the circle. Customers arrive after exponential times at uniformly distributed locations. The server moves at finite speed and adopts a greedy routing mechanism. It was conjectured by Coffman and Gilbert in 1987 that the service rate exceeding the arrival rate is a sufficient condition for the system to be positive recurrent, for any value of the speed. In this paper we show that the conjecture holds true.© 2017 Wiley Periodicals, Inc. Fil: Trivellato Rolla, Leonardo. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigaciones Matemáticas ; Argentina Fil: Sidoravicius, Vladas. University of New York; Estados Unidos
- Published
- 2017
31. Conic martingales from stochastic integrals
- Author
-
Frédéric Vrins, Monique Jeanblanc, Université Catholique de Louvain (UCL), Laboratoire de Mathématiques et Modélisation d'Evry (LaMME), Institut National de la Recherche Agronomique (INRA)-Université d'Évry-Val-d'Essonne (UEVE)-ENSIIE-Centre National de la Recherche Scientifique (CNRS), JEANBLANC, Monique, Université Catholique de Louvain = Catholic University of Louvain (UCL), Institut National de la Recherche Agronomique (INRA)-Université d'Évry-Val-d'Essonne (UEVE)-Centre National de la Recherche Scientifique (CNRS), and Laboratoire de Mathématiques et Modélisation d'Evry
- Subjects
[MATH.MATH-PR] Mathematics [math]/Probability [math.PR] ,Economics and Econometrics ,Pure mathematics ,[MATH] Mathematics [math] ,stochastic differential equation ,01 natural sciences ,Separable space ,Stochastic differential equation ,010104 statistics & probability ,symbols.namesake ,Mathematics::Probability ,Wiener process ,Accounting ,0502 economics and business ,Applied mathematics ,[MATH]Mathematics [math] ,0101 mathematics ,Martingale representation theorem ,Brownian motion ,Mathematics ,Discrete mathematics ,Geometric Brownian motion ,050208 finance ,Stochastic process ,Applied Mathematics ,010102 general mathematics ,05 social sciences ,Bounded martingale ,[MATH.MATH-PR]Mathematics [math]/Probability [math.PR] ,Doob's martingale inequality ,Diffusion process ,Conic section ,Quantitative Finance - Mathematical Finance ,Azuma's inequality ,Local martingale ,symbols ,Martingale difference sequence ,stochastic survival probability ,diffusion process ,Martingale (probability theory) ,Mathematics - Probability ,Social Sciences (miscellaneous) ,Finance - Abstract
In this paper we introduce the concept of conic martingales}. This class refers to stochastic processes having the martingale property, but that evolve within given (possibly time-dependent) boundaries. We first review some results about the martingale property of solution to driftless stochastic differential equations. We then provide a simple way to construct and handle such processes. Specific attention is paid to martingales in $[0,1]$. One of these martingales proves to be analytically tractable. It is shown that up to shifting and rescaling constants, it is the only martingale (with the trivial constant, Brownian motion and Geometric Brownian motion) having a separable coefficient $\sigma(t,y)=g(t)h(y)$ and that can be obtained via a time-homogeneous mapping of Gaussian diffusions. The approach is exemplified to the modeling of stochastic conditional survival probabilities in the univariate (both conditional and unconditional to survival) and bivariate cases., Comment: 34 pages, 5 figures
- Published
- 2017
32. WEIGHTED INEQUALITIES FOR MARTINGALE TRANSFORMS AND STOCHASTIC INTEGRALS
- Author
-
Adam Osȩkowski
- Subjects
Discrete mathematics ,General Mathematics ,010102 general mathematics ,Mathematical proof ,01 natural sciences ,Doob's martingale inequality ,010104 statistics & probability ,Special functions ,Local martingale ,Applied mathematics ,Martingale difference sequence ,0101 mathematics ,Majorization ,Predictable process ,Martingale (probability theory) ,Mathematics - Abstract
The paper is devoted to the study of Fefferman–Stein inequalities for stochastic integrals. If is a martingale, is the stochastic integral, with respect to , of some predictable process taking values in , then for any weight belonging to the class we have the estimates and The proofs rest on the Bellman function method: the inequalities are deduced from the existence of certain special functions, enjoying appropriate majorization and concavity. As an application, related statements for Haar multipliers are indicated. The above estimates can be regarded as probabilistic counterparts of the recent results of Lerner, Ombrosi and Perez concerning singular integral operators.
- Published
- 2017
33. On generalized Borgen plots II: The line-moving algorithm and its numerical implementation
- Author
-
Klaus Neymeyr, Annekathrin Jürß, and Mathias Sawall
- Subjects
Discrete mathematics ,business.industry ,Applied Mathematics ,Computation ,010401 analytical chemistry ,02 engineering and technology ,021001 nanoscience & nanotechnology ,01 natural sciences ,0104 chemical sciences ,Analytical Chemistry ,Set (abstract data type) ,Mathematical theory ,Software ,Line (geometry) ,0210 nano-technology ,business ,Spectral data ,Algorithm ,Mathematics - Abstract
Borgen plots are geometric constructions that represent the set of all nonnegative factorizations of spectral data matrices for three-component systems. The classical construction by Borgen and Kowalski (Anal. Chim. Acta 174, 1-26 (1985)) is limited to nonnegative data and results in nonnegative factorizations. The new approach of generalized Borgen plots allows factors with small negative entries. This makes it possible to construct Borgen plots for perturbed or noisy spectral data and stabilizes the computation. In the first part of this paper, the mathematical theory of generalized Borgen plots has been introduced. This second part presents the line-moving algorithm for the construction of generalized Borgen plots. The algorithm is justified, and the implementation in the FACPACK software is validated.
- Published
- 2016
34. Fuzzy transformations and extremality of Gibbs measures for the potts model on a Cayley tree
- Author
-
Christof Külske and Utkir Abdulloevich Rozikov
- Subjects
Discrete mathematics ,Markov chain ,Explicit formulae ,Applied Mathematics ,General Mathematics ,010102 general mathematics ,Interval (mathematics) ,01 natural sciences ,Computer Graphics and Computer-Aided Design ,Set (abstract data type) ,010104 statistics & probability ,symbols.namesake ,symbols ,Order (group theory) ,Tree (set theory) ,0101 mathematics ,Gibbs measure ,Software ,Mathematics ,Potts model - Abstract
We continue our study of the full set of translation-invariant splitting Gibbs measures TISGMs, translation-invariant tree-indexed Markov chains for the q-state Potts model on a Cayley tree. In our previous work Kulske et al., J Stat Phys 156 2014, 189-200 we gave a full description of the TISGMs, and showed in particular that at sufficiently low temperatures their number is 2q-1. In this paper we find some regions for the temperature parameter ensuring that a given TISGM is non-extreme in the set of all Gibbs measures. In particular we show the existence of a temperature interval for which there are at least 2q-1+q extremal TISGMs. For the Cayley tree of order two we give explicit formulae and some numerical values. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 636-678, 2017
- Published
- 2016
35. Triangle factors of graphs without large independent sets and of weighted graphs
- Author
-
Maryam Sharifzadeh, Theodore Molla, and József Balogh
- Subjects
Vertex (graph theory) ,Discrete mathematics ,Conjecture ,Sublinear function ,Applied Mathematics ,General Mathematics ,010102 general mathematics ,0102 computer and information sciences ,01 natural sciences ,Computer Graphics and Computer-Aided Design ,Graph ,Combinatorics ,Quadratic equation ,Probabilistic method ,Factorization ,010201 computation theory & mathematics ,0101 mathematics ,Software ,Independence number ,Mathematics - Abstract
The classical Corr adi-Hajnal theorem claims that every n-vertex graph G with (G) 2n=3 contains a triangle factor, when 3jn. In this paper we asymptotically determine the minimum degree condition necessary to guarantee a triangle factor in graphs with sublinear independence number. In particular, we show that if G is an n-vertex graph with (G) = o(n) and (G) (1=2 + o(1))n, then G has a triangle factor and this is asymptotically best possible. Furthermore, it is shown for every r that if every linear size vertex set of a graph G spans quadratic many edges, and (G) (1=2 +o(1))n, then G has a Kr-factor for n suciently large. We also propose many related open problems whose solutions could show a relationship with RamseyTur an theory. Additionally, we also consider a fractional variant of the Corr adi-Hajnal Theorem, settling a conjecture of Balogh-Kemkes-Lee-Young. Let t2 (0; 1) and w : E(Kn)! [0; 1]. We call a triangle in Kn heavy if the sum of the weights on its edges is more than 3t. We prove that if 3jn and w is such that for every vertex v the sum of w(e)
- Published
- 2016
36. A two‐grid SA‐AMG convergence bound that improves when increasing the polynomial degree
- Author
-
Jinchao Xu, Xiaozhe Hu, and Panayot S. Vassilevski
- Subjects
Discrete mathematics ,Polynomial ,Algebra and Number Theory ,Partial differential equation ,Approximation property ,Applied Mathematics ,Uniform convergence ,010103 numerical & computational mathematics ,01 natural sciences ,010101 applied mathematics ,Multigrid method ,Rate of convergence ,Applied mathematics ,Degree of a polynomial ,0101 mathematics ,Laplacian matrix ,Mathematics - Abstract
Summary In this paper, we consider the convergence rate of a smoothed aggregation algebraic multigrid method, which uses a simple polynomial (1 − t)ν or an optimal Chebyshev-like polynomial to construct the smoother and prolongation operator. The result is purely algebraic, whereas a required main weak approximation property of the tentative interpolation operator is verified for a spectral element agglomeration version of the method. More specifically, we prove that, for partial differential equations (PDEs), the two-grid method converges uniformly without any regularity assumptions. Moreover, the convergence rate improves uniformly when the degree of the polynomials used for the smoother and the prolongation increases. Such a result, as is well-known, would imply uniform convergence of the multilevel W-cycle version of the algorithm. Numerical results, for both PDE and non-PDE (graph Laplacian) problems are presented to illustrate the theoretical findings. Published 2016. This article is a U.S. Government work and is in the public domain in the USA.
- Published
- 2016
37. The probability of connectivity in a hyperbolic model of complex networks
- Author
-
Bode, Michel, Fountoulakis, Nikolaos, Müller, Tobias, Sub Mathematical Modeling, Mathematical Modeling, Sub Mathematical Modeling, and Mathematical Modeling
- Subjects
Discrete mathematics ,Mathematics(all) ,Uniform distribution (continuous) ,Degree (graph theory) ,Applied Mathematics ,General Mathematics ,Hyperbolic geometry ,Zero (complex analysis) ,complex networks ,01 natural sciences ,Computer Graphics and Computer-Aided Design ,random geometric graphs ,Combinatorics ,010104 statistics & probability ,Bounded function ,0103 physical sciences ,Exponent ,Graph (abstract data type) ,0101 mathematics ,010306 general physics ,Constant (mathematics) ,Software ,Mathematics - Abstract
We consider a model for complex networks that was introduced by Krioukov et al. (Phys Rev E 82 (2010) 036106). In this model, N points are chosen randomly inside a disk on the hyperbolic plane according to a distorted version of the uniform distribution and any two of them are joined by an edge if they are within a certain hyperbolic distance. This model exhibits a power-law degree sequence, small distances and high clustering. The model is controlled by two parameters α and ν where, roughly speaking, α controls the exponent of the power-law and ν controls the average degree. In this paper we focus on the probability that the graph is connected. We show the following results. For α > 1/2 and ν arbitrary, the graph is disconnected with high probability. For α < 1/2 and ν arbitrary, the graph is connected with high probability. When α = 1/2 and ν is fixed then the probability of being connected tends to a constant f(ν) that depends only on ν, in a continuous manner. Curiously, f(ν) = 1 for ν ≥ Π while it is strictly increasing, and in particular bounded away from zero and one, for 0 < ν < Π. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 65–94, 2016.
- Published
- 2016
38. Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems
- Author
-
Emmanuel J. Candès and Yuxin Chen
- Subjects
FOS: Computer and information sciences ,Computer Science - Information Theory ,General Mathematics ,Machine Learning (stat.ML) ,Mathematics - Statistics Theory ,Statistics Theory (math.ST) ,010103 numerical & computational mathematics ,02 engineering and technology ,System of linear equations ,01 natural sciences ,Machine Learning (cs.LG) ,Quadratic equation ,Statistics - Machine Learning ,FOS: Mathematics ,0202 electrical engineering, electronic engineering, information engineering ,Mathematics - Numerical Analysis ,0101 mathematics ,Time complexity ,Complement (set theory) ,Mathematics ,Discrete mathematics ,Information Theory (cs.IT) ,Applied Mathematics ,Linear system ,020206 networking & telecommunications ,Numerical Analysis (math.NA) ,Computer Science - Learning ,Flow (mathematics) ,Constant (mathematics) ,Spectral method - Abstract
We consider the fundamental problem of solving quadratic systems of equations in $n$ variables, where $y_i = |\langle \boldsymbol{a}_i, \boldsymbol{x} \rangle|^2$, $i = 1, \ldots, m$ and $\boldsymbol{x} \in \mathbb{R}^n$ is unknown. We propose a novel method, which starting with an initial guess computed by means of a spectral method, proceeds by minimizing a nonconvex functional as in the Wirtinger flow approach. There are several key distinguishing features, most notably, a distinct objective functional and novel update rules, which operate in an adaptive fashion and drop terms bearing too much influence on the search direction. These careful selection rules provide a tighter initial guess, better descent directions, and thus enhanced practical performance. On the theoretical side, we prove that for certain unstructured models of quadratic systems, our algorithms return the correct solution in linear time, i.e. in time proportional to reading the data $\{\boldsymbol{a}_i\}$ and $\{y_i\}$ as soon as the ratio $m/n$ between the number of equations and unknowns exceeds a fixed numerical constant. We extend the theory to deal with noisy systems in which we only have $y_i \approx |\langle \boldsymbol{a}_i, \boldsymbol{x} \rangle|^2$ and prove that our algorithms achieve a statistical accuracy, which is nearly un-improvable. We complement our theoretical study with numerical examples showing that solving random quadratic systems is both computationally and statistically not much harder than solving linear systems of the same size---hence the title of this paper. For instance, we demonstrate empirically that the computational cost of our algorithm is about four times that of solving a least-squares problem of the same size., accepted to Communications on Pure and Applied Mathematics (CPAM)
- Published
- 2016
39. Bounds for pairs in judicious partitioning of graphs
- Author
-
Genghua Fan and Jianfeng Hou
- Subjects
Discrete mathematics ,Conjecture ,Applied Mathematics ,General Mathematics ,010102 general mathematics ,0102 computer and information sciences ,01 natural sciences ,Computer Graphics and Computer-Aided Design ,Graph ,Combinatorics ,010201 computation theory & mathematics ,Chernoff bound ,struct ,0101 mathematics ,Software ,Mathematics - Abstract
In 2002, Bollobas and Scott posed the following problem: for an integer k≥2 and a graph G of m edges, what is the smallest f(k, m) such that V(G) can be partitioned into V 1,…,Vk in which e(Vi∪Vj)≤f(k,m) for all 1≤i≠j≤k, where e(Vi∪Vj) denotes the number of edges with both ends in Vi∪Vj? In this paper, we solve this problem asymptotically by showing that f(k,m)≤m/(k−1)+o(m). We also show that V(G) can be partitioned into V1,…,Vk such that e(Vi∪Vj)≤4m/k2+4Δ/k+o(m) for 1≤i≠j≤k, where Δ denotes the maximum degree of G. This confirms a conjecture of Bollobas and Scott. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 59–70, 2017
- Published
- 2016
40. A combinatorial characterization of smooth LTCs and applications
- Author
-
Michael Viderman and Eli Ben-Sasson
- Subjects
Discrete mathematics ,0209 industrial biotechnology ,Hadamard code ,Applied Mathematics ,General Mathematics ,Reed–Muller code ,0102 computer and information sciences ,02 engineering and technology ,Locally decodable code ,01 natural sciences ,Computer Graphics and Computer-Aided Design ,Combinatorics ,020901 industrial engineering & automation ,010201 computation theory & mathematics ,Code (cryptography) ,Error detection and correction ,Tanner graph ,Software ,Word (computer architecture) ,Testability ,Mathematics - Abstract
The study of locally testable codes (LTCs) has benefited from a number of nontrivial constructions discovered in recent years. Yet, we still lack a good understanding of what makes a linear error correcting code locally testable and as a result we do not know what is the rate-limit of LTCs and whether asymptotically good linear LTCs with constant query complexity exist. In this paper, we provide a combinatorial characterization of smooth locally testable codes, which are locally testable codes whose associated tester queries every bit of the tested word with equal probability. Our main contribution is a combinatorial property defined on the Tanner graph associated with the code tester (“well-structured tester”). We show that a family of codes is smoothly locally testable if and only if it has a well-structured tester. As a case study we show that the standard tester for the Hadamard code is “well-structured,” giving an alternative proof of the local testability of the Hadamard code, originally proved by (Blum, Luby, Rubinfeld, J. Comput. Syst. Sci. 47 (1993) 549–595) (STOC 1990). Additional connections to the works of (Ben-Sasson, Harsha, Raskhodnikova, SIAM J. Comput 35 (2005) 1–21) (SICOMP 2005) and of (Lachish, Newman and Shapira, Comput Complex 17 (2008) 70–93) are also discussed. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 2016
- Published
- 2016
41. A local central limit theorem for triangles in a random graph
- Author
-
Justin Gilmer and Swastik Kopparty
- Subjects
Random graph ,Discrete mathematics ,Characteristic function (probability theory) ,Distribution (number theory) ,Applied Mathematics ,General Mathematics ,0102 computer and information sciences ,01 natural sciences ,Computer Graphics and Computer-Aided Design ,Combinatorics ,010104 statistics & probability ,010201 computation theory & mathematics ,Perfect graph ,Random regular graph ,Limit (mathematics) ,0101 mathematics ,Nested triangles graph ,Software ,Central limit theorem ,Mathematics - Abstract
In this paper, we prove a local limit theorem for the distribution of the number of triangles in the Erdos-Renyi random graph G(n, p), where is a fixed constant. Our proof is based on bounding the characteristic function of the number of triangles, and uses several different conditioning arguments for handling different ranges of t. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 2016
- Published
- 2016
42. Random directed graphs are robustly Hamiltonian
- Author
-
Dan Hefetz, Benny Sudakov, and Angelika Steger
- Subjects
Discrete mathematics ,Random graph ,Strongly connected component ,Applied Mathematics ,General Mathematics ,010102 general mathematics ,0102 computer and information sciences ,Directed graph ,01 natural sciences ,Computer Graphics and Computer-Aided Design ,Feedback arc set ,Combinatorics ,Cycle rank ,Nearest neighbor graph ,010201 computation theory & mathematics ,Random regular graph ,FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,0101 mathematics ,Software ,Pancyclic graph ,Mathematics - Abstract
A classical theorem of Ghouila-Houri from 1960 asserts that every directed graph on $n$ vertices with minimum out-degree and in-degree at least $n/2$ contains a directed Hamilton cycle. In this paper we extend this theorem to a random directed graph ${\mathcal D}(n,p)$, that is, a directed graph in which every ordered pair $(u,v)$ becomes an arc with probability $p$ independently of all other pairs. Motivated by the study of resilience of properties of random graphs, we prove that if $p \gg \log n/\sqrt{n}$, then a.a.s. every subdigraph of ${\mathcal D}(n,p)$ with minimum out-degree and in-degree at least $(1/2 + o(1)) n p$ contains a directed Hamilton cycle. The constant $1/2$ is asymptotically best possible. Our result also strengthens classical results about the existence of directed Hamilton cycles in random directed graphs., Comment: 35 pages, 1 figure
- Published
- 2015
43. Asymptotic distribution of the numbers of vertices and arcs of the giant strong component in sparse random digraphs
- Author
-
Boris Pittel and Daniel J. Poole
- Subjects
Discrete mathematics ,Applied Mathematics ,General Mathematics ,Asymptotic distribution ,Digraph ,0102 computer and information sciences ,Covariance ,01 natural sciences ,Computer Graphics and Computer-Aided Design ,Giant component ,010101 applied mathematics ,Combinatorics ,010201 computation theory & mathematics ,Joint probability distribution ,Order (group theory) ,0101 mathematics ,Realization (systems) ,Software ,Central limit theorem ,Mathematics - Abstract
Two models of a random digraph on n vertices, D(n; Prob(arc) = p) and D(n; number of arcs = m) are studied. In 1990, Karp for D(n;p) and independently T. Luczak for D(n;m = cn) proved that for c > 1, with probability tending to 1, there is an unique strong component of size of order n. Karp showed, in fact, that the giant component has likely size asymptotic to n 2 , where = (c) is the unique positive root of 1 = e c . In this paper we prove that, for both random digraphs, the joint distribution of the number of vertices and number of arcs in the giant strong component is asymptotically Gaussian with the same mean vector n (c), (c) := ( 2 ;c 2 ) and two distinct 2 2 covariance matrices, nB(c) and n B(c) +c( 0 (c)) T ( 0 (c))) . To this end, we introduce and analyze a randomized deletion process which determines the directed (1; 1)-core, the maximal digraph with minimum in-degree and out-degree at least 1. This (1; 1)-core contains all nontrivial strong components. However, we show that the likely numbers of peripheral vertices and arcs in the (1; 1)-core, those outside the largest strong component, are of polylog order, thus dwarfed by anticipated uctuations, on the scale of n 1=2 , of the giant component parameters. By approximating the likely realization of the deletion algorithm with a deterministic trajectory, we obtain our main result via exponential supermartingales and Fourier-based techniques.
- Published
- 2015
44. Fast tensor method for summation of long-range potentials on 3D lattices with defects
- Author
-
Boris N. Khoromskij and Venera Khoromskaia
- Subjects
Discrete mathematics ,Tensor contraction ,Algebra and Number Theory ,Applied Mathematics ,Mathematical analysis ,Tensor product of Hilbert spaces ,010103 numerical & computational mathematics ,01 natural sciences ,Tensor field ,010101 applied mathematics ,Tensor product ,Cartesian tensor ,Symmetric tensor ,Tensor ,0101 mathematics ,Tensor density ,Mathematics - Abstract
Summary In this paper, we present a method for fast summation of long-range potentials on 3D lattices with multiple defects and having non-rectangular geometries, based on rank-structured tensor representations. This is a significant generalization of our recent technique for the grid-based summation of electrostatic potentials on the rectangular L × L × L lattices by using the canonical tensor decompositions and yielding the O(L) computational complexity instead of O(L3) by traditional approaches. The resulting lattice sum is calculated as a Tucker or canonical representation whose directional vectors are assembled by the 1D summation of the generating vectors for the shifted reference tensor, once precomputed on large N × N × N representation grid in a 3D bounding box. The tensor numerical treatment of defects is performed in an algebraic way by simple summation of tensors in the canonical or Tucker formats. To diminish the considerable increase in the tensor rank of the resulting potential sum, the ϵ-rank reduction procedure is applied based on the generalized reduced higher-order SVD scheme. For the reduced higher-order SVD approximation to a sum of canonical/Tucker tensors, we prove the stable error bounds in the relative norm in terms of discarded singular values of the side matrices. The required storage scales linearly in the 1D grid-size, O(N), while the numerical cost is estimated by O(NL). The approach applies to a general class of kernel functions including those for the Newton, Slater, Yukawa, Lennard-Jones, and dipole-dipole interactions. Numerical tests confirm the efficiency of the presented tensor summation method; we demonstrate that a sum of millions of Newton kernels on a 3D lattice with defects/impurities can be computed in seconds in Matlab implementation. The tensor approach is advantageous in further functional calculus with the lattice potential sums represented on a 3D grid, like integration or differentiation, using tensor arithmetics of 1D complexity. Copyright © 2015 John Wiley & Sons, Ltd.
- Published
- 2015
45. On the max-cut of sparse random graphs
- Author
-
Quan Li, David Gamarnik, Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science, Sloan School of Management, Gamarnik, David, and Li, Quan
- Subjects
Random graph ,Discrete mathematics ,Applied Mathematics ,General Mathematics ,Maximum cut ,Probability (math.PR) ,Second moment of area ,0102 computer and information sciences ,Expected value ,01 natural sciences ,Computer Graphics and Computer-Aided Design ,Upper and lower bounds ,Combinatorics ,010104 statistics & probability ,010201 computation theory & mathematics ,FOS: Mathematics ,Cubic graph ,Large deviations theory ,Second moment method ,0101 mathematics ,Software ,Mathematics - Probability ,Mathematics - Abstract
We consider the problem of estimating the size of a maximum cut (Max-Cut problem) in a random Erd\H{o}s-R\'{e}nyi graph on $n$ nodes and $\lfloor cn \rfloor$ edges. It is shown in Coppersmith et al. ~\cite{Coppersmith2004} that the size of the maximum cut in this graph normalized by the number of nodes belongs to the asymptotic region $[c/2+0.37613\sqrt{c},c/2+0.58870\sqrt{c}]$ with high probability (w.h.p.) as $n$ increases, for all sufficiently large $c$. In this paper we improve both upper and lower bounds by introducing a novel bounding technique. Specifically, we establish that the size of the maximum cut normalized by the number of nodes belongs to the interval $[c/2+0.47523\sqrt{c},c/2+0.55909\sqrt{c}]$ w.h.p. as $n$ increases, for all sufficiently large $c$. Instead of considering the expected number of cuts achieving a particular value as is done in the application of the first moment method, we observe that every maximum size cut satisfies a certain local optimality property, and we compute the expected number of cuts with a given value satisfying this local optimality property. Estimating this expectation amounts to solving a rather involved two dimensional large deviations problem. We solve this underlying large deviation problem asymptotically as $c$ increases and use it to obtain an improved upper bound on the Max-Cut value. The lower bound is obtained by application of the second moment method, coupled with the same local optimality constraint, and is shown to work up to the stated lower bound value $c/2+0.47523\sqrt{c}$. It is worth noting that both bounds are stronger than the ones obtained by standard first and second moment methods. Finally, we also obtain an improved lower bound of $1.36000n$ on the Max-Cut for the random cubic graph or any cubic graph with large girth, improving the previous best bound of $1.33773n$., Comment: To appear in Random Structures & Algorithms
- Published
- 2017
46. A certain class of weighted statistical convergence and associated Korovkin-type approximation theorems involving trigonometric functions
- Author
-
Hari M. Srivastava, Umakanta Misra, Susanta Kumar Paikray, and Bidu Bhusan Jena
- Subjects
Dominated convergence theorem ,Discrete mathematics ,Weak convergence ,General Mathematics ,Uniform convergence ,Normal convergence ,010102 general mathematics ,General Engineering ,01 natural sciences ,010101 applied mathematics ,Rate of convergence ,Applied mathematics ,Convergence tests ,0101 mathematics ,Modes of convergence ,Compact convergence ,Mathematics - Abstract
The subject of statistical convergence has attracted a remarkably large number of researchers due mainly to the fact that it is more general than the well-established theory of the ordinary (classical) convergence. In the year 2013, Edely et al[17] introduced and studied the notion of weighted statistical convergence. In our present investigation, we make use of the (presumably new) notion of the deferred weighted statistical convergence to present Korovkin-type approximation theorems associated with the periodic functions 1,cosx, and sinx defined on a Banach space C2π(R). In particular, we apply our concept of the deferred weighted statistical convergence with a view to proving a Korovkin-type approximation theorem for periodic functions and also to demonstrate that our result is a nontrivial extension of several known Korovkin-type approximation theorems which were given in earlier works. Moreover, we establish another result for the rate of the deferred weighted statistical convergence for the same set of functions. Finally, we consider a number of interesting special cases and illustrative examples in support of our definitions and of the results which are presented in this paper.
- Published
- 2017
47. σgi[xi]/m/s/k queues with mixed batch renewal inputs
- Author
-
Fumiaki Machihara
- Subjects
Discrete mathematics ,Queueing theory ,Distribution (number theory) ,Computer Networks and Communications ,Log-Cauchy distribution ,Markov process ,Asymptotic distribution ,Variance-gamma distribution ,symbols.namesake ,Categorical distribution ,symbols ,Piecewise ,Applied mathematics ,Electrical and Electronic Engineering ,Mathematics - Abstract
This paper presents the analysis for the finite capacity queueing model with two independent mixed batch renewal inputs. The analysis is presented for the steady-state distribution at an arbitrary time and the steady-state distribution immediately before the arrival for each type of customers. The results can be applied to the models of various kinds of strategies such as delay-delay, delay-loss and loss-loss. The structure of this paper is as follows. First, a simple numerical calculation procedures is proposed for the distribution at an arbitrary time which, compared with past methods, drastically reduces the computational complexity. Then the relationship is established between the distribution at an arbitrary time and the distribution immediately before the arrival, using the rate conservation principle in the theory of piecewise Markov process. Using this relationship, one distribution can easily be derived from the other. The individual blocking probabilities, which are the most important performance measures, are derived from the distribution immediately before the arrival. Finally, several examples are presented in order to discuss the effects of the interarrival distribution and the batch-size distribution on the individual blocking probabilities.
- Published
- 1987
48. A constructive approach to the analysis of nonlinear resistive circuits based on the fixed point algorithm theory
- Author
-
Regular Members Kazuo Horiuchi, Shin'ichi Oishi, Regular Member Yuzo Sumi, and Tadaaki Takase
- Subjects
Discrete mathematics ,Nonlinear system ,Resistive touchscreen ,Degree (graph theory) ,Basis (linear algebra) ,Computer Networks and Communications ,Applied mathematics ,Electrical and Electronic Engineering ,Unified field theory ,Resistive circuits ,Constructive ,Mathematics ,Network analysis - Abstract
The existence problem for solution of a nonlinear resistive circuit and the problem of identifying the number of the solutions are classic and basic problems in circuit theory. In their paper “On the application of degree theory to the analysis of resistive nonlinear networks” (Int. J. Cir. Theor. Appl., 5, pp. (1977)), Chua and Wang presented a unified theory for the existence of solutions for nonlinear circuit equations. That is, on the basis of the degree theory the existence of solutions of many nonlinear resistive circuits can be guaranteed in a unified manner by showing that the circuit equations are homotopic to certain odd fields. Their arguments are, however, not constructive. In this paper, an algorithm based on the fixed-point algorithm theory is presented and it is proved that by this algorithm at least one solution can always be constructed for nonlinear circuit equations whose solutions are guaranteed to exist by Chua and Wang's theorems. Usefulness of the algorithm is also demonstrated by a few examples.
- Published
- 1985
49. Sampling theorems using nonuniform sample points and interpolation functions with band-limited continuous spectra
- Author
-
Takuro Kida and Keiichi Akagawa
- Subjects
Discrete mathematics ,Sampling (signal processing) ,Sampling design ,Nonuniform sampling ,Slice sampling ,Nyquist–Shannon sampling theorem ,Applied mathematics ,Oversampling ,Electrical and Electronic Engineering ,Importance sampling ,Mathematics ,Interpolation - Abstract
This paper presents a unified theory for the nonuniform sampling theorem for the low-pass band-limited waveform. In most practical cases, the mean interval of the sampling points is in the so-called oversampling state. One can also assume that there exists a certain period in the sampling point sequence. Those properties of the sampling point sequence are assumed in this paper. Yen has derived a sampling theorem for the case where the sampling-point sequence has a period. In his theorem, how ever, the interpolation function has a spectrum which is a stepwise discontinuous function, not suited to the realization of the interpolation function by a digital or other similar filters. One of the greatest features of the sampling theorem proposed in this paper is that the interpolation function has a continuous spectrum. the problem has been discussed by one of the authors for the case where the sampling frequency and the band-end frequency of the waveform are in an integer ratio. In this paper, the sampling theorem is derived in a unified and integrated form without imposing such a condition. the variance of the approximation error is also derived for the case where a statistically independent additive error is superposed on the sampled value, and it is shown that the proposed sampling theorem is better in that respect. the discussion is extended to the multidimensional band-limited waveform, and a sampling theorem is shown which has an interpolation function with a continuous spectrum.
- Published
- 1989
50. Nonharmonic fourier series and the stabilization of distributed semi-linear control systems
- Author
-
M. Slemrod and J. M. Ball
- Subjects
Discrete mathematics ,Applied Mathematics ,General Mathematics ,Hilbert space ,Linear control systems ,Bilinear interpolation ,Lipschitz continuity ,Graph ,Linear map ,symbols.namesake ,Norm (mathematics) ,symbols ,Fourier series ,Mathematics - Abstract
ii(t)+Au(t)+p(t) B(u(t)) =O. Here A is a densely defined positive selfadjoint linear operator on a real Hilbert space H with inner product ( , ), B is a locally Lipschitz map from D(A”2) (endowed with the graph norm) into H, and p(t) is a real-valued control. The finite-dimensional stabilization problem H = IW” has been considered in the recent papers of Jurdjevic and Quinn [20] and Slemrod [24]. In the case when (1.1) is bilinear, i.e., B linear, these papers give simple criteria for feedback stabilization. Specifically, it is a consequence of both [20] and [24] that if the only solution of the uncontrolled system
- Published
- 1979
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.