Range of cube-indexed random walk

For given finite, connected, bipartite graphG=(V,E) with distinguishedν ₀ ∈V, set {fx189-1} Our main result says there is a fixedb so that whenG is a Hamming cube ({0, 1} ⁿ with the usual adjacency), andf is chosen uniformly fromF, the probability thatf takes more thanb values is at most e^?Ω(n). this settles in a very strong way a conjecture of I. Benjamini, O. Häggström and E. Mossel [2]. The proof is based on entropy considerations and a new log-concavity result.     

Sums of finitely based lattice varieties

This paper is concerned with the question whether the lattice sum (join) V + V′ of two finitely based lattice varieties V and V′ is finitely based. An example is constructed showing that this is not always the case. On the other hand, it is proved that if V ? M and (V′)³ = (N)³, then V + V′ is finitely based. Here M and N are, respectively, the variety of all modular lattices and the variety generated by the pentagon (the five-element nonmodular lattice), and (V)ⁿ is the variety defined by all those identities with n variables or less that hold in V. In particular, M + N, the unique lattice variety that covers M, is finitely based.     

The Critical Case of the Cramer-Lundberg Theorem on the Asymptotic Tail Behavior of the Maximum of a Negative Drift Random Walk

We study the asymptotic tail behavior of the maximum M = max{0,S _n ,n ≥ = 1} of partial sums S _n = ξ₁ + ? + ξ _n of independent identically distributed random variables ξ₁,ξ₂,... with negative mean. We consider the so-called Cramer case when there exists a β > 0 such that E e ^βξ1 = 1. The celebrated Cramer-Lundberg approximation states the exponential decay of the large deviation probabilities of M provided that Eξ₁ e ^βξ1 is finite. In the present article we basically study the critical case Eξ₁ e ^βξ1 = ∞.     

Quasi-periodic solutions with prescribed frequency in a nonlinear Schrdinger equation

In this paper, one-dimensional (1D) nonlinear Schrdinger equation iut-uxx + Mσ u + f ( | u | 2 )u = 0, t, x ∈ R , subject to periodic boundary conditions is considered, where the nonlinearity f is a real analytic function near u = 0 with f (0) = 0, f (0) = 0, and the Floquet multiplier Mσ is defined as Mσe inx = σne inx , with σn = σ, when n 0, otherwise, σn = 0. It is proved that for each given 0 σ 1, and each given integer b 1, the above equation admits a Whitney smooth family of small-amplitude quasi-periodic solutions with b-dimensional Diophantine frequencies, corresponding to b-dimensional invariant tori of an associated infinite-dimensional Hamiltonian system. Moreover, these b-dimensional Diophantine frequencies are the small dilation of a prescribed Diophantine vector. The proof is based on a partial Birkhoff normal form reduction and an improved KAM method.     

On reformulated Zagreb indices

The first and second reformulated Zagreb indices are defined respectively in terms of edge-degrees as EM₁(G)=∑_e∈Edeg(e)² and EM₂(G)=∑_e∼fdeg(e)deg(f), where deg(e) denotes the degree of the edge e, and e∼f means that the edges e and f are adjacent. We give upper and lower bounds for the first reformulated Zagreb index, and lower bounds for the second reformulated Zagreb index. Then we determine the extremal n-vertex unicyclic graphs with minimum and maximum first and second Zagreb indices, respectively. Furthermore, we introduce another generalization of Zagreb indices.     

On the adjacent vertex-distinguishing equitable edge coloring of graphs

Let G(V, E) be a graph. A k-adjacent vertex-distinguishing equatable edge coloring of G, k-AVEEC for short, is a proper edge coloring f if (1) C(u)≠C(v) for uv ∈ E(G), where C(u) = {f(uv)|uv ∈ E}, and (2) for any i, j = 1, 2,… k, we have ||Ei| |Ej|| ≤ 1, where Ei = {e|e ∈ E(G) and f(e) = i}. χáve (G) = min{k| there exists a k-AVEEC of G} is called the adjacent vertex-distinguishing equitable edge chromatic number of G. In this paper, we obtain the χáve (G) of some special graphs and present a conjecture.     

Antichains in the set of subsets of a multiset

A set F of distinct subsets x of a finite multiset M (that is, a set with several different kinds of elements) is a c-antichain if for no c + 1 elements x₀, x₁, …, x_c of F does x₀ ? x₁ ? ··· ? x_c hold. The weight of F, wF, is the total number of elements of M in the various elements x of F. For given integers f and c, we find min wF, where the minimum is taken over all f-element c-antichains F. Daykin [9, 10] has solved this problem for ordinary sets and Clements [3] has solved it for multisets, but only for c = 1.     

On the exactness of certain inequalities in approximation theory

We prove the following: for every sequence {F_v}, F_v ? 0, F_v > 0 there exists a functionf such that

1. E_n(f)?F_n (n=0, 1, 2, ...) and
2. A_kn^?k? _v=1 ⁿ v^k?1 F_v?1?Ω_k (f, n^?1) (n=1, 2, ...).

     

Complementary bases of a matroid

Let e₁, e′₁, e₂, e′₂, …, e_n, e′_n be the elements of matroid M. Suppose that {e₁, e₂, …;, e_n} is a base of M and that every circuit of M contains at least m + 1 elements. We prove that there exist at least 2^m bases, called complementary bases, of M with the property that only one of each complementary pair e_j, e′_j is contained in any base.We also prove an analogous result for the case where E is partitioned into E₁, E₂, …, E_n and the initial base contains |E_j| ? 1 elements from partition E_j.     

On systems of finite sets with constraints on their unions and intersections

Let F be a family of subsets of an n-element set. F is said to be of type (n, r, s) if A ∈ F, B ∈ F implies that |A ∪ B| ? n ? r, and |A ∩ B| ? s. Let f(n, r, s) = max {|F| : F is of type (n, r, s)}. We prove that f(n, r, s) ? f(n ? 1, r ? 1, s) + f(n ? 1, r + 1, s) if r > 0, n > s. And this result is used to give simple and unified proofs of Katona's and Frankl's results on f(n, r, s) when s = 0 and s = 1.     

Removable Singularities of Solutions of the Minimal Surface Equation

Suppose that G is a bounded domain in ? ⁿ (n ? 2), E ≠ G is a relatively closed set in G, and 0 < α < 1. We prove that E is removable for solutions of the minimal surface equation in the class C ^1,α(G)_loc if and only if the (n ? 1 + α)-dimensional Hausdorff measure of E is zero.     

Ideal Spaces of Measurable Operators Affiliated to A Semifinite Von Neumann Algebra

Suppose that M is a von Neumann algebra of operators on a Hilbert space H and τ is a faithful normal semifinite trace on M. Let E, F and G be ideal spaces on (M, τ). We find when a τ-measurable operator X belongs to E in terms of the idempotent P of M. The sets E+F and E·F are also ideal spaces on (M, τ); moreover, E·F = F·E and (E+F)·G = E·G+F·G. The structure of ideal spaces is modular. We establish some new properties of the L₁(M, τ) space of integrable operators affiliated to the algebra M. The results are new even for the *-algebra M = B(H) of all bounded linear operators on H which is endowed with the canonical trace τ = tr.     

Sequentially additive graphs

The concept of a simply sequentially additive graph is introduced as follows. A graph G with |V(G)|+|E(G)|=M is said to be simply sequentially additive if there is a bijection f:V(G)∪E(G)→{;1,2,…,M}; such that for each x = (u, ν) in E(G), f(x) = f(u) + f(ν). Various aspects of finding such numberinga or showing that none exist are discussed.     

Distance-restricted matching extension in planar triangulations

A graph G is said to have property E(m,n) if it contains a perfect matching and for every pair of disjoint matchings M and N in G with |M|=m and |N|=n, there is a perfect matching F in G such that M⊆F and N∩F=0?. In a previous paper (Aldred and Plummer 2001) [2], an investigation of the property E(m,n) was begun for graphs embedded in the plane. In particular, although no planar graph is E(3,0), it was proved there that if the distance among the three edges is at least two, then they can always be extended to a perfect matching. In the present paper, we extend these results by considering the properties E(m,n) for planar triangulations when more general distance restrictions are imposed on the edges to be included and avoided in the extension.     

Super (<Emphasis Type="Italic">a</Emphasis>, <Emphasis Type="Italic">d</Emphasis>)-edge-antimagic total labelings of complete bipartite graphs

An (a, d)-edge-antimagic total labeling of a graph G is a bijection f from V(G) ∪ E(G) onto {1, 2,…,|V(G)| + |E(G)|} with the property that the edge-weight set {f(x) + f(xy) + f(y) | xy ∈ E(G)} is equal to {a, a + d, a + 2d,...,a + (|E(G)| ? 1)d} for two integers a > 0 and d ? 0. An (a, d)-edge-antimagic total labeling is called super if the smallest possible labels appear on the vertices. In this paper, we completely settle the problem of the super (a, d)-edge-antimagic total labeling of the complete bipartite graph K_m,n and obtain the following results: the graph K_m,n has a super (a, d)-edge-antimagic total labeling if and only if either (i) m = 1, n = 1, and d ? 0, or (ii) m = 1, n ? 2 (or n = 1 and m ? 2), and d ∈ {0, 1, 2}, or (iii) m = 1, n = 2 (or n = 1 and m = 2), and d = 3, or (iv) m, n ? 2, and d = 1.     

Closed subsets of the domain whose image has the dimension of the range

It is shown that if dim Y < ∞ and if f(X) = Y is a mapping between compact metric spaces such that 1 ? m ? dim f^-1(y)?n for all y ? Y, then there exists a closed set K ? X such that dim K ? n ? m and dim f(K) = dim Y. This answers a question posed by J. Keesling and D. Wilson.     

Hamiltonian cycles in Dirac graphs

We prove that for any n-vertex Dirac graph (graph with minimum degree at least n/2) G=(V,E), the number, Ψ(G), of Hamiltonian cycles in G is at least

$exp_2 [2h(G) - n\log e - o(n)],$

where h(G)=maxΣ _e x _e log(1/x _e ), the maximum over x: E → ?⁺ satisfying Σ _e?υ x _e = 1 for each υ ∈ V, and log =log₂. (A second paper will show that this bound is tight up to the o(n).)

We also show that for any (Dirac) G of minimum degree at least d, h(G) ≥ (n/2) logd, so that Ψ(G) > (d/(e + o(1))) ⁿ . In particular, this says that for any Dirac G we have Ψ(G) > n!/(2 + o(1)) ⁿ , confirming a conjecture of G. Sárközy, Selkow, and Szemerédi which was the original motivation for this work.     

Edge-bipancyclicity of a hypercube with faulty vertices and edges

A bipartite graph G=(V,E) is said to be bipancyclic if it contains a cycle of every even length from 4 to |V|. Furthermore, a bipancyclic G is said to be edge-bipancyclic if every edge of G lies on a cycle of every even length. Let F_v (respectively, F_e) be the set of faulty vertices (respectively, faulty edges) in an n-dimensional hypercube Q_n. In this paper, we show that every edge of Q_n-F_v-F_e lies on a cycle of every even length from 4 to 2ⁿ-2|F_v| even if |F_v|+|F_e|?n-2, where n?3. Since Q_n is bipartite of equal-size partite sets and is regular of vertex-degree n, both the number of faults tolerated and the length of a longest fault-free cycle obtained are worst-case optimal.     

On the classification of conditionally integrable evolution systems in (1 + 1) dimensions

We generalize earlier results of Fokas and Liu and find all locally analytic (1 + 1)-dimensional evolution equations of order n that admit an N-shock-type solution with N ≤ n + 1. For this, we develop a refinement of the technique from our earlier work, where we completely characterized all (1+1)-dimensional evolution systems u _t = F (x, t, u, ?u/?x,..., ?ⁿ u/? x ⁿ) that are conditionally invariant under a given generalized (Lie-Bäcklund) vector field Q(x, t, u, ?u/?x,..., ?^k u/?x ^k)?/?u under the assumption that the system of ODEs Q = 0 is totally nondegenerate. Every such conditionally invariant evolution system admits a reduction to a system of ODEs in t, thus being a nonlinear counterpart to quasi-exactly solvable models in quantum mechanics.