Lattice Points, Dedekind Sums, and Ehrhart Polynomials of Lattice Polyhedra

Abstract. Let σ be a simplex of R ^N with vertices in the integral lattice Z ^N . The number of lattice points of mσ (={mα : α ∈ σ}) is a polynomial function L(σ,m) of m ≥ 0 . In this paper we present: (i) a formula for the coefficients of the polynomial L(σ,t) in terms of the elementary symmetric functions; (ii) a hyperbolic cotangent expression for the generating functions of the sequence L(σ,m) , m ≥ 0 ; (iii) an explicit formula for the coefficients of the polynomial L(σ,t) in terms of torsion. As an application of (i), the coefficient for the lattice n -simplex of R ⁿ with the vertices (0,. . ., 0, a _j , 0,. . . ,0) (1≤ j≤ n) plus the origin is explicitly expressed in terms of Dedekind sums; and when n=2 , it reduces to the reciprocity law about Dedekind sums. The whole exposition is elementary and self-contained.     

Spline monotone approximation with linear differential operators

Let f∈C³[a,b] and L be a linear differential operator such that L(f)≥0. Then there exists a sequence Q_n, n≥1, of polynomial splines with equally spaced knots, such that Q^(r), approximates f^(r), 0≤r≤s, simultaneously in the uniform norm. This approximation is given through inequalities with rates, involving a measure of smoothness to f^(s); so that L (Q_n)≥0. The encountered cases are the continuous, periodic and discrete.     

Completely symmetric configurations for <Emphasis Type="Italic">σ</Emphasis>-games on grid graphs

The paper deals with σ-games on grid graphs (in dimension 2 and more) and conditions under which any completely symmetric configuration of lit vertices can be reached – in particular the completely lit configuration – when starting with the all-unlit configuration. The answer is complete in dimension 2. In dimension ≥3, the answer is complete for the σ ⁺-game, and for the σ ⁻-game if at least one of the sizes is even. The case σ ⁻, dimension ≥3 and all sizes odd remains open.     

Operators on the Lattice of Pseudovarieties of Finite Semigroups

L (F) of pseudovarieties of finite semigroups that attempts to take full advantage of the underlying lattice structure, Auinger, Hall and the present authors recently introduced fourteen complete congruences on L (F). Such congruences provide a framework from which to study L (F) both locally and globally. For each such congruence ρ and each U∈L (F) the ρ-class of U is an interval [U ^ρ, U _ρ]. This provides a family of operators of the form U⇒Uρ on L (F) that reveal important relationships between elements of L (F). Various aspects of these operators are considered including characterizations of U ^ρ, bases of pseudoidentities for U ^ρ, instances of commutativity (U ^ρ)^σ = U ^σ)^ρ, as well as the semigroups generated by certain pairs of such operators.     

On the chromatic polynomial of a graph

Let P(G,λ) be the chromatic polynomial of a graph G with n vertices, independence number α and clique number ω. We show that for every λ≥n, ()^α≤≤ () ^{n −ω}. We characterize the graphs that yield the lower bound or the upper bound.?These results give new bounds on the mean colour number μ(G) of G: n− (n−ω)() ^{n −ω}≤μ(G)≤n−α() ^α. Received: December 12, 2000 / Accepted: October 18, 2001?Published online February 14, 2002     

Each 3-strong Tournament Contains 3 Vertices Whose Out-arcs Are Pancyclic

An arc in a tournament T with n ≥ 3 vertices is called pancyclic, if it is in a cycle of length k for all 3 ≤ k ≤ n. Yeo (Journal of Graph Theory, 50 (2005), 212–219) proved that every 3-strong tournament contains two distinct vertices whose all out-arcs are pancyclic, and conjectured that each 2-strong tournament contains 3 such vertices. In this paper, we confirm Yeo’s conjecture for 3-strong tournaments. The author is an associate member of “Graduiertenkolleg: Hierarchie und Symmetrie in mathematischen Modellen (DFG)” at RWTH Aachen University, Germany.     

Tight Distance-Regular Graphs and the Q-Polynomial Property

 Let Γ denote a distance-regular graph with diameter d≥3, and assume Γ is tight (in the sense of Jurišić, Koolen and Terwilliger). Let θ denote the second largest or smallest eigenvalue of Γ, and let σ₀,σ₁,…,σ _d denote the associated cosine sequence. We obtain an inequality involving σ₀,σ₁,…,σ _d for each integer i (1≤i≤d−1), and we show equality for all i is closely related to Γ being Q-polynomial with respect to θ. We use this idea to investigate the Q-polynomial structures in tight distance-regular graphs. Received: January 30, 1998 Final version received: August 14, 1998     

A Polytope Related to Empirical Distributions, Plane Trees, Parking Functions, and the Associahedron

Abstract. The volume of the n -dimensional polytope Π _n (x):= {y ∈ R ⁿ : y _i ≥ 0 and y ₁ + · · · + y _i ≤ x ₁ + · · ·+ x _i for all 1 ≤ i ≤ n } for arbitrary x:=(x ₁ , . . ., x _n ) with x _i >0 for all i defines a polynomial in variables x _i which admits a number of interpretations, in terms of empirical distributions, plane partitions, and parking functions. We interpret the terms of this polynomial as the volumes of chambers in two different polytopal subdivisions of Π _n (x) . The first of these subdivisions generalizes to a class of polytopes called sections of order cones. In the second subdivision the chambers are indexed in a natural way by rooted binary trees with n+1 vertices, and the configuration of these chambers provides a representation of another polytope with many applications, the associahedron .     

A Property About Minimum Edge- and Minimum Clique-Cover of a Graph

 Let G be a graph with n vertices, and denote as γ(G) (as θ(G)) the cardinality of a minimum edge cover (of a minimum clique cover) of G. Let E (let C) be the edge-vertex (the clique-vertex) incidence matrix of G; write then P(E)={x∈ℜ ⁿ :Ex≤1,x≥0}, P(C)={x∈ℜ ⁿ :Cx≤1,x≥0}, α _E (G)=max{1 ^T x subject to x∈P(E)}, and α _C (G)= max{1 ^T x subject to x∈P(C)}. In this paper we prove that if α _E (G)=α _C (G), then γ(G)=θ(G). Received: May 20, 1998?Final version received: April 12, 1999     

Limsup results and LIL for partial sum processes of a Gaussian random field

Let {ξ _j ; j ∈ ℤ₊ ^d be a centered stationary Gaussian random field, where ℤ₊ ^d is the d-dimensional lattice of all points in d-dimensional Euclidean space ℝ^d, having nonnegative integer coordinates. For each j = (j ₁ , ..., jd) in ℤ₊ ^d , we denote |j| = j ₁ ... j _d and for m, n ∈ ℤ₊ ^d , define S(m, n] = Σ _m<j≤n ζ _j , σ²(|n−m|) = ES ² (m, n], S _n = S(0, n] and S ₀ = 0. Assume that σ(|n|) can be extended to a continuous function σ(t) of t > 0, which is nondecreasing and regularly varying with exponent α at b ≥ 0 for some 0 < α < 1. Under some additional conditions, we study limsup results for increments of partial sum processes and prove as well the law of the iterated logarithm for such partial sum processes. Research supported by NSERC Canada grants at Carleton University, Ottawa     

The roots of <Emphasis Type="Italic">σ</Emphasis>-polynomials

Let G be a connected graph. We denote by σ(G,x) and δ(G) respectively the σ-polynomial and the edge-density of G, where . If σ(G,x) has at least an unreal root, then G is said to be a σ-unreal graph. Let δ(n) be the minimum edgedensity over all n vertices graphs with σ-unreal roots. In this paper, by using the theory of adjoint polynomials, a negative answer to a problem posed by Brenti et al. is given and the following results are obtained: For any positive integer a and rational number 0≤c≤1, there exists at least a graph sequence {G _i}_1≤i≤a such that G _i is σ-unreal and δ(G _i)→c as n→∞ for all 1 ≤i≤a, and moreover, δ(n)→0 as n→∞. Supported by the National Natural Science Foundation of China (10061003) and the Science Foundation of the State Education Ministry of China.     

Strong mean approximation on HP(Tn) for the Riesz means at the critical index

In this note we extend the results in [1] to high dimensions. Let f∈H^p (Tⁿ), 0<p<1, n≥1 andσ ^δ , f denote the Riesz means of f at the critical index δ=n/p−(n+1)/2. We have the following estimate: were 0<s≤2 and , is the K-functional in H^p(Tⁿ). Supported by NSFC     

Chromatic uniqueness of certain complete tripartite graphs

Let P(G, λ) be the chromatic polynomial of a graph G. A graph G is chromatically unique if for any graph H, P(H, λ) = P(G, λ) implies H is isomorphic to G. Liu et al. [Liu, R. Y., Zhao, H. X., Ye, C. F.: A complete solution to a conjecture on chromatic uniqueness of complete tripartite graphs. Discrete Math., 289, 175–179 (2004)], and Lau and Peng [Lau, G. C., Peng, Y. H.: Chromatic uniqueness of certain complete t-partite graphs. Ars Comb., 92, 353–376 (2009)] show that K(p − k, p − i, p) for i = 0, 1 are chromatically unique if p ≥ k + 2 ≥ 4. In this paper, we show that if 2 ≤ i ≤ 4, the complete tripartite graph K(p − k, p − i, p) is chromatically unique for integers k ≥ i and p ≥ k ²/4 + i + 1.     

On the Hopfield model at the critical temperature

We study the Hopfield model at temperature 1, when thenumber M(N) of patterns grows a bit slower than N. We reach a goodunderstanding of the model whenever M(N)≤N/(log N)¹¹. For example, we show that if M(N)→∞, for two typical configurations σ ¹, σ ², (∑ _{i ≤ N} σ¹ _i σ² _i )² is close to NM(N). Received: 15 December 1999 / Revised version: 8 December 2000 / Published online: 23 August 2001     

The natural functions on the cotangent bundle of higher order vector tangent bundles over fibered manifolds

For natural numbers r,s,q,m,n with s≥r≤q we determine all natural functions g: T ^*(J ^(r,s,q)(Y, R ^1,1)₀)^*→R for any fibered manifold Y with m-dimensional base and n-dimensional fibers. For natural numbers r,s,m,n with s≥r we determine all natural functions g: T ^*(J ^(r,s) (Y, R)₀)^*→R for any Y as above.     

On linguistic dynamical systems,families of graphs of large girth,and cryptography

The paper is devoted to the study of a linguistic dynamical system of dimension n ≥ 2 over an arbitrary commutative ring K, i.e., a family F of nonlinear polynomial maps f _α : K ⁿ → K ⁿ depending on “time” α ∈ {K − 0} such that f _α ⁻¹ = f _−αM, the relation f _α1 (x) = f _α2 (x) for some x ∈ Kⁿ implies α₁ = α₂, and each map f _α has no invariant points. The neighborhood {f _α (υ)∣α ∈ K − {0}} of an element v determines the graph Γ(F) of the dynamical system on the vertex set Kⁿ. We refer to F as a linguistic dynamical system of rank d ≥ 1 if for each string a = (α₁, υ, α₂), s ≤ d, where α_i + α_i+1 is a nonzero divisor for i = 1, υ, d − 1, the vertices υ _a = f _α1 × ⋯ × f _αs (υ) in the graph are connected by a unique path. For each commutative ring K and each even integer n ≠= 0 mod 3, there is a family of linguistic dynamical systems L_n(K) of rank d ≥ 1/3n. Let L(n, K) be the graph of the dynamical system L_n(q). If K = F_q, the graphs L(n, F_q) form a new family of graphs of large girth. The projective limit L(K) of L(n, K), n → ∞, is well defined for each commutative ring K; in the case of an integral domain K, the graph L(K) is a forest. If K has zero divisors, then the girth of K drops to 4. We introduce some other families of graphs of large girth related to the dynamical systems L_n(q) in the case of even q. The dynamical systems and related graphs can be used for the development of symmetric or asymmetric cryptographic algorithms. These graphs allow us to establish the best known upper bounds on the minimal order of regular graphs without cycles of length 4n, with odd n ≥ 3. Bibliography: 42 titles. Published in Zapiski Nauchnykh Seminarov POMI, Vol. 326, 2005, pp. 214–234.     

Acyclick-strong coloring of maps on surfaces

A coloring of graph vertices is called acyclic if the ends of each edge are colored in distinct colors and there are no two-colored cycles. Suppose each face of rank not greater thank, k ≥ 4, on a surfaceS ^N is replaced by the clique on the same set of vertices. Then the pseudograph obtained in this way can be colored acyclically in a set of colors whose cardinality depends linearly onN and onk. Results of this kind were known before only for 1 ≤N ≤ 2 and 3 ≤k ≤ 4. Translated fromMatematicheskie Zametki, vol. 67, No. 1, pp. 36–45, January, 2000.     

Wavelet characterization of Hörmander symbol classS ρ,δ m and applications

In this paper, we characterize the symbol in Hormander symbol classS _ρ ^m ,δ (m ∈ R, ρ, δ ≥ 0) by its wavelet coefficients. Consequently, we analyse the kerneldistribution property for the symbol in the symbol classS _ρ ^m ,δ (m ∈R, ρ > 0, δ≥ 0) which is more general than known results ; for non-regular symbol operators, we establish sharp L²-continuity which is better than Calderón and Vaillancourt’s result, and establishL ^p (1 ≤p ≤∞) continuity which is new and sharp. Our new idea is to analyse the symbol operators in phase space with relative wavelets, and to establish the kernel distribution property and the operator’s continuity on the basis of the wavelets coefficients in phase space.     

On the maximal operator of (<Emphasis Type="Italic">C</Emphasis>, α)-means of Walsh–Kaczmarz–Fourier series

Simon [J. Approxim. Theory, 127, 39–60 (2004)] proved that the maximal operator σ^α,κ,* of the (C, α)-means of the Walsh–Kaczmarz–Fourier series is bounded from the martingale Hardy space H _p to the space L _p for p > 1 / (1 + α), 0 < α ≤ 1. Recently, Gát and Goginava have proved that this boundedness result does not hold if p ≤ 1 / (1 + α). However, in the endpoint case p = 1 / (1 + α ), the maximal operator σ^α,κ,* is bounded from the martingale Hardy space H _1/(1+α) to the space weak- L _1/(1+α). The main aim of this paper is to prove a stronger result, namely, that, for any 0 < p ≤ 1 / (1 + α), there exists a martingale f ∈ H _p such that the maximal operator σ^α,κ,* f does not belong to the space L _p .