Polynomial interpolation and sums of powers of integers

In this note, we revisit the problem of polynomial interpolation and explicitly construct two polynomials in n of degree k + 1, P_k(n) and Q_k(n), such that P_k(n) = Q_k(n) = f_k(n) for n = 1, 2,…?, k, where f_k(1), f_k(2),…?, f_k(k) are k arbitrarily chosen (real or complex) values. Then, we focus on the case that f_k(n) is given by the sum of powers of the first n positive integers S_k(n) = 1^k + 2^k + ??? + n^k, and show that S_k(n) admits the polynomial representations S_k(n) = P_k(n) and S_k(n) = Q_k(n) for all n = 1, 2,…?, and k ≥ 1, where the first representation involves the Eulerian numbers, and the second one the Stirling numbers of the second kind. Finally, we consider yet another polynomial formula for S_k(n) alternative to the well-known formula of Bernoulli.     

Chromatic factorizations of a graph

Let n₁ ? n₂ ? …? ? n_k ? 2 be integers. We say that G has an (n₁, n₂, …?, n_k-chromatic factorization if G) can be edge-factored as G₁ ⊕ G₂ ⊕ …? ⊕ G_k with χ(G_i) = nA_i, for i = 1,2,…, k. The following results are proved:

• i If (n₁ ? 1)n₂ …? n_k < χ(G) ? n₁n₂ …? n_k, then G has an (n₁, n₂, …?, n_k)-chromatic factorization.
• ii If n₁ + n₂ + …? + n_k ? (k - 1) ? n ? n₁n₂ …? n_k, then K_n has an (n₁, n₂, …?, n_k)-chromatic factorization.

     

Ideal einstein,conformally flat and semi-symmetric immersions

Recently, B. Y. Chen introduced a new intrinsic invariant of a manifold, and proved that everyn-dimensional submanifold of real space formsR ^m (ε) of constant sectional curvature ε satisfies a basic inequality δ(n ₁,…,n _k )≤c(n ₁,…,n _k )H ²+b(n ₁,…,n _k )ε, whereH is the mean curvature of the immersion, andc(n ₁,…,n _k ) andb(n ₁,…,n _k ) are constants depending only onn ₁,…,n _k ,n andk. The immersion is calledideal if it satisfies the equality case of the above inequality identically for somek-tuple (n ₁,…,n _k ). In this paper, we first prove that every ideal Einstein immersion satisfyingn≥n ₁+…+n _k +1 is totally geodesic, and that every ideal conformally flat immersion satisfyingn≥n ₁+…+n _k +2 andk≥2 is also totally geodesic. Secondly we completely classify all ideal semi-symmetric hypersurfaces in real space forms. The author was supported by the NSFC and RFDP.     

Singular Manakov flows and geodesic flows on homogeneous spaces of SO(N)

We prove complete integrability of the Manakov-type SO(n)-invariant geodesic flows on homogeneous spaces SO(n)/SO(k₁) ×⋯× SO(k _r ), for any choice of k ₁,…,k _r , k ₁ + ⋯ + k _r ⩽ n. In particular, a new proof of the integrability of a Manakov symmetric rigid body motion around a fixed point is presented. Also, the proof of integrability of the SO(n)-invariant Einstein metrics on SO(k ₁ + k ₂ + k ₃)/SO(k ₁) × SO(k ₂) × SO(k ₃) and on the Stiefel manifolds V (n, k) = SO(n)/SO(k) is given.     

On the fluctuations of independent copies of moving maxima

Let {X_n, n1} be a sequence of independent random variables (r.v.'s) with a common distribution function (d.f.) F. Define the moving maxima Y_k(n)=max(X_n−k(n)+1,X_n−k(n)+2,…,X_n), where {k(n), n1} is a sequence of positive integers. Let Y_k(n)¹ and Y_k(n)² be two independent copies of Y_k(n). Under certain conditions on F and k(n), the set of almost sure limit points of the vector consisting of properly normalised Y_k(n)¹ and Y_k(n)² is obtained.     

Monotonicity of permanents of direct sums of doubly stochastic matrices

Let Ωn be the set of all n × n doubly stochastic matrices, let J_n be the n × n matrix all of whose entries are 1/n and let σ _k (A) denote the sum of the permanent of all k × k submatrices of A. It has been conjectured that if A ε Ω _n and A ≠ J_J then g_A,k (θ) ? σ _k ((1 θ)J_n 1 θA) is strictly increasing on [0,1] for k = 2,3,…,n. We show that if A = A ₁ ⊕ ⊕A_t (t ≥ 2) is an n × n matrix where A_i for i = 1,2, …,t, and if for each i g_Ai,ki (θ) is non-decreasing on [0.1] for k_t = 2,3,…,n_i , then g_A,k (θ) is strictly increasing on [0,1] for k = 2,3,…,n.     

Exchangeable and partially exchangeable random partitions

Summary Call a random partition of the positive integerspartially exchangeable if for each finite sequence of positive integersn ₁,...,n _k, the probability that the partition breaks the firstn ₁+...+n_k integers intok particular classes, of sizesn ₁,...,n_k in order of their first elements, has the same valuep(n ₁,...,n_k) for every possible choice of classes subject to the sizes constraint. A random partition is exchangeable iff it is partially exchangeable for a symmetric functionp(n ₁,...n_k). A representation is given for partially exchangeable random partitions which provides a useful variation of Kingman's representation in the exchangeable case. Results are illustrated by the two-parameter generalization of Ewens' partition structure.Research supported by N.S.F. Grants MCS91-07531 and DMS-9404345     

Representations of Integers as Sums of 32 Squares

In this paper, we derive a new explicit formula for r ₃₂(n), where r _k(n) is the number of representations of n as a sum of k squares. For a fixed integer k, our method can be used to derive explicit formulas for r _8k (n). We conclude the paper with various conjectures that lead to explicit formulas for r _2k (n), for any fixed positive integer k > 4.     

On Ramsey numbers involving starlike multipartite graphs

The Ramsey number r(G, H) is evaluated exactly in certain cases in which both G and H are complete multipartite graphs K(n,₁, n₂, …. n_k). Specifically, each of the following cases is handled whenever n is sufficiently large: r(K(1, m₁, …. m_k), K(1, n)), r(K(1, m), K(n₁, …. n_k, n)), provided m ≧ 4, and r(K(1, 1, m), K(n_k, …, n_k, n)).     

The smallest degree sum that yields potentially Pk-graphical sequences

A simple graph G is said to have property P_k if it contains a complete subgraph of order k + 1, and a sequence π is potentially P_k-graphical if it has a realization having property P_k. Let σ (k, n) denote the smallest degree sum such that every n-term graphical sequence π without zero terms and with degree sum σ(π) ≥ σ(k, n) is potentially P_k-graphical. Erdós, Jacobson, and Lehel [Graph Theory, 1991, 439–449] conjectured that σ(k, n) = (k − 1)(2n − k) + 2. In this article, we prove that the conjecture is true for k = 4 and n ≥ 10. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 63–72, 1998     

Sum Complexes—a New Family of Hypertrees

A k-dimensional hypertree X is a k-dimensional complex on n vertices with a full (k−1)-dimensional skeleton and \binomn-1k\binom{n-1}{k} facets such that H _k (X;ℚ)=0. Here we introduce the following family of simplicial complexes. Let n,k be integers with k+1 and n relatively prime, and let A be a (k+1)-element subset of the cyclic group ℤ _n . The sum complex X _A is the pure k-dimensional complex on the vertex set ℤ _n whose facets are σ⊂ℤ _n such that |σ|=k+1 and ∑ _x∈σ x∈A. It is shown that if n is prime, then the complex X _A is a k-hypertree for every choice of A. On the other hand, for n prime, X _A is k-collapsible iff A is an arithmetic progression in ℤ _n .     

On the Range of Possible Integrities of Graphs G(n, k)

We discuss the range of values for the integrity of a graphs G(n, k) where G(n, k) denotes a simple graph with n vertices and k edges. Let I _max(n, k) and I _min(n, k) be the maximal and minimal value for the integrity of all possible G(n, k) graphs and let the difference be D(n, k) = I _max(n, k) − I _min(n, k). In this paper we give some exact values and several lower bounds of D(n, k) for various values of n and k. For some special values of n and for s < n ^1/4 we construct examples of graphs G _n  = G _n (n, n + s) with a maximal integrity of I(G _n ) = I(C _n ) + s where C _n is the cycle with n vertices. We show that for k = n ²/6 the value of D(n, n ²/6) is at least \frac?6-13n{\frac{\sqrt{6}-1}{3}n} for large n.     

Edge disjoint Hamilton cycles in sparse random graphs of minimum degree at least k

Let G_n,m,k denote the space of simple graphs with n vertices, m edges, and minimum degree at least k, each graph G being equiprobable. Let G have property A_k, if G contains ⌊(k − 1)/2⌋ edge disjoint Hamilton cycles, and, if k is even, a further edge disjoint matching of size ⌊n/2⌋. We prove that, for k ≥ 3, there is a constant C_k such that if 2m ≥ C_kn then A_k occurs in G_n,m,k with probability tending to 1 as n → ∞. © 2000 John Wiley & Sons, Inc. J. Graph Theory 34: 42–59, 2000     

Posets and planar graphs

A k-decomposition (G₁,…,G_k) of a graph G is a partition of its edge set to form k spanning subgraphs G₁,…,G_k. The classical theorem of Nordhaus and Gaddum bounds χ(G₁) + χ(G₂) and χ(G₁)χ(G₂) over all 2-decompositions of K_n. For a graph parameter p, let p(k;G) denote the maximum of over all k-decompositions of the graph G. The clique number ω, chromatic number χ, list chromatic number χℓ, and Szekeres–Wilf number σ satisfy ω(2;K_n) = χ(2;K_n) = χℓ(2;K_n) = σ(2;K_n) = n + 1. We obtain lower and upper bounds for ω(k;K_n), χ(k;K_n), χℓ(k;K_n), and σ(k;K_n). The last three behave differently for large k. We also obtain lower and upper bounds for the maximum of χ(k;G) over all graphs embedded on a given surface. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Balancing the n-Cube: A Census of Colorings

Weights of 1 or 0 are assigned to the vertices of the n-cube in n-dimensional Euclidean space. Such an n-cube is called balanced if its center of mass coincides precisely with its geometric center. The seldom-used n-variable form of Pólya's enumeration theorem is applied to express the number N _{n, 2k} of balanced configurations with 2k vertices of weight 1 in terms of certain partitions of 2k. A system of linear equations of Vandermonde type is obtained, from which recurrence relations are derived which are computationally efficient for fixed k. It is shown how the numbers N _{n, 2k} depend on the numbers A _{n, 2k} of specially restricted configurations. A table of values of N _{n, 2k} and A _{n, 2k} is provided for n = 3, 4, 5, and 6. The case in which arbitrary, nonnegative, integral weights are allowed is also treated. Finally, alternative derivations of the main results are developed from the perspective of superposition.     

A note on a conjecture about cycles with many incident chords

Given positive integers n and k, let g_k(n) denote the maximum number of edges of a graph on n vertices that does not contain a cycle with k chords incident to a vertex on the cycle. Bollobás conjectured as an exercise in [2, p. 398, Problem 13] that there exists a function n(k) such that g_k(n) = (k + 1)n ? (k + 1)² for all n ≥ n(k). Using an old result of Bondy [ 3 ], we prove the conjecture, showing that n(k) ≤ 3 k + 3. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 180–182, 2004     

ON THE ITERATED ω-RULE

Let Γ_n(φ) be a formula of L_PA (PA = Peano Arithmetic) meaning “there is a proof of φ from PA-axioms, in which ω-rule is iterated no more than n times”. We examine relations over pairs of natural numbers of the kind. (n, k) ≦_H (n', k') iff PA + RFN_n' (H_k') ? RFN_n (H_k). Where H denotes one of the hierarchies ∑ or Π and RFN_n(C) is the scheme of the reflection principle for Γ_n restricted to formulas from the class C(Γ_n(φ) implies “φ is true”, for every φ ∈ C). Our main result is that. (n, k) ≦H (n', k') if n ≦ n' and k ≦ max (k', 2n' + 1).     

The number of connected sparsely edged graphs. II. Smooth graphs and blocks

A smooth graph is a connected graph without endpoints; f(n, q) is the number of connected graphs, v(n, q) is the number of smooth graphs, and u(n, q) is the number of blocks on n labeled points and q edges: W_k, V_k, and U_k are the exponential generating functions of f(n, n + k), v(n, n + k), and u(n, n + k), respectively. For any k ? 1, our reduction method shows that V_k can be deduced at once from W_k, which was found for successive k by the computer method described in our previous paper. Again the reduction method shows that U_k must be a sum of powers (mostly negative) of 1 - X and, given this information, we develop a recurrence method well suited to calculate U_k for successive k. Exact formulas for v(n, n + k) and u(n, n + k) for general n follow at once.     

On free semilattice-ordered semigroups satisfying x n =x

Let B(k,0,n) denote the group with k generators which is free in the group variety defined by the identity x ⁿ =1. Let B _slo (k,1,n) denote the semilattice-ordered semigroup with k generators which is free in the semilattice-ordered semigroup variety defined by the identity x ⁿ =x. We prove a generalization of the Green-Rees theorem: B _slo (k,1,n) is finite for all k≥1 if and only if B(k,0,n−1) is finite for all k≥1. We find a formula for card(B _slo (1,1,n)). We construct B _slo (k,1,n) for some concrete values of k and n.     

Linear Extensions of Semiorders: II

Let M _n (k) denote the family of posets on n points with k ordered pairs that maximize the number of linear extensions among all such posets. Fishburn and Trotter [2] prove that every poset in M _n (k) is a semiorder and identifies all semiorders in M _n (k) for k n. The present paper specifies M _n (k) for all k 2 n – 3.