On island sequences of labelings with a condition at distance two

An L(2,1)-labeling of a graph G is a function f from the vertex set of G to the set of nonnegative integers such that |f(x)−f(y)|≥2 if d(x,y)=1, and |f(x)−f(y)|≥1 if d(x,y)=2, where d(x,y) denotes the distance between the pair of vertices x,y. The lambda number of G, denoted λ(G), is the minimum range of labels used over all L(2,1)-labelings of G. An L(2,1)-labeling of G which achieves the range λ(G) is referred to as a λ-labeling. A hole of an L(2,1)-labeling is an unused integer within the range of integers used. The hole index of G, denoted ρ(G), is the minimum number of holes taken over all its λ-labelings. An island of a given λ-labeling of G with ρ(G) holes is a maximal set of consecutive integers used by the labeling. Georges and Mauro [J.P. Georges, D.W. Mauro, On the structure of graphs with non-surjective L(2,1)-labelings, SIAM J. Discrete Math. 19 (2005) 208-223] inquired about the existence of a connected graph G with ρ(G)≥1 possessing two λ-labelings with different ordered sequences of island cardinalities. This paper provides an infinite family of such graphs together with their lambda numbers and hole indices. Key to our discussion is the determination of the path covering number of certain 2-sparse graphs, that is, graphs containing no pair of adjacent vertices of degree greater than 2.     

Chain enumeration of k-divisible noncrossing partitions of classical types

We give combinatorial proofs of the formulas for the number of multichains in the k-divisible noncrossing partitions of classical types with certain conditions on the rank and the block size due to Krattenthaler and Müller. We also prove Armstrong's conjecture on the zeta polynomial of the poset of k-divisible noncrossing partitions of type A invariant under a 180° rotation in the cyclic representation.     

A “simple” rectangular puzzle

In this note we describe a dynamic, d-dimensional toroidal puzzle, the duplication puzzle. It was first introduced in [Rosenfeld, M., A dynamic puzzle, Amer. Math. Monthly 98 (1991), 22–24]. We calculate some optimal solutions for the 2-dimensional toroidal puzzle, for higher dimensional tori and demonstrate how they might be used to improve known lower bounds of the Shannon Capacity of odd cycles.     

On the hole index of L(2,1)-labelings of r-regular graphs

An L(2,1)-labeling of a graph G is an assignment of nonnegative integers to the vertices of G so that adjacent vertices get labels at least distance two apart and vertices at distance two get distinct labels. A hole is an unused integer within the range of integers used by the labeling. The lambda number of a graph G, denoted λ(G), is the minimum span taken over all L(2,1)-labelings of G. The hole index of a graph G, denoted ρ(G), is the minimum number of holes taken over all L(2,1)-labelings with span exactly λ(G). Georges and Mauro [On the structure of graphs with non-surjective L(2,1)-labelings, SIAM J. Discrete Math. 19 (2005) 208-223] conjectured that if G is an r-regular graph and ρ(G)?1, then ρ(G) must divide r. We show that this conjecture does not hold by providing an infinite number of r-regular graphs G such that ρ(G) and r are relatively prime integers.     

Quantum Complexity of Integration

It is known that quantum computers yield a speed-up for certain discrete problems. Here we want to know whether quantum computers are useful for continuous problems. We study the computation of the integral of functions from the classical Hölder classes F^k, α_d on [0, 1]^d and define γ by γ=(k+α)/d. The known optimal orders for the complexity of deterministic and (general) randomized methods are comp(F^k, α_d, ε)≍ε^−1/γ and comp^random(F^k, α_d, ε)≍ε^−2/(1+2γ). For a quantum computer we prove comp^quant_query(F^k, α_d, ε)≍ε^−1/(1+γ) and comp^quant(F^k, α_d, ε)⩽Cε^−1/(1+γ)(log ε⁻¹)^1/(1+γ). For restricted Monte Carlo (only coin tossing instead of general random numbers) we prove comp^coin(F^k, α_d, ε)⩽Cε^−2/(1+2γ)(log ε⁻¹)^1/(1+2γ). To summarize the results one can say that   • there is an exponential speed-up of quantum algorithms over deterministic (classical) algorithms, if γ is small;   • there is a (roughly) quadratic speed-up of quantum algorithms over randomized classical methods, if γ is small.     

Uniform boundary Harnack principle and generalized triangle property

Let D be a bounded open subset in R^d, d?2, and let G denote the Green function for D with respect to (-Δ)^α/2, 0<α?2, α<d. If α<2, assume that D satisfies the interior corkscrew condition; if α=2, i.e., if G is the classical Green function on D, assume—more restrictively—that D is a uniform domain. Let g=G(·,y₀)∧1 for some y₀∈D. Based on the uniform boundary Harnack principle, it is shown that G has the generalized triangle property which states that when d(z,x)?d(z,y). An intermediate step is the approximation G(x,y)≈|x-y|^α-dg(x)g(y)/g(A)², where A is an arbitrary point in a certain set B(x,y).This is discussed in a general setting where D is a dense open subset of a compact metric space satisfying the interior corkscrew condition and G is a quasi-symmetric positive numerical function on D×D which has locally polynomial decay and satisfies Harnack's inequality. Under these assumptions, the uniform boundary Harnack principle, the approximation for G, and the generalized triangle property turn out to be equivalent.     

The traces of Bessel potentials on regular subsets of Carnot groups

We prove the direct theorem on the traces of the Bessel potentials L _p ^α defined on a Carnot group, on the regular closed subsets called Ahlfors d-sets. The result is convertible for integer α, i.e., for the Sobolev spaces W _p ^α (the converse trace theorem was proven in [24]). This theorem generalizes A. Johnsson and H. Wallin’s results [13] for Sobolev functions and Bessel potentials on the Euclidean space.     

A survey on labeling graphs with a condition at distance two

For positive integers k,d₁,d₂, a k-L(d₁,d₂)-labeling of a graph G is a function f:V(G)→{0,1,2,…,k} such that |f(u)-f(v)|?d_i whenever the distance between u and v is i in G, for i=1,2. The L(d₁,d₂)-number of G, λ_d1,d2(G), is the smallest k such that there exists a k-L(d₁,d₂)-labeling of G. This class of labelings is motivated by the code (or frequency) assignment problem in computer network. This article surveys the results on this labeling problem.     

Construction of bent functions via Niho power functions

A Boolean function with an even number n=2k of variables is called bent if it is maximally nonlinear. We present here a new construction of bent functions. Boolean functions of the form f(x)=tr(α₁x^d₁+α₂x^d₂), α₁,α₂,x∈F_2ⁿ, are considered, where the exponents d_i (i=1,2) are of Niho type, i.e. the restriction of x^d_i on F_2^k is linear. We prove for several pairs of (d₁,d₂) that f is a bent function, when α₁ and α₂ fulfill certain conditions. To derive these results we develop a new method to prove that certain rational mappings on F_2ⁿ are bijective.     

Homoclinic points and isomorphism rigidity of algebraic ℤ<Superscript><Emphasis Type="Italic">d</Emphasis></Superscript>-actions on zero-dimensional compact abelian groups

Letd>1, and letα andβ be mixing ? ^d -actions by automorphisms of zero-dimensional compact abelian groupsX andY, respectively. By analyzing the homoclinic groups of certain sub-actions ofα andβ we prove that, if the restriction ofα to some subgroup Γ ? ? ^d of infinite index is expansive and has completely positive entropy, then every measurable factor mapφ: (X, α)→(Y, β) is almost everywhere equal to an affine map. The hypotheses of this result are automatically satisfied if the actionα contains an expansive automorphismα ⁿ ,n ∈ ? ^d , or ifα arises from a nonzero prime ideal in the ring of Laurent polynomials ind variables with coefficients in a finite prime field. Both these corollaries generalize the main theorem in [9]. In several examples we show that this kind of isomorphism rigidity breaks down if our hypotheses are weakened.     

Bipartite labeling of trees with maximum degree three

Let T = (V, E) be a tree with a properly 2‐colored vertex set. A bipartite labeling of T is a bijection φ: V → {1, …, |V|} for which there exists a k such that whenever φ(u) ≤ k < φ(v), then u and v have different colors. The α‐size α(T) of the tree T is the maximum number of elements in the sets {|φ(u) − φ(v)|; uv ∈ E}, taken over all bipartite labelings φ of T. The quantity α(n) is defined as the minimum of α(T) over all trees with n vertices. In an earlier article (J Graph Theory 19 (1995), 201–215), A. Rosa and the second author proved that 5n/7 ≤ α(n) ≤ (5n + 4)/6 for all n ≥ 4; the upper bound is believed to be the asymptotically correct value of (n). In this article, we investigate the α‐size of trees with maximum degree three. Let α₃(n) be the smallest α‐size among all trees with n vertices, each of degree at most three. We prove that α₃(n) ≥ 5n/6 for all n ≥ 12, thus supporting the belief above. This result can be seen as an approximation toward the graceful tree conjecture—it shows that every tree on n ≥ 12 vertices and with maximum degree three has “gracesize” at least 5n/6. Using a computer search, we also establish that α₃(n) ≥ n − 2 for all n ≤ 17. © 1999 John Wiley & Sons, Inc. J Graph Theory 31:7–15, 1999     

Strong summability theorems for H p (Δ d )

We prove that certain means of the (C,α,…,α)-means (α=1/p?1) of the d-dimensional trigonometric Fourier series are uniformly bounded operators from the Hardy space H _p to H _p (1≦p≦2). As a consequence we obtain strong summability theorems concerning (C,α,…,α)-means.     

The existence of (p,q)-extended Rosa sequences

A (p,q)-extended Rosa sequence is a sequence of length 2n+2 containing each of the symbols 0,1,…,n exactly twice, and such that two occurrences of the integer j>0 are separated by exactly j-1 symbols. We prove that, with two exceptions, the conditions necessary for the existence of a (p,q)-extended Rosa sequence with prescribed positions of the symbols 0 are sufficient. We also extend the result to λ-fold (p,q)-extended Rosa sequences; i.e., the sequences where every pair of numbers is repeated exactly λ times.     

On second-order duality for a class of nondifferentiable minimax fractional programming problem with (C,α,ρ,d)-convexity

In this paper, we derive appropriate duality theorems for three second-order dual models of a nondifferentiable minimax fractional programming problem under second-order (C,α,ρ,d)-convexity assumptions. A nontrivial example has also been exemplified to show the existence of second-order (C,α,ρ,d)-convex functions. Several known results including many recent works are obtained as special cases.     

Extremal results for odd cycles in sparse pseudorandom graphs

We consider extremal problems for subgraphs of pseudorandom graphs. For graphs F and Г the generalized Turán density π _F (Г) denotes the relative density of a maximum subgraph of Г, which contains no copy of F. Extending classical Turán type results for odd cycles, we show that π _F (Г)=1/2 provided F is an odd cycle and Г is a sufficiently pseudorandom graph. In particular, for (n,d,λ)-graphs Г, i.e., n-vertex, d-regular graphs with all non-trivial eigenvalues in the interval [?λ,λ], our result holds for odd cycles of length ?, provided $$\lambda ^{\ell - 2} \ll \frac{{d^{\ell - 1} }} {n}\log (n)^{ - (\ell - 2)(\ell - 3)} .$$ Up to the polylog-factor this verifies a conjecture of Krivelevich, Lee, and Sudakov. For triangles the condition is best possible and was proven previously by Sudakov, Szabó, and Vu, who addressed the case when F is a complete graph. A construction of Alon and Kahale (based on an earlier construction of Alon for triangle-free (n,d;λ)-graphs) shows that our assumption on Г is best possible up to the polylog-factor for every odd ?≥5.     

On the Cauchy Problem for Integro-differential Operators in Hölder Classes and the Uniqueness of the Martingale Problem

The existence and uniqueness in Hölder spaces of classical solutions of the Cauchy problem to parabolic integro-differential equation of the order α ∈ (0, 2) is investigated. The principal part of the operator has kernel m(t, x, y)/|y| ^d?+?α with a bounded nondegenerate m, Hölder in x and measurable in y. The result is applied to prove the uniqueness of the corresponding martingale problem.     

One method for proving the impossibility of certain Moore graphs

A Moore (d, k)-graph is a regular graph of degree d with diameter k and girth 2k + 1. It is proved that every edge of a Moore (d, k)-graph is contained in the same number r_m cycles of length m, where m ? 4k + 1. A recurrence relation for r_m is given. Further, some corollaries, as for the impossibility of certain Moore graphs, are shown, e.g., if 3 ? d ? 100 and 3 ? k ? 100, then there is no Moore (d, k)-graph.     

On Rosa-type labelings and cyclic graph decompositions

A labeling (or valuation) of a graph G is an assignment of integers to the vertices of G subject to certain conditions. A hierarchy of graph labelings was introduced by Rosa in the late 1960s. Rosa showed that certain basic labelings of a graph G with n edges yielded cyclic G-decompositions of K _2n+1 while other stricter labelings yielded cyclic G-decompositions of K _2nx+1 for all natural numbers x. Rosa-type labelings are labelings with applications to cyclic graph decompositions. We survey various Rosa-type labelings and summarize some of the related results. (Communicated by Peter Horák)     

Subexponential estimates in the height theorem and estimates on numbers of periodic parts of small periods

This paper is devoted to subexponential estimates in Shirshov’s height theorem. A word W is n-divisible if it can be represented in the form W = W ₀ W ₁ ?W _n , where W ₁ ? W ₂ ??? W _n . If an affine algebra A satisfies a polynomial identity of degree n, then A is spanned by non-n-divisible words of generators a ₁ ??? a _l . A. I. Shirshov proved that the set of non-n-divisible words over an alphabet of cardinality l has bounded height h over the set Y consisting of all words of degree ≤ n ? 1. We show that h < Φ (n, l), where Φ(n, l) = 2⁸⁷ l?n ^{12 log3 n+48}. Let l, n, and d ≥ n be positive integers. Then all words over an alphabet of cardinality l whose length is greater than ψ(n, d, l) are either n-divisible or contain the dth power of a subword, where ψ(n, d, l) = 2¹⁸ l(nd)^{3 log3(nd)+13} d ². In 1993, E. I. Zelmanov asked the following question in the Dniester Notebook: Suppose that F _2,m is a 2-generated associative ring with the identity x ^m = 0. Is it true that the nilpotency degree of F _2,m has exponential growth? We give the definitive answer to E. I. Zelmanov by this result. We show that the nilpotency degree of the l-generated associative algebra with the identity x ^d = 0 is smaller than ψ(d, d, l). This implies subexponential estimates on the nilpotency index of nil-algebras of arbitrary characteristic. Shirshov’s original estimate was just recursive; in 1982 a double exponent was obtained, and an exponential estimate was obtained in 1992. Our proof uses Latyshev’s idea of an application of the Dilworth theorem. We think that Shirshov’s height theorem is deeply connected to problems of modern combinatorics. In particular, this theorem is related to the Ramsey theory. We obtain lower and upper estimates of the number of periods of length 2, 3, n ? 1 in some non-n-divisible word. These estimates differ only by a constant.