The k-factor conjecture is true

A sequence 〈d_i〉, 1≤i≤n, is called graphical if there exists a graph whose i^th vertex has degree d_i for all i. It is shown that the sequences 〈d_i〉 and 〈d_i-k〉 are graphical only if there exists a graph G whose degree sequence is 〈d_i〉 and which has a regular subgraph with k lines at each vertex. Similar theorems have been obtained for digraphs. These theorems resolve comjectures given by A.R. Rao and S.B. Rao, and by B. Grünbaum.     

Modifications of object sizes and box capacities to achieve a simultaneous fitting

Given a set of k objects of positive integral sizes {s_i} and a set of n boxes of positive integral capacities {b₁} we define a compatibility relation between each box and some subset of objects such that the condition $\text{s}{}_{\mathrm{i}}\text{? b}{}_1$ is necessary but not sufficient for object i to be compatible with box j. A simultaneous fitting of objects in boxes is one where every object is compatible to its box and no box has its capacity exceeded. In this paper, a necessary condition for the existence of such a fitting is stated. It is shown that this condition is sufficient for the existence of fittings under certain modifications of sizes or capacities. Two measures of the magnitude of the needed modification are introduced and examined.     

Note on the outdegree of a node in random recursive trees

In this note we find the exact probability distribution ofd _n,i , the outdegree of the nodei in a random recursive tree withn nodes, Fori=i _n increasing as a linear function onn, we show thatd _n ,i _n is asymptotically normal.     

Maximizing a lower bound on the computational complexity

We solve a combinatorial problem that arises in determining by a method due to Engeler lower bounds for the computational complexity of algorithmic problems. Denote by G_d the class of permutation groups G of degree d that are iterated wreath products of symmetric groups, i.e. G = S_dh?11?1S_d0 with Π^h?1_i=0d_i = d for some natural number h and some sequence (d₀,…,d_h?1) of natural numbers greater than 1. The problem is to characterize those G = S_dh?11?1S_d0 in G_d on which k(G):=log|G|/max_0≤i≤h?1log(d_i!) assumes its maximum. Our solution consists of two necessary conditions for this, namely that d₀≤d₁≤?≤d_h and that d_h is the largest prime divisor of d. Consequently, if d is a prime power, say d = p^h with p prime, then a necessary and sufficient condition is that d_i = p, 0 ≤ i ≤ h ? 1.     

Approximation of functions of finite variation by superpositions of a Sigmoidal function

The aim of this note is to generalize a result of Barron [1] concerning the approximation of functions, which can be expressed in terms of the Fourier transform, by superpositions of a fixed sigmoidal function. In particular, we consider functions of the type h(x) = ∫ℝ^d ƒ (〈t, x〉)dμ(t), where μ is a finite Radon measure on ℝ^d and ƒ : ℝ → ℂ is a continuous function with bounded variation in ℝ We show (Theorem 2.6) that these functions can be approximated in L₂-norm by elements of the set G_n = {Σ_i=0^staggeredn c_ig(〈a_i, x〉 + b_i) : a_iℝ^d, b_i, c_iℝ}, where g is a fixed sigmoidal function, with the error estimated by C/n^1/2, where C is a positive constant depending only on f. The same result holds true (Theorem 2.9) for f : ℝ → ℂ satisfying the Lipschitz condition under an additional assumption that ∫ℝ^d6t6e^d|u(t)| > ∞     

An algorithmic proof of Tutte's f-factor theorem

Let G be a multigraph on n vertices, possibly with loops. An f-factor is a subgraph of G with degree f_i at the ith vertex for i = 1, 2,…, n. Tutte's f-factor theorem is proved by providing an algorithm that either finds an f-factor or shows that it does not exist and does this in O(n³) operations. Note that the complexity bound is independent of the number of edges of G and the degrees f_i. The algorithm is easily altered to handle the problem of looking for a symmetric integral matrix with given row and column sums by assigning loops degree one. A (g,f)-factor is a subgraph of G with degree d_i at the ith vertex, where g_i ? d_i ? f_i, for i = 1,2,…, n. Lovasz's (g,f)-factor theorem is proved by providing an O(n³) algorithm to either find a (g,f)-factor or show one does not exist.     

Intersection patterns of convex sets

LetK ₁,…K_n be convex sets inR ^d. For 0≦i denote byf _ithe number of subsetsS of {1,2,…,n} of cardinalityi+1 that satisfy ∩{K _i∶i∈S}≠Ø. We prove:Theorem.If f _d+r=0 for somer r>=0, then {fx161-1} This inequality was conjectured by Katchalski and Perles. Equality holds, e.g., ifK ₁=…=K_r=R^d andK _r+1,…,K_n aren?r hyperplanes in general position inR ^d. The proof uses multilinear techniques (exterior algebra). Applications to convexity and to extremal set theory are given.     

A distance-labelling problem for hypercubes

Let i₁≥i₂≥i₃≥1 be integers. An L(i₁,i₂,i₃)-labelling of a graph G=(V,E) is a mapping ?:V→{0,1,2,…} such that |?(u)−?(v)|≥i_t for any u,v∈V with d(u,v)=t, t=1,2,3, where d(u,v) is the distance in G between u and v. The integer ?(v) is called the label assigned to v under ?, and the difference between the largest and the smallest labels is called the span of ?. The problem of finding the minimum span, λ_i1,i2,i3(G), over all L(i₁,i₂,i₃)-labellings of G arose from channel assignment in cellular communication systems, and the related problem of finding the minimum number of labels used in an L(i₁,i₂,i₃)-labelling was originated from recent studies on the scalability of optical networks. In this paper we study the L(i₁,i₂,i₃)-labelling problem for hypercubes Q_d (d≥3) and obtain upper and lower bounds on λ_i1,i2,i3(Q_d) for any (i₁,i₂,i₃).     

An approximate approach of global optimization for polynomial programming problems

Many methods for solving polynomial programming problems can only find locally optimal solutions. This paper proposes a method for finding the approximately globally optimal solutions of polynomial programs. Representing a bounded continuous variable x_i as the addition of a discrete variable d_i and a small variable ϵ_i, a polynomial term x_ix_i can be expanded as the sum of d_ix_j, d_jϵ_i; and ϵ_iϵ_j. A procedure is then developed to fully linearize d_ix_j and d_je_i, and to approximately linearize ϵ_iϵ_j with an error below a pre-specified tolerance. This linearization procedure can also be extended to higher order polynomial programs. Several polynomial programming examples in the literature are tested to demonstrate that the proposed method can systematically solve these examples to find the global optimum within a pre-specified error.     

Injektive Moduln über Ringen linearer Differentialoperatoren

LetR be a division ring of characteristic 0 withn commuting (partial) differentiationsd _i . DefineR[d]=R[d ₁, ...,d _n ] to be all polynomials ind _i with coefficients inR. A typical element ofR[d] has the form Σ(r _α d ₁ ^α(1) ...d _n ^α(n) ∣α∈? ⁿ ) withr _αεR. Equality and addition are defined as in commuting polynomial rings, with multiplication induced by the relationsd _i r=rd _i +d _i (r) forrεR and 1≤i≤n. The power series ring $$[[X_1 ,...,X_n ]]R = [[X]]R = \{ \Sigma (X^\alpha r_\alpha \left| {\alpha \in \mathbb{N}^n )} \right|r_\alpha \in R\} $$ is anR[d]-module,d _i acting as partial differentiation ?/?X _i on[[X]]R andR acting via the ring homomorphism $$R \mathrel\backepsilon r \mapsto \Sigma (1/\alpha !) X^\alpha d_1^{\alpha (1)} ...d_n^{\alpha (n)} (r) \in [[X]]R$$ . Then the module[[X]]R is a big injective cogenerator in the sense of Roos [11]. This result is in a certain sense a dual of the Hilbert Basis Theorem: For each left idealL ofR[d] there exists afinite number of power seriesf ₁, ...,f _m such thatL is the annihilator of thef _i inR[d]. For commutative rings of differential operators the minimal injective cogeneratorM is explicitly described as a submodule of[[X]]R, especially forR=? we haveM=Σ(R[X] exp (ΣX _i a _i )|(a ₁, ...,a _n )εR ⁿ ) and all these power series are convergent.     

Topological obstructions for vertex numbers of Minkowski sums

We show that for polytopes P₁,P₂,…,Pr⊂Rd, each having ni?d+1 vertices, the Minkowski sum P₁+P₂+?+Pr cannot achieve the maximum of i_∏ni vertices if r?d. This complements a recent result of Fukuda and Weibel (2006), who show that this is possible for up to d−1 summands. The result is obtained by combining methods from discrete geometry (Gale transforms) and topological combinatorics (van Kampen-type obstructions).     

The topological type of the α-sections of convex sets

An α=(α₁,…,αk)(0?αi?1) section of a family {K₁,…,Kk} of convex bodies in Rd is a transversal halfspace H⁺ for which Vold(Ki∩H⁺)=αi⋅Vold(Ki) for every 1?i?k. Our main result is that for any well-separated family of strictly convex sets, the space of α-sections is diffeomorphic to Sd−k.     

A note on lattice chains and Delannoy numbers

Fix nonnegative integers n₁,…,n_d and let L denote the lattice of integer points (a₁,…,a_d)∈Z^d satisfying 0?a_i?n_i for 1?i?d. Let L be partially ordered by the usual dominance ordering. In this paper we offer combinatorial derivations of a number of results concerning chains in L. In particular, the results obtained are established without recourse to generating functions or recurrence relations. We begin with an elementary derivation of the number of chains in L of a given size, from which one can deduce the classical expression for the total number of chains in L. Then we derive a second, alternative, expression for the total number of chains in L when d=2. Setting n₁=n₂ in this expression yields a new proof of a result of Stanley [Enumerative Combinatorics, vol. 2, Cambridge University Press, Cambridge, 1999] relating the total number of chains to the central Delannoy numbers. We also conjecture a generalization of Stanley's result to higher dimensions.     

Simple continued fractions for the Fredholm numbers

Let {a_i} with a₁ ≥ 2 be an infinite bounded sequence of positive integers, and d₁ = 1, d_i = ±1 for i = 2, 3,…. Let {Q_i} be another sequence defined by the recursion Q₁ = 1, Q_i = a_i?1Q_i?1^k for i = 2, 3,…, where k ≥ 2 an integer. Put C_k(a) = Σ_{i = 1}^∞d_iQ_i^?1. In this paper we shall determine the simple continued fraction expansion for the real numbers C_k(a).     

The combinatorial structure of random polytopes

Choose n random points in , let P_n be their convex hull, and denote by f_i(P_n) the number of i-dimensional faces of P_n. A general method for computing the expectation of f_i(P_n), i=0,…,d−1, is presented. This generalizes classical results of Efron (in the case i=0) and Rényi and Sulanke (in the case i=d−1) to arbitrary i. For random points chosen in a smooth convex body a limit law for f_i(P_n) is proved as n→∞. For random points chosen in a polytope the expectation of f_i(P_n) is determined as n→∞. This implies an extremal property for random points chosen in a simplex.     

Monotonicity of the probability of percolation for Bernoulli random fields on periodic graphs

In this work, the problem of percolation of the Bernoulli random field on periodic graphs ?? of an arbitrary dimension d is studied. A theorem on nondecreasing dependence of the probability of percolation Q(c ₁ , ?? , c _n ) with respect to each of the parameters c _i , i = 1÷n, ?C concentration of the Bernoulli field is proved.     

Langford sequences: perfect and hooked

A sequence {d, d+1,…, d+m?1} of m consecutive positive integers is said to be perfect if the integers {1, 2,…, 2m} can be arranged in disjoint pairs {(a_i, b_i): 1?i?m} so that {b_i?a_i: 1?i?m}={d,d+1,…,d+m?1}. A sequence is hooked if the set {1, 2,…, 2m?1 2m+1} can be arranged in pairs to satisfy the same condition. Well known necessary conditions for perfect sequences are herein shown to be sufficient. Similar necessary and sufficient conditions for hooked sequences are given.     

Tridiagonal matrices with nonnegative entries

In this paper, we characterize the nonnegative irreducible tridiagonal matrices and their permutations, using certain entries in their primitive idempotents. Our main result is summarized as follows. Let d denote a nonnegative integer. Let A denote a matrix in R and let denote the roots of the characteristic polynomial of A. We say A is multiplicity-free whenever these roots are mutually distinct and contained in R. In this case E_i will denote the primitive idempotent of A associated with theta_i(0?i?d). We say A is symmetrizable whenever there exists an invertible diagonal matrix Δ∈R such that ΔAΔ^-1 is symmetric. Let Γ(A) denote the directed graph with vertex set {0,1,…,d}, where i→j whenever i≠j and A_ij≠0.Theorem.Assume that each entry ofAis nonnegative. Then the following are equivalent for0≤s,t≤d.

(i)

The graphΓ(A)is a bidirected path with endpointss,t:s↔*↔*↔?↔*↔t.

(ii)

The matrixAis symmetrizable and multiplicity-free. Moreover the(s,t)-entry ofE_itimes(θ_i-θ₀)?(θ_i-θ_i-1)(θ_i-θ_i+1)?(θ_i-θ_d)is independent of i for0≤i≤d, and this common value is nonzero.

Recently Kurihara and Nozaki obtained a theorem that characterizes the Q-polynomial property for symmetric association schemes. We view the above result as a linear algebraic generalization of their theorem.