Search

We investigate various kinds of bases in infinite dimensional Banach spaces. In particular, we consider the complexity of Hamel bases in separable and non-separable Banach spaces and show that in a separable Banach space a Hamel basis cannot be analytic, whereas there are non-separable Hilbert spaces which have a discrete and closed Hamel basis. Further we investigate the existence of certain complete minimal systems in `∞ as well as in separable Banach spaces. Outline. The paper is concerned with bases in infinite dimensional Banach spaces. The first section contains the definitions of the various kinds of bases and biorthogonal systems and also summarizes some set-theoretic terminology and notation which will be used throughout the paper. The second section provides a survey of known or elementary results. The third section deals with Hamel bases and contains some consistency results proved using the forcing technique. The fourth section is devoted to complete minimal systems (including Φ-bases and Auerbach bases) and the last section contains open problems. ∗The research for this paper began during the Workshop on Set Theory, Topology, and Banach Space Theory, which took place in June 2003 at Queen’s University Belfast, whose hospitality is gratefully acknowledged. The workshop was supported by the Nuffield Foundation Grant NAL/00513/G of the third author, the EPSRC Advanced Fellowship of the second author and the grant GACR 201/03/0933 of the fourth author. 1

This paper studies the multiplicative semigroup generated by all rationals of the form (3n+2)/(2n+1) for nonnegative integers n, together with 1/2. The subsemigroup of integers in this semigroup is called the wild integer semigroup, and the wild numbers are the irreducible elements in this subsemigroup. This paper presents evidence that the wild numbers consist of all the prime numbers p except 3. The subsemigroup of integers in the multiplicative semigroup generated by all rationals of the form (3n+2)/(2n+1) for nonnegative integers n is called the Wooley integer semigroup and its irreducible elements are called Wooley numbers. This semigroup is shown to be recursive, and various open problems are formulated about Wooley integers., 11 pages, latex; revised with title change and some notation changes

A counterexample to a compactness embedding result of Nagy is provided. Let V and H be real separable Hilbert spaces with V densely and continuously embedded in H. Identifying H with its dual we write V c H c V' algebraically and topologically, where V' is the dual space to V. Given T > 0, let Y = L2(0, T; V), * = L2(0, T; H) and 7' = L2(0, T; V') denote the spaces of the square summable functions defined on the interval (0, T) with values in V, H and V', respectively. We define 2 = {v E 7: v' E 7'},whichwiththeusualnorm Ilullr = (I1uII2+I1u'II2,)1/2 is a Hilbert space (cf. [7], Theorem 25.4). The following remarks about the space 2f are in order. In the definition the derivative u' = du is understood in the dt weak sense. Nevertheless, when we view u as a V'-valued function, we know (see [8], Proposition 23.23) that it is absolutely continuous, so its derivative exists in the strong sense almost everywhere on (0, T). It is known (see, e.g., [7], Theorem 25.5) that the embedding (1) 7C C(0 T; H) is continuous. Here C(0, T; H) denotes the space of continuous functions from [0, T] into H, endowed with the supremum norm. Therefore every function in /l can be, after modification on the set of measure zero, considered as an element of C(0, T; H). We also know that 2 c X compactly (see [8]). The following is the main result of Nagy (see [3], Theorem 2). Theorem. Let V and H be infinite-dimensional separable Hilbert spaces such that the embedding V c H is dense, continuous and compact. Then the embedding (1) is also compact. The aim of this paper is to exhibit a simple example which shows that the embedding (1) cannot be compact, i.e., the above theorem is not true. It should also be noted here that this theorem was exploited in several recent papers in Received by the editors December 1, 1993. 1991 Mathematics Subject Classification. Primary 46E35.

Bifurcation diagrams of Steiner tree topologies for four boundary points are constructed in this paper. Also some properties of such diagrams for an arbitrary number of points are considered.

The set of solutions to the equation xy = yx has been studied extensively over the past three centuries, including work by well known mathematicians such as Daniel Bernoulli (1700–1782), Leonhard Euler (1707–1783), and Christian Goldbach (1690–1764). Various mathematicians have focused on the integer, rational, real, and complex solutions. For example, it has been shown (see [1]) that the equality 24 = 42 gives the only distinct integer solutions. Our exposition below presents some of the key ideas behind the positive real solutions to this equation and illustrates how rational solutions can be found. To learn more about the various solutions, the reader can consult the articles listed at the end of this paper, as well as the extensive references given in these articles. It is also possible to find some of this material on the Web.

In this paper, we mainly discuss the constructions of some new K-g-frames which differ from the existing methods. Meanwhile, we use the relation between a positive operator and the frame operator of a K-g-frame to yield a new K-g-frame. We also obtain a necessary and sufficient condition to generate a new K-g-frame. In addition, we correct some recent results which were obtained by Huang and Leng. In the end, we give an equivalent characterization to construct some new tight K-g-frames by two given g-Bessel sequences. Our results generalize and improve some remarkable results.

In this paper, we consider the constraint set K := {x ? Rn : gj(x)? 0,? j = 1,2,...,m} of inequalities with nonsmooth nonconvex constraint functions gj : Rn ? R (j = 1,2,...,m).We show that under Abadie?s constraint qualification the ?perturbation property? of the best approximation to any x in Rn from a convex set ?K := C ? K is characterized by the strong conical hull intersection property (strong CHIP) of C and K, where C is an arbitrary non-empty closed convex subset of Rn: By using the idea of tangential subdifferential and a non-smooth version of Abadie?s constraint qualification, we do this by first proving a dual cone characterization of the constraint set K. Moreover, we present sufficient conditions for which the strong CHIP property holds. In particular, when the set ?K is closed and convex, we show that the Lagrange multiplier characterizations of constrained best approximation holds under a non-smooth version of Abadie?s constraint qualification. The obtained results extend many corresponding results in the context of constrained best approximation. Several examples are provided to clarify the results.

It is known that under the Dirichlet product, the set of arithmetic functions in several variables becomes a unique factorization domain. A. Zaharescu and M. Zaki proved an analog of the ABC conjecture in this ring and showed that there exists a non-trivial solution to the Fermat equation $$z^n=x^n+y^n$$ ($$n\ge 3$$). It is also known that under the Cauchy product, the set of arithmetic functions becomes a unique factorization domain. In this paper, we consider the ring of arithmetic functions in several variables under the Cauchy product and prove an analog of the ABC conjecture in this ring to show that there exists a non-trivial solution to the Fermat equation $$z^n=x^n+y^n$$ ($$n\ge 3$$).

The domatic number [Formula: see text] of a graph [Formula: see text] is the maximum number of disjoint dominating sets in a dominating set partition of a graph [Formula: see text]. For any graph [Formula: see text], [Formula: see text] where [Formula: see text] is the minimum degree of [Formula: see text], and [Formula: see text] is domatically full if the equality holds, i.e., [Formula: see text]. In this paper, we characterize domatically full Cartesian products of a path of order 2 and a tree of order at least 3. Moreover, we show a characterization of the Cartesian product of a longer path and a tree of order at least 3. By using these results, we also show that for any two trees of order at least 3, the Cartesian product of them is domatically full.

Let V be a finite dimensional vector space over a local field. Let us say that a complex function on V is elementary if it is a product of the additive character of a rational function Q on V and multiplicative characters of polynomials on V. In this paper we study when the Fourier transform of an elementary function is elementary. If Q has a nonzero Hessian, a necessary condition for this is that the Legendre transform Q_* of Q is rational. The basic example is a nondegenerate quadratic form. We study such functions Q, give examples, and find all of them such that both Q and Q_* are of the form f(x)/t, where f is a cubic form in many variables (the simplest case after quadratic forms). It turns out that this classification is closely related to Zak's classification of Severi varieties. The second half of the paper is devoted to finding and classifying elementary functions with elementary Fourier transforms when Q is a fixed function with rational Q_*. We consider the simplest case when Q is a monomial, and classify combinations of multiplicative characters that can arise. The answer (for real and complex fields) is given in terms of exact covering systems. We also describe examples related to prehomogeneous vector spaces. Finally, we consider examples over p-adic fields, and in particular give a local proof of an integral formula of D.K. that could previously be proved only by a global method., Comment: 31 pages, latex; the proof of Theorem 3.10 given in the previous version was found to be incomplete. We have added a remark about this and a reference to a paper by Chaput and Sabatino that gives a complete proof

This paper is devoted to the computation of the index of a critical point for nonlinear operators with strong coefficient growth. These operators are associated with boundary value problems of the type \begin{center} $\displaystyle \sum_{|\alpha|=1}\mathscr{D}^{\alpha}\{\rho^{2}(u)\mathscr{D}^{\alpha}u+a_{\alpha}(x,\mathscr{D}^{1}u)\}=\lambda a_{0}(x,u,\mathscr{D}^{1}u),\ x\in\Omega$, $u(x)=0,\ x\in\partial\Omega$, \end{center} where $\Omega\subset\mathbf{R}^{n}$ is open, bounded and such that $\partial\Omega\in\mathbf{C}^{2}$, while $\rho: \mathbf{R} \to \mathbf{R}_{+}$ can have exponential growth. An index formula is given for such densely defined operators acting from the Sobolev space $W_0^{1,m}(\Omega)$ into its dual space. We consider different sets of assumptions for $m>2$ (the case of a real Banach space) and $m=2$ (the case of a real Hilbert space). The computation of the index is important for various problems concerning nonlinear equations: solvability, estimates for the number of solutions, branching of solutions, etc. The result of this paper are based upon recent results of the authors involving the computation of index of a critical point for densely defined abstract operators of type $(S_{+})$. The latter are based in turn upon a new degree theory for densely defined $(S_{+})$-mappings, which has also been developed by the authors in a recent paper. Applications of the index formula to the relevant bifurcation problems are also included.

The main goal of the present paper is two-fold. First we extend the theory of toroidal embeddings introduced by Kempf, Knudsen, Mumford and Saint-Donat to the class of toroidal varieties with stratifications (which is the main body of the paper). Second we give a proof of the following weak factorization theorem as an application and illustration of the theory: A birational map between complete nonsingular varieties over an algebraically closed field K of characteristic zero is a composite of blow ups and blow downs with smooth centers. Another proof of the weak factorization theorem appeared in a joint paper with Abramovich, Karu and Matsuki (math.AG/9904135) In that paper the theorem is stated and proven in general for proper algebraic and analytic spaces., Comment: 69 pages, a revised version with conceptual simplifications. The present version is self-contained and it does not rely on weak factorization theorem for toric varieties

The paper suggests a general method for proving the fact whether a certain set is p-computable or not. The method is based on a polynomial analogue of the classical Gandy’s fixed point theorem. Classical Gandy’s theorem deals with the extension of a predicate through a special operator ΓΦ(x)Ω∗ and states that the smallest fixed point of this operator is a Σ-set. Our work uses a new type of operator which extends predicates so that the smallest fixed point remains a p-computable set. Moreover, if in the classical Gandy’s fixed point theorem, the special Σ-formula Φ(x¯) is used in the construction of the operator, then a new operator uses special generating families of formulas instead of a single formula. This work opens up broad prospects for the application of the polynomial analogue of Gandy’s theorem in the construction of new types of terms and formulas, in the construction of new data types and programs of polynomial computational complexity in Turing complete languages.

In the present article, we make use of the set partitions and the generating functions to give new combinatorial relations for the generalized central factorial numbers. In the second part of the paper, we present a relationship between the Bernoulli polynomials and the Stirling numbers with higher level.

where Lc(X, Y ) denotes the subspace of all compact operators. This phenomenon was studied later by many authors (see e.g. [1; 5; 11; 12; 13; 14; 15; 20; 21]); of prime importance are Vogt’s results [24] giving a generally complete description of the relations (1) for the general case of Frechet spaces (for further generalizations see also [3; 4]). Originally, the main goal in [25; 26] was the isomorphism of Cartesian products (and, consequently, the quasi-equivalence property for those spaces). The papers made use of the fact that, due to Fredholm operators theory, an isomorphism of spaces X × Y ' X1× Y1 (X,X1∈X , Y, Y1∈Y ) that satisfies (2) also implies an isomorphism of Cartesian factors “up to some finite-dimensional subspace”. In the present paper we generalize this approach onto classes X × Y of products that satisfy (1) instead of (2). Although Fredholm operators theory fails, we have established that—in the case of Kothe spaces—the stability of an automorphism under a bounded perturbation still takes place, but in a weakened form: “up to some basic Banach space”. In particular, we get a positive answer to Question 2 in [7]: Is it possible to modify somehow the method developed in [25; 26] in order to obtain isomorphic classification of the spaces E0(a) × E∞(b) in terms of sequences a, b if ai 6→ ∞ and bi 6→ ∞? Some of our results are announced without proofs in [9].

In the present paper, we face the problem of classifying classes of orientable PL 5-manifolds M5 with h ≥ 1 boundary components, by making use of a combinatorial invariant called regular genusG(M5). In particular, a complete classification up to regular genus five is obtained: where denotes the regular genus of the boundary ∂M5 and denotes the connected sumof h ≥ 1 orientable 5-dimensional handlebodies 𝕐αi of genus αi ≥ 0 (i = 1, . . . ,h), so that .Moreover, we give the following characterizations of orientable PL 5-manifolds M5 with boundary satisfying particular conditions related to the “gap” between G(M5) and either G(∂M5) or the rank of their fundamental group rk(π1(M5)): Further, the paper explains how the above results (together with other known properties of regular genus of PL manifolds) may lead to a combinatorial approach to 3-dimensional Poincaré Conjecture.

It is known that every semigroup of normal completely positive maps $P = {P_t: t\geq 0}$ of $B(H)$, satisfying $P_t(1) = 1$ for every $t\geq 0$, has a minimal dilation to an E_0-semigroup acting on $B(K)$ for some Hilbert space K containing H. The minimal dilation of P is unique up to conjugacy. In a previous paper a numerical index was introduced for semigroups of completely positive maps and it was shown that the index of P agrees with the index of its minimal dilation to an E_0-semigroup. However, no examples were discussed, and no computations were made. In this paper we calculate the index of a unital completely positive semigroup whose generator is a bounded operator $ L: B(H)\to B(H) $ in terms of natrual structures associated with the generator. This includes all unital CP semigroups acting on matrix algebras. We also show that the minimal dilation of the semigroup $P={\exp{tL}: t\geq 0}$ to an \esg\ is is cocycle conjugate to a CAR/CCR flow., Comment: 31 pp. AMS-TeX 2.0

In this paper the Lebesgue covering lemma is extended from the setting of metric spaces to the setting of admissible spaces. An admissible space is a topological space endowed with an admissible family of open coverings, and need not be metric. The paper contains applications to uniform continuity and dimension theory.

The classic all-terminal network reliability problem posits a graph, each of whose edges fails independently with some given probability. The goal is to determine the probability that the network becomes disconnected due to edge failures. This problem has obvious applications in the design of communication networks. Since the problem is ${\sharp {\cal P}}$-complete and thus believed hard to solve exactly, a great deal of research has been devoted to estimating the failure probability. In this paper, we give a fully polynomial randomized approximation scheme that, given any n-vertex graph with specified failure probabilities, computes in time polynomial in n and $1/\epsilon$ an estimate for the failure probability that is accurate to within a relative error of $1\pm\epsilon$ with high probability. We also give a deterministic polynomial approximation scheme for the case of small failure probabilities. Some extensions to evaluating probabilities of $k$-connectivity, strong connectivity in directed Eulerian graphs and $r$-way disconnection, and to evaluating the Tutte polynomial are also described. This version of the paper corrects several errata that appeared in the previous journal publication [D. R. Karger, SIAM J. Comput., 29 (1999), pp. 492--514].

Let g be a symmetrisable Kac-Moody algebra, and U_h(g) the corresponding quantum group. We showed in arXiv:1610.09744 and arXiv:1610.09741 that the braided quasi-Coxeter structure on integrable, category O representations of U_h(g) which underlies the R-matrix actions arising from the Levi subalgebras of U_h(g) and the quantum Weyl group action of the generalised braid group B_g can be transferred to integrable, category O representations of g. We prove in this paper that, up to unique equivalence, there is a unique such structure on the latter category with prescribed restriction functors, R--matrices, and local monodromies. This extends, simplifies and strengthens a similar result of the second author valid when g is semisimple, and is used in arXiv:1512.03041 to describe the monodromy of the rational Casimir connection of g in terms of the quantum Weyl group operators of U_h(g). Our main tool is a refinement of Enriquez's universal algebras, which is adapted to the PROP describing a Lie bialgebra graded by the non-negative roots of g., Expanded Introduction and Sec. 5 to discuss convolution product (5.11), cosimplicial structure on basis elements (5.13) and module structure on coinvariants (5.15). Minor revisions in Sec. 7.1 (gradings), 7.4 (deformation DY modules), 9.7 (exposition), 15.7 (Drinfeld double) and 15.15 (rigidity for diagrammatic KM algebras). Final version, to appear in Adv. Math. 81 pages

This paper presents a method for deriving optimal lower and upper bounds for probabilities and conditional probabilities (given a σ-field) for various combinations of events. The optimality is understood as the possibility that inequalities become equalities for some sets of events. New generalizations of the Jordan formula and the Bonferroni inequalities are obtained. The corresponding conditional versions of these results are also considered.

Let V be a sums of independent nonnegative integer-valued random variables and $$h_z$$ be a call function defined by $$h_{z}(v)=(v-z)^+$$ for $$v\ge 0, z \ge 0$$ where $$(v-z)^+=\max \{v-z,0\}$$. In this paper, we give bounds of Poisson approximation for $${E}[h_{z}(V)]$$. These bounds improve the results of Jiao and Karoui (Finance Stoch 13(2):151–180, 2009). The technique used is Stein–Chen method with the zero bias transformation. One example of applications for a call function in finance is the standard collateralized debt obligation (CDO) tranche pricing. The CDO is a security backed by a diversified pool of debt obligation such as bounds, loans and credit default swaps.

S. Ramanujan recorded several modular equations and P " role="presentation"> P P P - Q " role="presentation"> Q Q Q theta function identities in his notebooks and lost notebook without recording the proofs. In this paper, we provide an elementary proof of two modular equations and two P " role="presentation"> P P P - Q " role="presentation"> Q Q Q theta function identities of level 35, which have been proved by B.C. Berndt using the theory of modular forms.

Let $G$ be an $n$-vertex graph with $n\ge 3$. A classic result of Dirac from 1952 asserts that $G$ is hamiltonian if $\delta(G)\ge n/2$. Dirac's theorem is one of the most influential results in the study of hamiltonicity and by now there are many related known results\,(see, e.g., J. A. Bondy, Basic Graph Theory: Paths and Circuits, Chapter 1 in: {\it Handbook of Combinatorics Vol.1}). A {\it Halin graph} is a planar graph consisting of two edge-disjoint subgraphs: a spanning tree of at least 4 vertices and with no vertex of degree 2, and a cycle induced on the set of the leaves of the spanning tree. Halin graphs possess rich hamiltonicity properties such as being hamiltonian, hamiltonian connected, and almost pancyclic. As a continuous "generalization" of Dirac's theorem, in this paper, we show that there exists a positive integer $n_0$ such that any graph $G$ with $n\ge n_0$ vertices and $\delta(G)\ge (n+1)/2$ contains a spanning Halin subgraph. In particular, it contains a spanning Halin subgraph which is also pancyclic., Comment: 25 pages, 3 figures

A Boolean function $g$ is said to be an optimal predictor for another Boolean function $f$ , if it minimizes the probability that $f(X^{n})\neq g(Y^{n})$ among all functions, where $X^{n}$ is uniform over the Hamming cube and $Y^{n}$ is obtained from $X^{n}$ by independently flipping each coordinate with probability $\delta$ . This paper is about self-predicting functions, which are those that coincide with their optimal predictor.

Given a fixed sigma-finite measure space $$\left( X,\mathscr {B},\nu \right) $$ , we shall study an associated family of positive definite kernels K. Their factorizations will be studied with view to their role as covariance kernels of a variety of stochastic processes. In the interesting cases, the given measure $$\nu $$ is infinite, but sigma-finite. We introduce such positive definite kernels $$K\left( \cdot ,\cdot \right) $$ with the two variables from the subclass of the sigma-algebra $$\mathscr {B}$$ whose elements are sets with finite $$\nu $$ measure. Our setting and results are motivated by applications. The latter are covered in the second half of the paper. We first make precise the notions of realizations and factorizations for K, and we give necessary and sufficient conditions for K to have realizations and factorizations in $$L^{2}\left( \nu \right) $$ . Tools in the proofs rely on probability theory and on spectral theory for unbounded operators in Hilbert space. Applications discussed here include the study of reversible Markov processes, and realizations of Gaussian fields, and their Ito-integrals.

v is the 1-vectorfield “dual” to ω: if ω = ∑ (−1)fi dx1 ∧ · · · ∧ ∧ dxi ∧ · · · ∧ dxn, then v = (f1, . . . , fn).) There has been considerable effort in the literature (e.g. [JK], [M], [P]) to extend this formula to permit integrands of less regularity by generalizing the Lebesgue integral. On the other hand, invariably the situations in which (1) holds require fairly strong hypotheses on the boundary ∂Ω, e.g. that it should have sigmafinite (n−1)-measure, or that the gradient of the characteristic function of Ω be a vector valued measure with finite total variation [F], [P]. However there is a natural way to expand the validity of (1) to much more general boundaries while still using the ordinary Lebesgue integral; this is the topic of the present paper. For the case of Lipschitz forms, the results of this paper follow readily from Whitney’s theory of flat chains [W2]. However his approach to the Gauss-Green theorem is not widely appreciated because he focused on chains and cochains, where effectively (1) is used to define the exterior derivative. In [HN] we extend Whitney’s method to treat the more general Holder case. (Only the case n = 2 is discussed

This paper investigates the optimal recovery of Sobolev spaces W∞r[−1,1],r∈ℕ in space L∞[−1,1] and weighted spaces Lp,ω[−1,1],1≤p

Whitney proved in 1931 that 4-connected planar triangulations are Hamiltonian. Hakimi, Schmeichel, and Thomassen conjectured in 1979 that if $G$ is a 4-connected planar triangulation with $n$ vertices then $G$ contains at least $2(n-2)(n-4)$ Hamiltonian cycles, with equality if and only if $G$ is a double wheel. On the other hand, a recent result of Alahmadi, Aldred, and Thomassen states that there are exponentially many Hamiltonian cycles in 5-connected planar triangulations. In this paper, we consider 4-connected planar $n$-vertex triangulations $G$ that do not have too many separating 4-cycles or have minimum degree 5. We show that if $G$ has $O(n/{\log}_2 n)$ separating 4-cycles then $G$ has $\Omega(n^2)$ Hamiltonian cycles, and if $\delta(G)\ge 5$ then $G$ has $2^{\Omega(n^{1/4})}$ Hamiltonian cycles. Both results improve previous work. Moreover, the proofs involve a "double wheel" structure, providing further evidence to the above conjecture., Comment: 20 pages, 2 figures

By \(\text{NT}(n)\) we denote the set of graphs of order \(n\) which are traceable but have non-traceable edges, i.e. edges which are not contained in any hamiltonian path. The class \(\text{NT}(n)\) has been considered by Balińska and co-authors in a paper published in 2003, where it was proved that the maximum size \(t_{\max}(n)\) of a graph in \(\text{NT}(n)\) is at least \((n^2-5n+14)/2\) (for \(n \geq 12\)). The authors also found \(t_{\max}(n)\) for \(5 \leq n \leq 11\). We prove that, for \(n \geq 5\), \(t_{\max}(n) = max\left\{ {{n-2}\choose{2}}+4, {{n-\lfloor\frac{n-1}{2}\rfloor}\choose{2}}+\lfloor\frac{n-1}{2}\rfloor^2\right\}\) and, moreover, we characterize the extremal graphs (in fact we prove that these graphs are exactly those already described in the paper by Balinska et al.). We also prove that a traceable graph of order \(n \geq 5\) may have at most \( \lceil\frac{n-3}{2}\rceil \lfloor\frac{n-3}{2}\rfloor\) non traceable edges (this result was conjectured in the mentioned paper by Balinska and co-authors).

LetX= (X(t))(t >= 0)(X(0) = 0) be a continuous centered Gaussian process on a probability space (omega,F,P), and let (Y-t)(t is an element of)[0,1] (Y-0= 0) be a continuous process (on the same probability space) with nondecreasing paths, independent ofX. Define the time-changed Gaussian processZ(t)=X(Y-t),t is an element of [0,1]. In this paper, we investigate a problem of finite-dimensional large deviations and a problem of pathwise large deviations for time-changed continuous Gaussian processes. As applications, we considered subordinated Gaussian processes.

In this paper, we introduce a new kind of generalized Fibonacci polynomials in the distance sense. We give a direct formula, a generating function and matrix generators for these polynomials. Moreover, we present a graph interpretation of these polynomials, their connections with Pascal&rsquo, s triangle and we prove some identities for them.

Diophantine problems related to binomial coefficients have a vast literature. In this paper we investigate power and polynomial values of row sums of hyperbolic Pascal triangles, which are recently introduced generalizations of Pascal's classical triangle. We prove various effective and ineffective finiteness results.

For any positive integer $k$, define $f(k)$ (respectively, $f_3(k)$) to be the minimal integer $\ge k$ such that every 3-connected planar graph $G$ (respectively, 3-connected cubic planar graph $G$) of circumference $\ge k$ has a cycle whose length is in the interval $[k, f(k)]$ (respectively, $[k, f_3(k)]$). Merker showed that $f_3(k) \le 2k + 9$ for any $k \ge 2$, and $f_3(k) \ge 2k + 2$ for any even $k \ge 4$. He conjectured that $f_3(k) \le 2k + 2$ for any $k \ge 2$. This conjecture was disproved by Zamfirescu, who gave an infinite family of counterexamples for every even $k \ge 6$ whose graphs have no cycle length in $[k, 2k + 2]$, i.e. $f_3(k) \ge 2k + 3$ for any even $k \ge 6$. However, the exact value of $f_3(k)$ was only known for $k \le 4$, and it was left open to determine $f_3(k)$ for $k \ge 5$. In this paper we improve Merker's upper bound, and give the exact value of $f_3(k)$ for every $k \ge 5$. We show that $f_3(5) = 10$, $f_3(7) = 15$, $f_3(9) = 20$, and $f_3(k) = 2k + 3$ for any $k = 6, 8$ or $\ge 10$. For general 3-connected planar graphs, Merker conjectured that there exists some positive integer $c$ such that $f(k) \le 2k + c$ for any positive integer $k$. We give a complete positive answer to this conjecture. We prove that $f(k) = 5$ for any $k \le 3$, $f(4) = 10$, and $f(k) = 2k + 3$ for any $k \ge 5$.

In this paper we study the weak Roman domination number and the secure domination number of a graph. In particular, we obtain general bounds on these two parameters and, as a consequence of the study, we derive new inequalities of Nordhaus-Gaddum type involving secure domination and weak Roman domination. Furthermore, the particular case of Cartesian product graphs is considered.

In their last published paper [9], [16, pp. 310–321], G. H. Hardy and S. Ramanujan derived infinite series representations for the coefficients of certain modular forms of negative weight which are not analytic in the upper half-plane. In particular, they examined in detail the coefficients of the reciprocal of the Eisenstein series E6(τ). While confined to the sanitarium, Matlock House, in 1918, Ramanujan wrote several letters to Hardy about the coefficients in the power series expansions of certain quotients of Eisenstein series. These letters are photocopied in [18, pp. 97–126], and printed versions with commentary can be found in [6, pp. 175–191]. In these letters, Ramanujan recorded formulas for the coefficients of several quotients of Eisenstein series not examined by Hardy and him in [9]. These claims fall into two related classes. In the first class are formulas for coefficients that arise from the main theorem of Hardy and Ramanujan, or a slight modification of it, and these results have been proved in a paper by Berndt and Bialek [5]. Those in the second class, which we prove in this paper, are much harder to prove. To establish the first main result, we need an extension of Hardy and Ramanujan’s theorem due to H. Petersson [11]. To prove the second primary result, we need to first extend work of H. Poincare [14], Petersson [11], [12], [13], and J. Lehner [10] to cover double poles. In all cases, the formulas have a completely different shape from those arising from modular forms analytic in the upper half-plane, such as the famous infinite series for the partition function p(n) arising from the reciprocal of the Dedekind eta-function. As we shall see in the sequel, the series examined in this paper are very rapidly convergent, even more so than those arising from modular forms analytic in the upper half-plane, so that truncating a series, even with a small number of terms, provides a remarkable approximation. Using Mathematica, we calculated several coefficients and series approximations for the two primary functions 1/B(q) and 1/B(q) (defined below) examined by Ramanujan. As will be seen from the first table, the coefficient of q in 1/B(q), for example, has 17 digits, while just two terms of Ramanujan’s infinite series representation calculate this coefficient with

In this paper, we give several inequalities involving the Davis–Wielandt radius and the numerical radii of Hilbert space operators. In particular, we show that if T is a bounded linear operator on a complex Hilbert space, then $$\begin{aligned} dw(T) \le \Big (w\big (|T|^4 + |T|^8\big ) + 2w^2\big (|T|^2T\big )\Big )^{\frac{1}{4}}, \end{aligned}$$where $$dw(\cdot )$$ and $$w(\cdot )$$ are the Davis–Wielandt radius and the numerical radius, respectively.

In this paper, we introduce the iterative scheme for finding a common fixed point of a countable family of G-nonexpansive mappings by the shrinking projection method which generalizes Takahashi Takeuchi and Kubota&rsquo, s theorem in a Hilbert space with a directed graph. Simultaneously, we give examples and numerical results for supporting our main theorems and compare the rate of convergence of some examples under the same conditions.

In this paper, we study the Erdős distinct distances problem for Cartesian product sets in the setting of arbitrary finite fields. More precisely, let $\mathbb{F}_{q}$ be an arbitrary finite field and $A$ be a set in $\mathbb{F}_{q}$ . Suppose $|A\cap (aG)|\le |G|^{1/2}$ for any subfield $G$ and $a\in \mathbb{F}_{q}^{*}$ , then \begin{equation*}\vert \Delta _{\mathbb{F}_{q}}(A^{2})\vert =\vert (A-A)^{2}+(A-A)^{2}\vert \gg \vert A\vert ^{1+\frac{1}{21}}.\end{equation*} Using the same method, we also obtain some results on sum–product type problems.

By Smith’s theorem, if a cubic graph has a Hamiltonian cycle, then it has a second Hamiltonian cycle. Thomason [‘Hamilton cycles and uniquely edge-colourable graphs’, Ann. Discrete Math.3 (1978), 259–268] gave a simple algorithm to find the second cycle. Thomassen [private communication] observed that if there exists a polynomially bounded algorithm for finding a second Hamiltonian cycle in a cubic cyclically 4-edge connected graph $G$, then there exists a polynomially bounded algorithm for finding a second Hamiltonian cycle in any cubic graph $G$. In this paper we present a class of cyclically 4-edge connected cubic bipartite graphs $G_{i}$ with $16(i+1)$ vertices such that Thomason’s algorithm takes $12(2^{i}-1)+3$ steps to find a second Hamiltonian cycle in $G_{i}$.

Let E be a finite set of elements, and let L be a clutter over ground set E. We say distinct elements e, f are opposite if every member and every minimal cover of L contains at most one of e, f. In this paper, we investigate opposite elements and reveal a rich theory underlying such a seemingly simple restriction. The clutter C obtained from L after identifying some opposite elements is called an identification of L; inversely, L is called a split of C. We will show that splitting preserves three clutter properties, i.e., idealness, the max-flow min-cut property, and the packing property. We will also display several natural examples in which a clutter does not have these properties but a split of them does. We will develop tools for recognizing when splitting is not a useful operation, and as well, we will characterize when identification preserves the three mentioned properties. We will also make connections to spanning arborescences, Steiner trees, comparability graphs, degenerate projective planes, binary clutters, matroids, as well as the results of Menger, Ford and Fulkerson, the Replication Conjecture, and a conjecture on ideal, minimally nonpacking clutters.

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).

A classical P��lya urn scheme is a Markov process whose evolution is encoded by a replacement matrix $(R_{i,j})_{1\leq i,j\leq d}$. At every discrete time-step, we draw a ball uniformly at random, denote its colour $c$, and replace it in the urn together with $R_{c,j}$ balls of colour $j$ (for all $1\leq j\leq d$). We are interested in multi-drawing P��lya urns, where the replacement rule depends on the random drawing of a set of $m$ balls from the urn (with or without replacement). This generalisation has already been studied in the literature, in particular by Kuba & Mahmoud (ArXiv:1503.09069 and 1509.09053), where second order asymptotic results are proved for $2$-colour urns under the balanced and the affinity assumptions. The main idea of this work is to apply stochastic approximation methods to this problem, which enables us to remove the affinity hypothesis of Kuba & Mahmoud and generalise the result to more-than-two-colour urns. We also give some partial results in the two-colour non-balanced case., This new arxiv version (v6) corrects a mistake that we discovered in the previous versions of this paper (v1-5). The mistake was in Theorem 1$(a)$ and in the last sentence of Theorem 4. In this new version, Theorem 1$(a)$ has been corrected, and Theorem 4 has been deleted

This paper aims to highlight classes of linear positive operators of discrete and integral type for which the rates in approximation of continuous functions and in quantitative estimates in Voronovskaya type results are of an arbitrarily small order. The operators act on functions defined on unbounded intervals and we achieve the intended purpose by using a strictly decreasing positive sequence $$(\lambda _n)_{n\ge 1}$$ such that $$\lim \limits _{n\rightarrow \infty }\lambda _n=0$$ , how fast we want. Particular cases are presented.

In 1973, Williams [D. Williams, On Rényi's ‘record’ problem and Engel's series, Bull. London Math. Soc.5 (1973), 235–237] introduced two interesting discrete Markov processes, namely C-processes and A-processes, which are related to record times in statistics and Engel's series in number theory respectively. Moreover, he showed that these two processes share the same classical limit theorems, such as the law of large numbers, central limit theorem and law of the iterated logarithm. In this paper, we consider the large deviations for these two Markov processes, which indicate that there is a difference between C-processes and A-processes in the context of large deviations.

The notion of [math] -graph was introduced by Bretto et al. and has interesting properties. This graph is related to a group [math] and a set of generators [math] of [math] and is denoted by [math] . In this paper, we consider several types of groups [math] and study the existence of Hamiltonian and Eulerian paths and circuits in [math] .

Let $G$ be a finite connected graph, and let $\rho$ be the spectral radius of its universal cover. For example, if $G$ is $k$-regular then $\rho=2\sqrt{k-1}$. We show that for every $r$, there is an $r$-covering (a.k.a. an $r$-lift) of $G$ where all the new eigenvalues are bounded from above by $\rho$. It follows that a bipartite Ramanujan graph has a Ramanujan $r$-covering for every $r$. This generalizes the $r=2$ case due to Marcus, Spielman and Srivastava (2013). Every $r$-covering of $G$ corresponds to a labeling of the edges of $G$ by elements of the symmetric group $S_{r}$. We generalize this notion to labeling the edges by elements of various groups and present a broader scenario where Ramanujan coverings are guaranteed to exist. In particular, this shows the existence of richer families of bipartite Ramanujan graphs than was known before. Inspired by Marcus-Spielman-Srivastava, a crucial component of our proof is the existence of interlacing families of polynomials for complex reflection groups. The core argument of this component is taken from a recent paper of them (2015). Another important ingredient of our proof is a new generalization of the matching polynomial of a graph. We define the $r$-th matching polynomial of $G$ to be the average matching polynomial of all $r$-coverings of $G$. We show this polynomial shares many properties with the original matching polynomial. For example, it is real rooted with all its roots inside $\left[-\rho,\rho\right]$., Comment: 38 pages, 4 figures, journal version (minor changes from previous arXiv version). Shortened version appeared in STOC 2016

Classes of circulant graphs play an important role in modeling interconnection networks in parallel and distributed computing. They also find applications in modeling quantum spin networks supporting the perfect state transfer. It has been noticed that unitary Cayley graphs as a class of circulant graphs possess many good properties such as small diameter, mirror symmetry, recursive structure, regularity, etc. and therefore can serve as a model for efficient interconnection networks. In this paper we go a step further and analyze some other characteristics of unitary Cayley graphs important for the modeling of a good interconnection network. We show that all unitary Cayley graphs are hamiltonian. More precisely, every unitary Cayley graph is hamiltonian-laceable (up to one exception for X6) if it is bipartite, and hamiltonianconnected if it is not. We prove this by presenting an explicit construction of hamiltonian paths on Xnm using the hamiltonian paths on Xn and Xm for gcd(n,m) = 1. Moreover, we also prove that every unitary Cayley graph is bipancyclic and every nonbipartite unitary Cayley graph is pancyclic.

We study the problem of routing symmetric demand pairs in planar digraphs. The input consists of a directed planar graph G = (V, E) and a collection of k source-destination pairs M = {s_1t_1, ..., s_kt_k}. The goal is to maximize the number of pairs that are routed along disjoint paths. A pair s_it_i is routed in the symmetric setting if there is a directed path connecting s_i to t_i and a directed path connecting t_i to s_i. In this paper we obtain a randomized poly-logarithmic approximation with constant congestion for this problem in planar digraphs. The main technical contribution is to show that a planar digraph with directed treewidth h contains a constant congestion crossbar of size Omega(h/polylog(h)).

For nonnegative integers $k, d_1, \ldots, d_k$, a graph is $(d_1, \ldots, d_k)$-colorable if its vertex set can be partitioned into $k$ parts so that the $i$th part induces a graph with maximum degree at most $d_i$ for all $i\in\{1, \ldots, k\}$. A class $\mathcal C$ of graphs is balanced $k$-partitionable and unbalanced $k$-partitionable if there exists a nonnegative integer $D$ such that all graphs in $\mathcal C$ are $(D, \ldots, D)$-colorable and $(0, \ldots, 0, D)$-colorable, respectively, where the tuple has length $k$. A set $X$ of cycles is a cycle obstruction set of a class $\mathcal C$ of planar graphs if every planar graph containing none of the cycles in $X$ as a subgraph belongs to $\mathcal C$. This paper characterizes all cycle obstruction sets of planar graphs to be balanced $k$-partitionable and unbalanced $k$-partitionable for all $k$; namely, we identify all inclusionwise minimal cycle obstruction sets for all $k$.