578 results
Search Results
2. A Note on A Paper of Cellina Concerning Differential Equations in Banach Spaces
- Author
-
M. Kunze
- Subjects
Discrete mathematics ,Pure mathematics ,Approximation property ,General Mathematics ,Eberlein–Šmulian theorem ,Infinite-dimensional vector function ,Banach space ,Interpolation space ,Banach manifold ,Lp space ,C0-semigroup ,Mathematics - Published
- 1996
3. Note on a Paper by G. J. Rieger
- Author
-
Doug Hensley
- Subjects
Combinatorics ,Discrete mathematics ,General Mathematics ,Mathematics - Abstract
Let c e IN. For d e ℤ with gcd (d, c) = 1 let δ(d, c) be defined by d · δ(d, c) 1 mod c, 1 ⩽ δ(d, c) ⩽ c. Let s, t e IN with 1 ⩽ s ⩽ c, 1 ⩽ t ⩽ c. The main result is that for arbitrary fixed e > 0, but uniformly over c, s and t Equivalently, the points (d, δ(c,d)) are approximately uniformly distributed in [0, c] × [0, c]: The two-dimensional discrepancy of {(d,δ (c, d)): 1 ⩽ d ⩽ c and (c, d)= 1} in [0,c] × [0,c] is Oe(ce-1/2).
- Published
- 1996
4. Some Remarks on a Paper of A. F. Beardon and P. L. Waterman about Strongly Discrete Subgroups of SL(2, C)
- Author
-
Gerhard Rosenberger
- Subjects
Discrete mathematics ,Combinatorics ,General Mathematics ,Mathematics - Published
- 1983
5. Relations Between the Divisors of the First n Natural Numbers: (Second Paper.)
- Author
-
J. W. L. Glaisher
- Subjects
Discrete mathematics ,Pure mathematics ,Practical number ,Amicable numbers ,General Mathematics ,Natural number ,Quasiperfect number ,Table of divisors ,Refactorable number ,Mathematics - Abstract
n/a
- Published
- 1908
6. Remarks on my paper 'The radical property of rings such that every homomorphic image has no nonzero left annihilators'
- Author
-
Ferenc A. Szász
- Subjects
Discrete mathematics ,Property (philosophy) ,General Mathematics ,Homomorphic encryption ,Mathematics ,Image (mathematics) - Published
- 1974
7. Addendum to Jukes' Paper on Tauberian Theorems of Landau-Ingham Type
- Author
-
S. L. Segal
- Subjects
Discrete mathematics ,General Mathematics ,Addendum ,Type (model theory) ,Abelian and tauberian theorems ,Mathematics - Published
- 1974
8. A Note on Tutte's Paper 'The Factorization of Linear Graphs'*
- Author
-
F. G. Maunsell
- Subjects
Combinatorics ,Discrete mathematics ,Factorization ,General Mathematics ,Tutte 12-cage ,Nowhere-zero flow ,Tutte matrix ,Chromatic polynomial ,Tutte theorem ,Mathematics - Published
- 1952
9. Remark on a Paper of Erdös and Turán
- Author
-
A. Makowski
- Subjects
Discrete mathematics ,General Mathematics ,Mathematics - Published
- 1959
10. Virtual χ−y‐genera of Quot schemes on surfaces
- Author
-
Woonam Lim
- Subjects
Discrete mathematics ,Mathematics - Algebraic Geometry ,Mathematics::Algebraic Geometry ,010308 nuclear & particles physics ,General Mathematics ,010102 general mathematics ,0103 physical sciences ,0101 mathematics ,Mathematics::Symplectic Geometry ,01 natural sciences ,14N99 (primary), 14J80 (secondary) ,Mathematics - Abstract
This paper studies the virtual $\chi_{-y}$-genera of Grothendieck's Quot schemes on surfaces, thus refining the calculations of the virtual Euler characteristics by Oprea-Pandharipande. We first prove a structural result expressing the equivariant virtual $\chi_{-y}$-genera of Quot schemes universally in terms of the Seiberg-Witten invariants. The formula is simpler for curve classes of Seiberg-Witten length $N$, which are defined in the paper. By way of application, we give complete answers in the following cases: (i) arbitrary surfaces for the zero curve class, (ii) relatively minimal elliptic surfaces for rational multiples of the fiber class, (iii) minimal surfaces of general type with $p_g>0$ for any curve classes. Furthermore, a blow up formula is obtained for curve classes of Seiberg-Witten length $N$. As a result of these calculations, we prove that the generating series of the virtual $\chi_{-y}$-genera are given by rational functions for all surfaces with $p_g>0$, addressing a conjecture of Oprea-Pandharipande. In addition, we study the reduced $\chi_{-y}$-genera for $K3$ surfaces and primitive curve classes with connections to the Kawai-Yoshioka formula., Comment: 48 pages. Reformulation of Theorem 1 for readability. Extra explanation for the mixed terms in section 2.2.3. Reference updates
- Published
- 2021
11. Haar null and Haar meager sets: a survey and new results
- Author
-
Donát Nagy and Márton Elekes
- Subjects
Discrete mathematics ,General Mathematics ,010102 general mathematics ,Null (mathematics) ,Haar ,Survey result ,Locally compact space ,0101 mathematics ,01 natural sciences ,Mathematics - Abstract
We survey results about Haar null subsets of (not necessarily locally compact) Polish groups. The aim of this paper is to collect the fundamental properties of the various possible definitions of Haar null sets, and also to review the techniques that may enable the reader to prove results in this area. We also present several recently introduced ideas, including the notion of Haar meager sets, which are closely analogous to Haar null sets. We prove some results in a more general setting than that of the papers where they were originally proved and prove some results for Haar meager sets which were already known for Haar null sets.
- Published
- 2020
12. Integral inequalities for n-polynomial s-type preinvex functions with applications
- Author
-
Muhammad Tariq, Muhammad Nadeem, Saad Ihsan Butt, Hüseyin Budak, and [Belirlenecek]
- Subjects
Discrete mathematics ,Polynomial ,lder&apos ,Inequality ,Hö ,Invexity ,General Mathematics ,media_common.quotation_subject ,General Engineering ,Í ,Generation ,lder– ,polynomial s‐ ,type preinvexity ,s inequality ,Convexity ,improved power mean integral inequality ,s‐ ,n‐ ,scan inequality ,media_common ,Mathematics ,preinvex function - Abstract
In this present paper, we introduce the idea and concept of n-polynomial s-type preinvex functions. We elaborate and investigate the algebraic properties of the newly introduced definition and discuss their connections and relations with convex functions. We find the new sort of Hermite-Hadamard inequality via a newly introduced definition. Furthermore, some refinements of Hermite-Hadamard inequality are given. Finally, we investigated some applications via this newly introduced definition. The results obtained in this paper can be viewed as significant improvement of previously known results. H.E.C. Pakistan under NRPU project [7906] The research of the author Saad Ihsan Butt has been fully supported by H.E.C. Pakistan under NRPU project 7906. WOS:000649589100001 2-s2.0-85105631491
- Published
- 2021
13. 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
14. Bounds for Shannon and Zipf-Mandelbrot entropies
- Author
-
Muhammad Adil Khan, Đilda Pečarić, and Josip Pečarić
- Subjects
convex function ,Jensen inequality ,Shannon entropy ,Zipf-Mandelbrot entropy ,Discrete mathematics ,Mathematics::Dynamical Systems ,Shannon's source coding theorem ,General Mathematics ,010102 general mathematics ,General Engineering ,Maximum entropy thermodynamics ,Min entropy ,Entropy in thermodynamics and information theory ,01 natural sciences ,010101 applied mathematics ,Rényi entropy ,Entropy power inequality ,Combinatorics ,0101 mathematics ,Entropic uncertainty ,Limiting density of discrete points ,Mathematics - Abstract
Shannon and Zipf-Mandelbrot entropies have many applications in many applied sciences, for example, in information theory, biology and economics, etc. In this paper, we consider two refinements of the well-know Jensen inequality and obtain different bounds for Shannon and Zipf-Mandelbrot entropies. First of all, we use some convex functions and manipulate the weights and domain of the functions and deduce results for Shannon entropy. We also discuss their particular cases. By using Zipf-Mandelbrot laws for different parameters in Shannon entropies results, we obtain bounds for Zipf-Mandelbrot entropy. The idea used in this paper for obtaining the results may stimulate further research in this area, particularly for Zipf-Mandelbrot entropy.
- Published
- 2017
15. 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
16. On Ahlfors–David regular weighted bounds for the extension operator associated to the circle
- Author
-
Tuomas Orponen
- Subjects
Discrete mathematics ,symbols.namesake ,Operator (computer programming) ,Fourier transform ,Mathematics - Classical Analysis and ODEs ,General Mathematics ,Classical Analysis and ODEs (math.CA) ,FOS: Mathematics ,symbols ,Point (geometry) ,Extension (predicate logic) ,16. Peace & justice ,Mathematics - Abstract
This paper addresses the sharpness of a weighted $L^{2}$-estimate for the Fourier extension operator associated to the circle, obtained by J. Bennett, A. Carbery, F. Soria and A. Vargas in 2006. A point left open in their paper was the necessity of a certain $\log R$-factor in the bound. Here, I show that the factor is necessary for all $1/2$-Ahlfors-David regular weights on the circle, but it can be removed for $s$-Ahlfors-David regular weights with $s \neq 1/2$., 12 pages
- Published
- 2015
17. 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
18. Hyponormality of bounded-type Toeplitz operators
- Author
-
Raúl E. Curto, In Sung Hwang, and Woo Young Lee
- Subjects
Discrete mathematics ,Mathematics::Functional Analysis ,Mathematics::Operator Algebras ,General Mathematics ,Rational function ,Divisor (algebraic geometry) ,Function (mathematics) ,Hardy space ,Bounded type ,Toeplitz matrix ,symbols.namesake ,Symbol (programming) ,symbols ,Mathematics - Abstract
In this paper we deal with the hyponormality of Toeplitz operators with matrix-valued symbols. The aim of this paper is to provide a tractable criterion for the hyponormality of bounded-type Toeplitz operators (i.e., the symbol is a matrix-valued function such that Φ and are of bounded type). In particular, we get a much simpler criterion for the hyponormality of when the co-analytic part of the symbol Φ is a left divisor of the analytic part.
- Published
- 2014
19. 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
20. On the existence of low-diaphony sequences made of digital sequences and lattice point sets
- Author
-
Peter Kritzer and Friedrich Pillichshammer
- Subjects
Discrete mathematics ,Set (abstract data type) ,Function space ,General Mathematics ,Point (geometry) ,Mathematics - Abstract
In this paper, we discuss hybrid point sets built from two of the most prominent classes of sequences used in quasi-Monte Carlo methods. We derive an existence result on point sets with low diaphony, where the components of the points involved stem from a digital (t, s)-sequence on the one hand, and from a lattice point set on the other. Moreover, we outline how the hybrid diaphony of the point sets considered in this paper relates to the worst-case integration error in suitable function spaces.
- Published
- 2012
21. 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
22. 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
23. 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
24. ON LINEAR COMBINATIONS OF UNITS WITH BOUNDED COEFFICIENTS
- Author
-
Volker Ziegler and Jörg M. Thuswaldner
- Subjects
Discrete mathematics ,Degree (graph theory) ,Generalization ,General Mathematics ,010102 general mathematics ,010103 numerical & computational mathematics ,Algebraic number field ,Mathematical proof ,01 natural sciences ,Integer ,Bounded function ,0101 mathematics ,Algebraic number ,Linear combination ,Mathematics - Abstract
Starting with a paper of Jacobson from the 1960s, many authors became interested in characterizing all algebraic number fields in which each integer is the sum of pairwise distinct units. Although there exist many partial results for number fields of low degree, a full characterization of these number fields is still not available. Narkiewicz and Jarden posed an analogous question for sums of units that are not necessarily distinct. In this paper we propose a generalization of these problems. In particular, for a given rational integer n we consider the following problem. Characterize all number fields for which every integer is a linear combination of finitely many units e i in a way that the coefficients a i ∈ℕ are bounded by n . The paper gives several partial results on this problem. In our proofs we exploit the fact that these representations are related to symmetric beta expansions with respect to Pisot bases.
- Published
- 2011
25. Degenerate elliptic operators, Feller semigroups and modified Bernstein-Schnabl operators
- Author
-
Francesco Altomare, Sabrina Diomede, and Mirella Cappelletti Montano
- Subjects
Discrete mathematics ,Semi-elliptic operator ,Elliptic operator ,Iterated function ,Semigroup ,General Mathematics ,Special classes of semigroups ,Operator theory ,Domain (mathematical analysis) ,Fourier integral operator ,Mathematics - Abstract
In this paper we study a class of elliptic second-order differential operators on finite dimensional convex compact sets whose principal part degenerates on a subset of the boundary of the domain. We show that the closures of these operators generate Feller semigroups. Moreover, we approximate these semigroups by iterates of suitable positive linear operators which we also introduce and study in this paper for the first time, and which we refer to as modified Bernstein-Schnabl operators. As a consequence of this approximation we investigate some regularity properties preserved by the semigroup. Finally, we consider the special case of the finite dimensional simplex and the well-known Wright-Fisher diffusion model of gene frequency used in population genetics. © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim
- Published
- 2011
26. Hamiltonian cycles in the generating graphs of finite groups
- Author
-
Attila Maróti, Gábor P. Nagy, Thomas Breuer, Robert M. Guralnick, and Andrea Lucchini
- Subjects
Normal subgroup ,Discrete mathematics ,General Mathematics ,010102 general mathematics ,0102 computer and information sciences ,01 natural sciences ,Hamiltonian path ,Graph ,Vertex (geometry) ,Combinatorics ,symbols.namesake ,Subgroup ,010201 computation theory & mathematics ,Solvable group ,Simple group ,finite simple groups ,symbols ,generating graphs of finite groups ,0101 mathematics ,Mathematics - Abstract
For a flnite group G let i(G) denote the graph deflned on the non- identity elements of G in such a way that two distinct vertices are connected by an edge if and only if they generate G. In this paper it is shown that the graph i(G) contains a Hamiltonian cycle for many flnite groups G. In the literature many deep results about flnite simple groups G can equivalently be stated as theorems about i(G). Three examples are given. Guralnick and Shalev (10) showed that for su-ciently large G the graph i(G) has diameter at most 2. Guralnick and Kantor (9) showed that there is no isolated vertex in i(G). Finally, Breuer, Guralnick, Kantor (4) showed that the diameter of i(G) is at most 2 for all G. In this paper those flnite groups G are considered for which i(G) contains a Hamiltonian cycle. The following proposition reduces the investigations to those non-solvable groups G for which G=N is cyclic for any non-trivial normal subgroup N of G. Proposition 1.1. Let G be a flnite solvable group that has at least 4 elements. Then the graph i(G) contains a Hamiltonian cycle if and only if G=N is cyclic for all non-trivial normal subgroups N of G. The three main results of this paper are Theorems 1.2, 1.3, and 1.4.
- Published
- 2010
27. An extension of Buchberger’s criteria for Gröbner basis decision
- Author
-
John Perry
- Subjects
Discrete mathematics ,Polynomial ,Class (set theory) ,Mathematics::Commutative Algebra ,Basis (linear algebra) ,General Mathematics ,Extension (predicate logic) ,Characterization (mathematics) ,Commutative Algebra (math.AC) ,Mathematics - Commutative Algebra ,Set (abstract data type) ,Mathematics - Algebraic Geometry ,Gröbner basis ,Computational Theory and Mathematics ,FOS: Mathematics ,Computer Science::Symbolic Computation ,Ideal (order theory) ,Algebraic Geometry (math.AG) ,13P10 ,Mathematics - Abstract
Two fundamental questions in the theory of Groebner bases are decision ("Is a basis G of a polynomial ideal a Groebner basis?") and transformation ("If it is not, how do we transform it into a Groebner basis?") This paper considers the first question. It is well-known that G is a Groebner basis if and only if a certain set of polynomials (the S-polynomials) satisfy a certain property. In general there are m(m-1)/2 of these, where m is the number of polynomials in G, but criteria due to Buchberger and others often allow one to consider a smaller number. This paper presents two original results. The first is a new characterization theorem for Groebner bases that makes use of a new criterion that extends Buchberger's Criteria. The second is the identification of a class of polynomial systems G for which the new criterion has dramatic impact, reducing the worst-case scenario from m(m-1)/2 S-polynomials to m-1., 20 pages, 2 figures
- Published
- 2010
28. Variant sandwich pairs
- Author
-
Martin Schechter
- Subjects
Discrete mathematics ,Combinatorics ,Set (abstract data type) ,Sequence ,Partial differential equation ,Development (topology) ,General Mathematics ,Bounded function ,Mathematics - Abstract
Since the development of the calculus of variations there has been interest in finding critical points of functionals. This was intensified by the fact that for many equations arising in practice, the solutions are critical points. In searching for such points, there is a distinct advantage if the functional G is semibounded. In this case one can find a Palais-Smale (PS) sequence G (uk) c, G ′(uk) 0 or even a Cerami sequence G (uk) c, (1 + ‖uk ‖)G ′(uk) 0. These sequences produce critical points if they have convergent subsequences. However, there is no clear method of finding critical points of functionals which are not semibounded. Linking subsets do provide such a method. They can produce a PS sequence provided they separate the functional. In previous papers we have shown that there are pairs of subsets that can produce Cerami-like sequences even though they do not separate the functional. We call such sets sandwich pairs. All that is required is that the functional be bounded from above on one ofthe sets and bounded from below on the other, with no relationship needed between the bounds. This provides a distinct advantage in applications. The present paper discusses the situation in which one cannot find linking subsets which separate the functional or sandwich pairs for which the functional is bounded below on one set and bounded above on the other. We develop a method which can deal with such situations. We apply the method to problems in partial differential equations (© 2010 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)
- Published
- 2010
29. Banach Lie algebras with Lie subalgebras of finite codimension have Lie ideals
- Author
-
Edward Kissin, Victor S. Shulman, and Yurii V. Turovskii
- Subjects
Discrete mathematics ,Pure mathematics ,Adjoint representation of a Lie algebra ,Representation of a Lie group ,Mathematics::Commutative Algebra ,General Mathematics ,Simple Lie group ,Adjoint representation ,Real form ,Killing form ,Lie conformal algebra ,Graded Lie algebra ,Mathematics - Abstract
This paper continues the work started in [E. Kissin, V. S. Shulman and Yu. V. Turovskii, �Banach Lie algebras with Lie subalgebras of finite codimension: their invariant subspaces and Lie ideals�, J. Funct. Anal. 256 (2009) 323�351.] and is devoted to the study of reducibility of an infinite-dimensional Lie algebra of operators on a Banach space when its Lie subalgebra of finite codimension has an invariant subspace of finite codimension. In addition to the tools developed in the above paper; filtrations of Banach spaces with respect to Lie algebras of operators and related systems of operators on graded Banach spaces, the present paper introduces and studies some new concepts and techniques: the theory of Lie quasi-ideals and properties of Lie nilpotent finite-dimensional subspaces of Banach associative algebras. The application of these techniques to an operator Lie algebra L shows that, under some mild additional assumptions, L is reducible if its Lie subalgebra of finite codimension has an invariant subspace of finite codimension. This, in turn, leads to the main result of the paper: if a Banach Lie algebra L has a closed Lie subalgebra of finite codimension, then it has a proper closed Lie ideal of finite codimension. Moreover, if L is non-commutative, then it has a characteristic Lie ideal of finite codimension, that is, a proper closed Lie ideal of L invariant for all bounded derivations of L.
- Published
- 2009
30. Discrete characterisations of Lipschitz spaces on fractals
- Author
-
Mats Bodin
- Subjects
Discrete mathematics ,Harmonic function ,Function space ,General Mathematics ,Piecewise ,Metric map ,Interpolation space ,Birnbaum–Orlicz space ,Lipschitz continuity ,Mathematics ,Sierpinski triangle - Abstract
This thesis consists of three papers, all of them on the topic of function spaces on fractals.The papers summarised in this thesis are:Paper I Mats Bodin, Wavelets and function spaces on Mauldin-Williams fractals, Research Report in Mathematics No. 7, Umea University, 2005.Paper II Mats Bodin, Harmonic functions and Lipschitz spaces on the Sierpinski gasket, Research Report in Mathematics No. 8, Umea University, 2005.Paper III Mats Bodin, A discrete characterisation of Lipschitz spaces on fractals, Manuscript.The first paper deals with piecewise continuous wavelets of higher order in Besov spaces defined on fractals. A. Jonsson has constructed wavelets of higher order on fractals, and characterises Besov spaces on totally disconnected self-similar sets, by means of the magnitude of the coefficients in the wavelet expansion of the function. For a class of fractals, W. Jin shows that such wavelets can be constructed by recursively calculating moments. We extend their results to a class of graph directed self-similar fractals, introduced by R. D. Mauldin and S. C. Williams.In the second paper we compare differently defined function spaces on the Sierpinski gasket. R. S. Strichartz proposes a discrete definition of Besov spaces of continuous functions on self-similar fractals having a regular harmonic structure. We identify some of them with Lipschitz spaces introduced by A. Jonsson, when the underlying domain is the Sierpinski gasket. We also characterise some of these spaces by means of the magnitude of the coefficients of the expansion of a function in a continuous piecewise harmonic base.The last paper gives a discrete characterisation of certain Lipschitz spaces on a class of fractal sets. A. Kamont has discretely characterised Besov spaces on intervals. We give a discrete characterisation of Lipschitz spaces on fractals admitting a type of regular sequence of triangulations, and for a class of post critically finite self-similar sets. This shows that, on some fractals, certain discretely defined Besov spaces, introduced by R. Strichartz, coincide with Lipschitz spaces introduced by A. Jonsson and H. Wallin for low order of smoothness.
- Published
- 2008
31. A new constraint qualification for the formula of the subdifferential of composed convex functions in infinite dimensional spaces
- Author
-
Radu Ioan Boţ, Gert Wanka, and Sorin-Mihai Grad
- Subjects
Convex analysis ,Discrete mathematics ,Effective domain ,General Mathematics ,Mathematical analysis ,Convex set ,Proper convex function ,Convex combination ,Subderivative ,Convex conjugate ,Pseudoconvex function ,Mathematics - Abstract
In this paper we work in separated locally convex spaces where we give equivalent statements for the formulae of the conjugate function of the sum of a convex lower-semicontinuous function and the precomposition of another convex lower-semicontinuous function which is also K -increasing with a K -convex K -epi-closed function, where K is a nonempty closed convex cone. These statements prove to be the weakest constraint qualifications given so far under which the formulae for the subdifferential of the mentioned sum of functions are valid. Then we deliver constraint qualifications inspired from them that guarantee some conjugate duality assertions. Two interesting special cases taken from the literature conclude the paper. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)
- Published
- 2008
32. Languages of k -interval exchange transformations
- Author
-
Sébastien Ferenczi and Luca Q. Zamboni
- Subjects
Discrete mathematics ,General Mathematics ,Interval (graph theory) ,Characterization (mathematics) ,Probability vector ,Mathematics ,Unit interval - Abstract
This paper gives a complete characterization of those sequences of subword complexity (k −1)n+1 which are natural codings of orbits of k-interval exchange transfor- mations, thereby answering an old question of Rauzy. Interval exchange transformations were originally introduced by Oseledec (17), following an idea of Arnold (1), see also (9); an exchange of k intervals, denoted throughout this paper by I, is given by a probability vector of k lengths (�1,...,�k) together with two permutations (�0,�1) on k letters. The unit interval is partitioned into k subintervals of lengths �1,...,�k which are ordered according to � −1 0 and then rearranged by I according to � −1
- Published
- 2008
33. Projective modules for Frobenius kernels and finite Chevalley groups
- Author
-
Zongzhu Lin and Daniel K. Nakano
- Subjects
Discrete mathematics ,Pure mathematics ,Morphism ,Finite field ,Group of Lie type ,General Mathematics ,Algebraic group ,Projective space ,Projective linear group ,Pencil (mathematics) ,Mathematics ,Twisted cubic - Abstract
Let G be a connected reductive algebraic group with a Frobenius morphism F: G → G defined over a finite field □ pr . The main result of the paper is to prove that any rational G-module M which is projective when restricted to the Frobenius kernel G r = Ker(F) is also projective over the split and twisted finite Chevalley groups. In 1987, Parshall conjectured this statement for r = 1 in the split case. The authors verified this in 1999 with the possible exclusion of primes 2 and 3 in non-simply laced cases. The converse of the main result is also discussed for split groups in this paper.
- Published
- 2007
34. Semigroup approach for identification of the unknown diffusion coefficient in a quasi-linear parabolic equation
- Author
-
Ebru Ozbilge and Ali Demir
- Subjects
Discrete mathematics ,Integral representation ,Semigroup ,General Mathematics ,General Engineering ,Boundary (topology) ,Inverse ,symbols.namesake ,Dirichlet boundary condition ,symbols ,Quasi linear ,Boundary value problem ,Diffusion (business) ,Mathematical physics ,Mathematics - Abstract
This article presents a semigroup approach for the mathematical analysis of the inverse coefficient problems of identifying the unknown coefficient k(u(x, t)) in the quasi-linear parabolic equation u t (x, t) = (k(u(x, t))u x (x, t)) x , with Dirichlet boundary conditions u(0, t) = ψ 0 , u(1,t) = ψ 1 . The main purpose of this paper is to investigate the distinguishability of the input-output mappings Φ[·]: K →C 1 [0, T], Ψ[·]: Κ → C 1 [0, T] via semigroup theory. In this paper, it is shown that if the null space of the semigroup T(t) consists of only zero function, then the input-output mappings Φ[·] and Ψ[·] have the distinguishability property. It is also shown that the types of the boundary conditions and the region on which the problem is defined play an important role in the distinguishability property of these mappings. Moreover, under the light of measured output data (boundary observations) f(t):=k(u(0, t))u x (0, t) or/and h(t):=k (u(1,t))u x (1, t), the values k(ψ 0 ) and k(ψ 1 ) of the unknown diffusion coefficient k(u(x,t)) at (x, t) = (0,0) and (x,t) = (1,0), respectively, can be determined explicitly. In addition to these, the values k u (ψ 0 ) and k u (ψ 1 ) of the unknown coefficient k(u(x, t)) at (x,t)=(0,0) and (x, t) = (1, 0), respectively, are also determined via the input data. Furthermore, it is shown that measured output data f(t) and h(t) can be determined analytically by an integral representation. Hence the input-output mappings Φ[·]:Κ→ C 1 [0, T], Ψ[·]:K→ C 1 [0, T] are given explicitly in terms of the semigroup.
- Published
- 2007
35. DERIVED FUNCTORS OF INVERSE LIMITS REVISITED
- Author
-
Jan-Erik Roos
- Subjects
Discrete mathematics ,Pure mathematics ,Derived category ,Derived functor ,General Mathematics ,Functor category ,Mathematics::K-Theory and Homology ,Mathematics::Category Theory ,Natural transformation ,Ext functor ,Inverse limit ,Abelian category ,Adjoint functors ,Mathematics - Abstract
We prove, correct and extend several results of an earlier paper of ours (using and recalling several of our later papers) about the derived functors of projective limit in abelian categories. In particular we prove that if C is an abelian category satisfying the Grothendieck axioms AB3 and AB4* and having a set of generators then the first derived functor of projective limit vanishes on so-called Mittag-Leffler sequences in C. The recent examples given by Deligne and Neeman show that the condition that the category has a set of generators is necessary. The condition AB4* is also necessary, and indeed we give for each integer $m \geq 1$ an example of a Grothendieck category Cm and a Mittag-Leffler sequence in Cm for which the derived functors of its projective limit vanish in all positive degrees except m. This leads to a systematic study of derived functors of infinite products in Grothendieck categories. Several explicit examples of the applications of these functors are also studied.
- Published
- 2006
36. CRESTED PRODUCTS OF ASSOCIATION SCHEMES
- Author
-
R. A. Bailey and Peter J. Cameron
- Subjects
Discrete mathematics ,Combinatorics ,Normal subgroup ,Association scheme ,Wreath product ,General Mathematics ,Equivalence relation ,Distributive lattice ,Permutation group ,Direct product ,Mathematics ,Cyclic permutation - Abstract
The paper defines a new type of product of association schemes (and of the related objects, permutation groups and orthogonal block structures), which generalizes the direct and wreath products (which are referred to as 'crossing' and 'nesting' in the statistical literature). Given two association schemes for , each having an inherent partition (that is, a partition whose equivalence relation is a union of adjacency relations in the association scheme), a product of the two schemes is defined, which reduces to the direct product if or , and to the wreath product if and , where and are the relation of equality and the universal relation on . The character table of the crested product is calculated, and it is shown that, if the two schemes and have formal duals, then so does their crested product (and a simple description of this dual is given). An analogous definition for permutation groups with intransitive normal subgroups is created, and it is shown that the constructions for association schemes and permutation groups are related in a natural way. The definition can be generalized to association schemes with families of inherent partitions, or permutation groups with families of intransitive normal subgroups. This time the correspondence is not so straightforward, and it works as expected only if the inherent partitions (or orbit partitions) form a distributive lattice. The paper concludes with some open problems.
- Published
- 2005
37. BRAUER GROUP INVARIANTS ASSOCIATED TO ORTHOGONAL EPSILON-CONSTANTS
- Author
-
Darren B. Glass
- Subjects
Arithmetic surface ,Discrete mathematics ,Pure mathematics ,Modular representation theory ,Finite group ,Morphism ,Brauer's theorem on induced characters ,General Mathematics ,Invariant (mathematics) ,Brauer group ,Mathematics ,Symplectic geometry - Abstract
In this paper, the theory of e-constants associated to tame finite group actions on arithmetic surfaces is used to define a Brauer group invariant µ(X ,G , V) associated to certain symplectic motives of weight one. The relationship between this invariant and w2(π) (the Galois-theoretic invariant associated to tame covers of surfaces defined by Cassou-Nogues, Erez and Taylor) is also discussed. In his paper (4), Deligne used elements in the Brauer group of Q and their relation- ship with certain e-constants to give a proof of the Frohlich-Queyrut theorem. In particular, he showed that certain global orthogonal root numbers are equal to one, by interpreting the associated local orthogonal root numbers as Stiefel-Whitney classes and then using the local root numbers to define an element of order two in the Brauer group of Q. This idea was furthered by Saito (in (13), for example) and others who defined Brauer group invariants associated to situations which can be interpreted as motives that are orthogonal and of even weight. In this paper, we define a Brauer group invariant associated to certain motives that are symplectic and have weight one. In order to construct the relevant motives, we first define X to be an arithmetic surface of dimension two which is flat, regular, and projective over Z. Throughout this paper, we assume that f : X− →Spec(Z) is the structure morphism. Let G be a finite group that acts tamely on X. In other words, for each closed point x ∈ X, the order of the inertia group of x is relatively prime to the residue characteristic of x .L etY be the quotient scheme X /G, which we assume is regular, and assume that for all finite places v, the fiber Yv =( Xv)/G = Y⊗ Z (Z/p(v)) has normal crossings and smooth irreducible components with multiplicities relatively prime to the residue characteristic of v. Finally, let V be a virtual representation of G over
- Published
- 2005
38. Virtual algebraic Lie theory: Tilting modules and Ringel duals for blob algebras
- Author
-
S. Ryom-Hansen and Paul Martin
- Subjects
Discrete mathematics ,Pure mathematics ,Ring (mathematics) ,Quantum group ,General Mathematics ,Duality (order theory) ,Free module ,Basis (universal algebra) ,Connection (algebraic framework) ,Indecomposable module ,Representation theory ,Mathematics - Abstract
In this paper we construct a representation of the blob algebra [22] over a ring allowing base change to every interesting (i.e. non–semisimple) specialisation which, in quasihereditary specialisations, passes to a full tilting module. The Temperley–Lieb algebras are a tower T0(q) ⊂ T1(q) ⊂ .. of one–parameter finite dimensional algebras [28], each with a basis independent of q. These algebras are quasihereditary [3, 8] except in case q+q = 0. Accordingly one may in principle construct tilting modules, full tilting modules, and corresponding Ringel duals. In fact, if V is a free module of rank 2 over the ground ring then Tn(q) has an action on V , and it is straightforward to show (see later) that V ⊗n is a full tilting module in the quasihereditary cases. Since V ⊗n exists over the ground ring, the Ringel dual can be constructed without having to pick a specialisation. The cases of n finite of this dual are a nested sequence of quotients of the quantum group Uqsl2 [17, 11]. This q–deformable duality and glorious limit structure [16] (more usually observed with Uqsl2 as the starting point) provides the mechanism for massive exchange of representation theoretic information between the two sides [26, 10, 13, 4, 18]. In particular the weight theory of Uqsl2 controls the representation theory of Tn(q) for all n simultaneously (as localisations of a global limit). The blob algebras are a tower b0 ⊂ b1 ⊂ .. of two–parameter finite dimensional algebras (and bn ⊃ Tn(q)). They are quasihereditary except at a finite set of parameter values. Accordingly one may in principle construct tilting modules and so on. Ab initio one would have to expect such a construction to depend on the specialisation, as indecomposable tilting modules do [24]. On the other hand, it turns out [23] that bn has an action on V , and in this paper we show that V ⊗2n is a full tilting module in the quasihereditary cases. Historically, Tn(q) and Uqsl2 were studied extensively separately, before the full tilting module/Ringel duality connection was known, but if one side, and the appropriate full tilting module, had been discovered first, the passage to the Ringel dual would rightly have been regarded as quite a significant spin–off! The bn tilting property of V ⊗2n is a striking result, in as much as it places us in a position analogous to this (as it were, before the discovery of quantum groups).
- Published
- 2004
39. A solution of the isomorphism problem for circulant graphs
- Author
-
Mikhail Muzychuk
- Subjects
Discrete mathematics ,General Mathematics ,Subgraph isomorphism problem ,Combinatorics ,Indifference graph ,Circulant graph ,Chordal graph ,ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION ,Induced subgraph isomorphism problem ,Isomorphism ,Graph isomorphism ,Circulant matrix ,Physics::Atmospheric and Oceanic Physics ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics - Abstract
The isomorphism problem for circulant graphs (Cayley graphs over the cyclic group) which has been open since 1967 is completely solved in this paper. The main result of the paper gives an efficient isomorphism criterion for circulant graphs of arbitrary order. This result also solves an isomorphism problem for colored circulant graphs and some classes of cyclic codes.
- Published
- 2004
40. Stable Model of X0(125)
- Author
-
Ken McMurdy
- Subjects
Discrete mathematics ,Number theory ,Derived algebraic geometry ,Conjecture ,Stable curve ,Computational Theory and Mathematics ,General Mathematics ,Algebraic surface ,Real algebraic geometry ,Geometric invariant theory ,Interpretation (model theory) ,Mathematics - Abstract
In this paper, the components in the stable model of X0(125) over C5 are determined by constructing (in the language of R. Coleman's ‘Stable maps of curves’, to appear in the Kato Volume of Doc. Math.) an explicit semi-stable covering. Empirical data is then offered regarding the placement of certain CM j-invariants in the supersingular disk of X(1) over C5, which suggests a moduli-theoretic interpretation for the components of the stable model. The paper then concludes with a conjecture regarding the stable model of X0(p3) for p > 3, which is as yet unknown.
- Published
- 2004
41. On rank invariance of moment matrices of nonnegative Hermitian-valued Borel measures on the unit circle
- Author
-
Bernd Kirstein, Andreas Lasarow, and Bernd Fritzsche
- Subjects
Combinatorics ,Discrete mathematics ,Matrix (mathematics) ,Sequence ,Unit circle ,Rank (linear algebra) ,Borel hierarchy ,General Mathematics ,Borel measure ,Hermitian matrix ,Orthogonal basis ,Mathematics - Abstract
This paper provides first tools for generalizing the theory of orthogonal rational functions on the unit circle created by Bultheel, Gonzalez-Vera, Hendriksen and Njastad to the matrix case. A crucial part in this generalization is the definition of the spaces of matrix-valued rational functions for which an orthogonal basis is to be constructed. An important feature of the matrix case is that these spaces will be considered simultaneously as left and right modules over the algebra ℂq×q. In this modules we will define simultaneously left and right matrix-valued inner products with the aid of a nonnegative Hermitian-valued q × q Borel measure on the unit circle. Given a sequence (αj)j∈ℕ of complex numbers located in ℂ\ (especially in “good position” with respect to the unit circle) we will introduce a concept of rank for nonnegative Hermitian-valued q × q Borel measures on the unit circle which is based on the Gramian matrix of particular rational matrix-valued functions with prescribed pole structure. A main result of this paper is that this concept of rank is universal. More precisely, it turns out that the rank of a matrix measure does not depend on the given sequence (αj)j∈ℕ. (© 2004 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)
- Published
- 2004
42. BURNS' EQUIVARIANT TAMAGAWA INVARIANT $T\Omega{^{\rm loc}}(N/{\bf Q},1)$ FOR SOME QUATERNION FIELDS
- Author
-
Victor Snaith
- Subjects
Discrete mathematics ,Pure mathematics ,Conjecture ,General Mathematics ,Galois group ,Equivariant map ,Algebraic number field ,Invariant (mathematics) ,Quaternion ,Mathematics - Abstract
Inspired by the work of Bloch and Kato in [ 2 ], David Burns constructed several ‘equivariant Tamagawa invariants’ associated to motives of number fields. These invariants lie in relative $K$ -groups of group-rings of Galois groups, and in [ 3 ] Burns gave several conjectures (see Conjecture 3.1) about their values. In this paper I shall verify Burns' conjecture concerning the invariant $T\Omega^{\rm loc}( N/{\bf Q},1)$ for some families of quaternion extensions $N/{\bf Q}$ . Using the results of [ 9 ] I intend in a subsequent paper to verify Burns' conjecture for those families of quaternion fields which are not covered here.
- Published
- 2003
43. 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
44. MACKEY FORMULA IN TYPE A (Proc. London Math. Soc. (3) 80 (2000) 545–574)
- Author
-
Cédric Bonnafé
- Subjects
Discrete mathematics ,General Mathematics ,010102 general mathematics ,0103 physical sciences ,010307 mathematical physics ,0101 mathematics ,Type (model theory) ,01 natural sciences ,Mathematics - Abstract
The statement (and the proof) of Theorem 4.1.1 of the paper ‘Mackey formula in type A’ [Proc. London. Math. Soc. (3) 80 (2000) 545–574] is false. In this corrigendum we provide a correct statement (and a correct proof). As a consequence, we see that Corollary 4.1.2 of the paper holds. So all the other statements in the paper are correct (up to minor misprints…).2000 Mathematical Subject Classification: 20G05, 20G40.
- Published
- 2003
45. 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
46. UNIFORM EIGENVALUE ESTIMATES FOR TIME-FREQUENCY LOCALIZATION OPERATORS
- Author
-
F. De Mari, Hans G. Feichtinger, and K. Nowak
- Subjects
Discrete mathematics ,General Mathematics ,Bounded function ,Spectral theorem ,Operator theory ,Algebraic number ,Eigenvalues and eigenvectors ,Toeplitz matrix ,Mathematics ,Functional calculus ,Fock space - Abstract
Time-variantfilters based on Calderon and Gabor reproducingformulas are important tools in time frequencyanalysis.The paper studiesthe behaviorof the eigenvaluesof these filters.Optimal two-sided estimates of the number of eigenvaluescontainedin the interval (151,02), where 0 < 01 < 152 < 1, arc obtained.The estimatescoverlarge classesof localizationdomainsand generatingfunctions. 1. Introduction and statements of the results Calderon- Toeplitz and Gabor- Toeplitz operators arise naturally in two contexts: (i) Toephtz operators on Fock and Bergman spaces of holomorphic functions; (ii) time-variant filters based on Calderon and Gabor reproducing formulas. This paper is concerned with the eigenvalues of a subclass of Calderon- Toeplitz and Gabor- Toeplitz operators which have characteristic functions of bounded domains as symbols. Operators of this class are called time-frequency localiza tion operators. The basic idea of functional calculus is that the operators resemble the main algebraic features of their symbols. We consider symbols that are idem potent with respect to pointwise multiplication, so it is natural to expect that the corresponding operators are at least approximately idempotent. It is easy to verify that time-frequency localization operators are compact, self-adjoint and bounded by 1. In view of these facts and the above-mentioned correspondence principle, one is inclined to think that localization operators should resemble finite dimensional orthogonal projections. We show that this expectation is correct for Gabor- Toeplitz operators and that it is false for Calderon- Toeplitz operators. We identify the basic geometric features responsible for these two different behaviors. Our principal results are two-sided estimates of the number of eigenvalues inside the plunge region corresponding to 61, (52, where 0 < 61 < (52 < 1. The plunge region consists of the set of indices of the eigenvalues contained inside the open interval (61,62). The eigen val ues are ordered non-increasingly. Our work generalizes and improves previ ous results of Daubechies, Paul, Ramanathan and Topiwala [6, 8, 21].
- Published
- 2002
47. 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
48. LOWER BOUNDS ON LP QUASI‐NORMS AND THE UNIFORM SUBLEVEL SET PROBLEM
- Author
-
John Green
- Subjects
Set (abstract data type) ,Discrete mathematics ,Mathematics - Classical Analysis and ODEs ,General Mathematics ,Classical Analysis and ODEs (math.CA) ,FOS: Mathematics ,26D10 (Primary), 42B99 (Secondary) ,Mathematics - Abstract
Recently, Steinerberger proved a uniform inequality for the Laplacian serving as a counterpoint to the standard uniform sublevel set inequality which is known to fail for the Laplacian. In this paper, we observe that many inequalities of this type follow from a uniform lower bound on the $L^1$ norm, and give an analogous result for any linear differential operator, which can fail for non-linear operators. We consider lower bounds on the $L^p$ quasi-norms for $p, 42 pages, 1 figure, supersedes arXiv:2005.09407: main theorems strengthened and surrounding discussion presented in a much different context
- Published
- 2021
49. The Probability that the Number of Points on an Elliptic Curve over a Finite Field is Prime
- Author
-
James McKee and Steven D. Galbraith
- Subjects
Discrete mathematics ,Elliptic curve ,Jacobian curve ,Modular elliptic curve ,General Mathematics ,Sato–Tate conjecture ,Hessian form of an elliptic curve ,Schoof's algorithm ,Twists of curves ,Tripling-oriented Doche–Icart–Kohel curve ,Mathematics - Abstract
The paper gives a formula for the probability that a randomly chosen elliptic curve over a finite field has a prime number of points. Two heuristic arguments in support of the formula are given as well as experimental evidence. The paper also gives a formula for the probability that a randomly chosen elliptic curve over a finite field has kq points where k is a small number and q is a prime.
- Published
- 2000
50. Set Theory is Interpretable in the Automorphism Group of an Infinitely Generated Free Group
- Author
-
Vladimir Tolstykh
- Subjects
p-group ,Combinatorics ,Discrete mathematics ,Endomorphism ,Inner automorphism ,Symmetric group ,General Mathematics ,Quaternion group ,Outer automorphism group ,Alternating group ,Automorphism ,Mathematics - Abstract
In [6] S. Shelah showed that in the endomorphism semi-group of an infinitely generated algebra which is free in a variety one can interpret some set theory. It follows from his results that, for an algebra Fℵ which is free of infinite rank ℵ in a variety of algebras in a language L, if ℵ > |L|, then the first-order theory of the endomorphism semi-group of Fℵ, Th(End(Fℵ)), syntactically interprets Th(ℵ,L2), the second-order theory of the cardinal ℵ. This means that for any second-order sentence χ of empty language there exists χ*, a first-order sentence of semi-group language, such that for any infinite cardinal ℵ > |L|,formula hereIn his paper Shelah notes that it is natural to study a similar problem for automorphism groups instead of endomorphism semi-groups; a priori the expressive power of the first-order logic for automorphism groups is less than the one for endomorphism semi-groups. For instance, according to Shelah's results on permutation groups [4, 5], one cannot interpret set theory by means of first-order logic in the permutation group of an infinite set, the automorphism group of an algebra in empty language. On the other hand, one can do this in the endomorphism semi-group of such an algebra.In [7, 8] the author found a solution for the case of the variety of vector spaces over a fixed field. If V is a vector space of an infinite dimension ℵ over a division ring D, then the theory Th(ℵ, L2) is interpretable in the first-order theory of GL(V), the automorphism group of V. When a field D is countable and definable up to isomorphism by a second-order sentence, then the theories Th(GL(V)) and Th(ℵ, L2) are mutually syntactically interpretable. In the general case, the formulation is a bit more complicated.The main result of this paper states that a similar result holds for the variety of all groups.
- Published
- 2000
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.