Asymptotic bounds for the number of convex n-ominoes

Unit squares having their vertices at integer points in the Cartesian plane are called cells. A point set equal to a union of n distinct cells which is connected and has no finite cut set is called an n-omino. Two n-ominoes are considered the same if one is mapped onto the other by some translation of the plane. An n-omino is convex if all cells in a row or column form a connected strip. Letting c(n) denote the number of different convex n-ominoes, we show that the sequence ((c(n))¹ⁿ: n=1,2,…) tends to a limit γ and γ=2.309138….     

Hamiltonicity in (0–1)-polyhedra

The graph G(P) of a polyhedron P has a node corresponding to each vertex of P and two nodes are adjacent in G(P) if and only if the corresponding vertices of P are adjacent on P. We show that if P ? $\text{R}$ⁿ is a polyhedron, all of whose vertices have (0–1)-valued coordinates, then (i) if G(P) is bipartite, the G(P) is a hypercube; (ii) if G(P) is nonbipartite, then G(P) is hamilton connected. It is shown that if P ? $\text{R}$ⁿ has (0–1)-valued vertices and is of dimension d (≤n) then there exists a polyhedron P′ ? $\text{R}$^d having (0–1)-valued vertices such that $\text{G(P) ? G(P′)}$. Some combinatorial consequences of these results are also discussed.     

Über die Wurzelschranke für das Minimalgewicht von codes

Let d be the minimum distance of an (n, k) code $\text{C}$, invariant under an abelian group acting transitively on the basis of the ambient space over a field F with char F × n. Assume that $\text{C}$ contains the repetition code, that dim($\text{C}$ ∏ $\text{C}$^⊥) = k ? 1 and that the supports of the minimal weight vectors of $\text{C}$ form a 2-design. Then d² ? d + 1 ? n with equality if and only if the design is a projective plane of order d ? 1. The case d² ? d + 1 = n can often be excluded with Hall's multiplier theorem on projective planes, a theorem which follows easily from the tools developed in this paper Moreover, if d² ? d + 1 > n and F = GF(2) then (d ? 1)² ? n. Examples are the generalized quadratic residue codes.     

Boundedness of solutions of a system of integro-differential equations

Let b: [?1, 0] →$\text{R}$ be a nondecreasing, strictly convex C²-function with b(? 1) = 0, and let g: $\text{R}$ⁿ → $\text{R}$ⁿ be a locally Lipschitzian mapping, which is the gradient of a function G: $\text{R}$ⁿ → $\text{R}$. Consider the following vector-valued integro-differential equation of the Levin-Nohel type

$\text{x}\text{?}\text{(t)=?∝}{}_{\mathrm{?1}}{}^0\text{b(θ)g(x(t + θ))dθ}$

. (E) This equation is used in applications to model various viscoelastic phenomena. By LaSalle's invariance principle, every bounded solution x(t) goes to a connected set of zeros of g, as time t goes to infinity. It is the purpose of this paper to give several geometric criteria assuring the boundedness of solutions of (E) or some of its components.     

The extremal graph problem of the icosahedron

P. Turán has asked the following question:Let I¹² be the graph determined by the vertices and edges of an icosahedron. What is the maximum number of edges of a graph Gⁿ of n vertices if Gⁿ does not contain I¹² as a subgraph?We shall answer this question by proving that if n is sufficiently large, then there exists only one graph having maximum number of edges among the graphs of n vertices and not containing I¹². This graph Hⁿ can be defined in the following way:Let us divide n ? 2 vertices into 3 classes each of which contains [$\text{(n?2)}\text{3}$] or $\text{[}\text{(n?2)}\text{3}\text{] + 1}$ vertices. Join two vertices iff they are in different classes. Join two vertices outside of these classes to each other and to every vertex of these three classes.     

Triangles in arrangements of lines

A set of n lines in the projective plane divides the plane into a certain number of polygonal cells. We show that if we insist that all of these cells be triangles, then there are at most $\text{1}\text{3}\text{n(n ? 1) + 4 ?}\text{2}\text{7}\text{n}$ of them. We also observe that if no point of the plane belongs to more than two of the lines and n is at least 4, some of the cells must be either quadrangles or pentagons. We further show that for $\text{n ≧ 4}$, there is a set of n lines which divides the plane into at least $\text{1}\text{3}\text{n(n ? 3) + 4}$ triangles.     

Decomposable sets and weak invariance

Given a set X ? Rⁿ and a subspace B ? Rⁿ, we say that X is $\text{B}$-decomposable if there exists a direct sum complement $\text{M}$ of $\text{B}$ such that {X ∩ M ≠ ?} and X ? {X ∩ M} + B. A structural characterization of $\text{B}$-decomposability is obtained for compact convex X, which yields a procedure for verification of the property in case X is also polyhedral. Our application of $\text{B}$-decomposability is in control theory. It is proven that if a compact convex polyhedral set X is {Range(B)}-decomposable, then the system capability of weak invariance (holdability) of X under the linear autonomous control system x = Ax + Bu (without control restraints) is equivalent to the existence of a constant linear feedback law u = Fx under which X is holdable.     

Triangles in arrangements of lines

A set of n nonconcurrent lines in the projective plane (called an arrangment) divides the plane into polygonal cells. It has long been a problem to find a nontrivial upper bound on the number of triangular regions. We show that $\text{5}\text{12}\text{n(n ? 1)}$ is such a bound. We also show that if no three lines are concurrent, then the number of quadrilaterals, pentagons and hexagons is at least cn².     

On the ∂-Neumann problem for generalized functions

Using the new theory of generalized functions developed by one of the authors the $\text{?}$ equation in $\text{C}$ⁿ is studied. In particular it is proven that if G is any generalized function on $\text{C}$ (in the above sense) then there is a generalized function S on $\text{C}$ such that $\text{?S}\text{?}\text{z}\text{?}\text{= G}$. Several other results are proven valid in polydiscs of $\text{C}$ⁿ, for which differential forms whose coefficients are generalized functions are introduced.     

A better decomposition theorem for simply connected m-convex sets

A set S in R^d is said to be m-convex, m ? 2, if and only if for every m points in S, at least one of the line segments determined by these points lies in S. For S a closed m-convex set in R², various decomposition theorems have been obtained to express S as a finite union of convex sets. However, the previous bounds may be lowered further, and we have the following result:In case S is simply connected, then S is a union of σ(m) or fewer convex sets, where $\text{σ(m) = [(m ?}\text{N}\text{)(m ?}\text{3}\text{2}\text{) +}\text{3}\text{2}\text{]}$.Moreover, this result induces an improved decomposition in the general case as well.     

Periodic-type functionals and their extensions

Let Ω denote a simply connected domain in the complex plane and let $\text{K[Ω]}$ be the collection of all entire functions of exponential type whose Laplace transforms are analytic on Ω′, the complement of Ω with respect to the sphere. Define a sequence of functionals $\text{{L}{}_{\mathrm{n}}\text{}}\text{on}\text{K[Ω]}$ by $\text{L}{}_{\mathrm{n}}\text{(f) =}\text{1}\text{2πi}\text{∝}{}_{\mathrm{\Gamma }}\text{g}{}_{\mathrm{n}}\text{(ζ) F(ζ) dζ}$, where F denotes the Laplace transform of f, Γ ? Ω is a simple closed contour chosen so that F is analytic outside and on Ω, and g_n is analytic on Ω. The specific functionals considered by this paper are patterned after the Lidstone functions, L_2n(f) = f⁽²ⁿ⁾(0) and L_{2n + 1}(f) = f⁽²ⁿ⁾(1), in that their sequence of generating functions {g_n} are “periodic.” Set g_{pn + k}(ζ) = h_k(ζ) ζ^pn, where p is a positive integer and each h_k (k = 0, 1,…, p ? 1) is analytic on Ω. We find necessary and sufficient conditions for $\text{f ∈ k[Ω]}\text{with}\text{L}{}_{\mathrm{n}}\text{(f) = 0 (n = 0, 1,…)}$. DeMar previously was able to find necessary conditions [7]. Next, we generalize {L_n} in several ways and find corresponding necessary and sufficient conditions.     

Omega theorems for the iterated additive convolution of a nonnegative arithmetic function

Let R_k(n) denote the number of ways of representing the integers not exceeding n as the sum of k members of a given sequence of nonnegative integers. Suppose that $\text{1}\text{2}\text{< β < k}$, $\text{δ =}\text{β}\text{2}\text{?}\text{β}\text{(4}\text{min}\text{(β,}\text{k}\text{2}\text{))}$ and

$\text{ξ=}\text{1/2β if β<k/2,}\text{β?1/2 if β=1/2,}\text{(k ? 2)(k + 1)/2k if k/2<β<k.}$

R. C. Vaughan has shown that the relation R_k(n) = G(n) + o(n^δ log^?ξn) as n → +∞ is impossible when G(n) is a linear combination of powers of n and the dominant term of G(n) is cn^β, c > 0. P. T. Bateman, for the case k = 2, has shown that similar results can be obtained when G(n) is a convex or concave function. In this paper, we combine the ideas of Vaughan and Bateman to extend the theorems stated above to functions whose fractional differences are of one sign for large n. Vaughan's theorem is included in ours, and in the case $\text{β <}\text{k}\text{2}$ we show that a better choice of parameter improves Vaughan's result by enabling us to drop the power of log n from the estimate of the error term.     

A note on symmetric doubly-stochastic matrices

Each extreme point in the convex set Δ¹_n of all n×n symmetric doubly-stochastic matrices is shown to have the form $\text{1}\text{2}\text{(P + P}{}^{\mathrm{t}}\text{)}$, for some n×n permutation matrix P. The convex hull Σ_n of the integral points in Δ¹_n (i.e., the symmetric permutation matrices) is shown to consist of those matrices, X = (x_ij) in Δ¹_n satisfying Σ_i∈SΣ_j∈S?{i}x_ij ? 2k, for each subset S of {1, 2, …, n} having cardinality 2k + 1, for some k > 0.     

Nonlinear eigenvalue problems with positively convex operators

We consider the equation u = λAu (λ > 0), where A is a forced isotone positively convex operator in a partially ordered normed space with a complete positive cone K. Let Λ be the set of positive λ for which the equation has a solution u?K, and let Λ₀ be the set of positive λ for which a positive solution—necessarily the minimum one—can be obtained by an iteration u_n = λAu_n?1, u₀ = 0. We show that if K is normal, and if Λ is nonempty, then Λ₀ is nonempty, and each set Λ₀, Λ is an interval with $\text{inf}\text{(Λ}{}_0\text{) =}\text{inf}\text{(Λ) = 0}\text{and sup}\text{(Λ}{}_0\text{) =}\text{sup}\text{(Λ) (= λ1,}\text{say}\text{)}$; but we may have λ1 ? Λ₀ and λ1 ? Λ. Furthermore, if A is bounded on the intersection of K with a neighborhood of 0, then Λ₀ is nonempty. Let u⁰(λ) = lim_n→∞(λA)ⁿ(0) be the minimum positive fixed point corresponding to λ ? Λ₀. Then u⁰(λ) is a continuous isotone convex function of λ on Λ₀.     

On weighted lattice paths

A weighted lattice path from (1, 1) to (n, m) is a path consisting of unit vertical, horizontal, and diagonal steps of weight w. Let f(0), f(1), f(2), … be a nondecreasing sequence of positive integers; the path connecting the points of the set $\text{{(n, m) ¦ f(n ? 1) ? m ? f(n), n = 1, 2, …}}$ will be called the roof determined by f. We determine the number of weighted lattice paths from (1, 1) to (n + 1, f(n)) which do not cross the roof determined by f. We also determine the polynomials that must be placed in each cell below the roof such that if a 1 is placed in each cell whose lower left-hand corner is a point of the roof, every k × k square subarray comprised of adjacent rows and columns and containing at least one 1 will have determinant $\text{x(}\text{k}\text{2}\text{)}$.     

On subgraph number independence in trees

For finite graphs F and G, let N_F(G) denote the number of occurrences of F in G, i.e., the number of subgraphs of G which are isomorphic to F. If $\text{F}$ and $\text{G}$ are families of graphs, it is natural to ask then whether or not the quantities N_F(G), F∈$\text{F}$, are linearly independent when G is restricted to $\text{G}$. For example, if $\text{F}$ = {K₁, K₂} (where K_n denotes the complete graph on n vertices) and $\text{F}$ is the family of all (finite) trees, then of course N_K1(T) ? N_K2(T) = 1 for all T∈$\text{F}$. Slightly less trivially, if $\text{F}$ = {S_n: n = 1, 2, 3,…} (where S_n denotes the star on n edges) and $\text{G}$ again is the family of all trees, then Σ_n=1^∞(?1)ⁿ⁺¹N_Sn(T)=1 for all T∈$\text{G}$. It is proved that such a linear dependence can never occur if $\text{F}$ is finite, no F∈$\text{F}$ has an isolated point, and $\text{G}$ contains all trees. This result has important applications in recent work of L. Lovász and one of the authors (Graham and Lovász, to appear).     

2-Colored triangles in edge-colored complete graphs

If each edge of complete graph K_n is colored with one of k colors then it contains a triangle having two colors if $\text{k < 1 + n}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$. The result is best possible when n is the square of a prime.     

Integral formulas with distribution kernels for irreducible projections in L2 of a nilmanifold

Let N be a simply connected nilpotent Lie group and Γ a discrete uniform subgroup. The authors consider irreducible representations σ in the spectrum of the quasi-regular representation N × L²(Γ/N) → L²(Γ→) which are induced from normal maximal subordinate subgroups M ? N. The primary projection P_σ and all irreducible projections P ? P_σ are given by convolutions involving right Γ-invariant distributions D on Γ→, $\text{Pf(Γn) = D 1 f(Γn) = <D, n · f>}\text{all}\text{f ? C}{}^{\mathrm{\infty }}\text{(Γ/N)}$, where n · f(ζ) = f(ζ · n). Extending earlier work of Auslander and Brezin, and L. Richardson, the authors give explicit character formulas for the distributions, interpreting them as sums of characters on the torus T^κ = (Γ ∩ M) · [M, M]?M. By examining these structural formulas, they obtain fairly sharp estimates on the order of the distributions: if σ is associated with an orbit $\text{O}$ ? $\text{n}$¹ and if $\text{V}$ ? $\text{n}$¹ is the largest subspace which saturates θ in the sense that f ? $\text{O}$ ? f + $\text{V}$ ? $\text{O}$. As a corollary they obtain Richardson's criterion for a projection to map C⁰(Γ→) into itself. The authors also resolve a conjecture of Brezin, proving a Zero-One law which says, among other things, that if the primary projection P_σ maps C^r(Γ→) into C⁰(Γ→), so do all irreducible projections P ? P_σ. This proof is based on a classical lemma on the extent to which integral points on a polynomial graph in Rⁿ lie in the coset ring of Zⁿ (the finitely additive Boolean algebra generated by cosets of subgroups in Zⁿ). This lemma may be useful in other investigations of nilmanifolds.     

A Note on pinching sphere theorem

Let M²ⁿ be a 2n-dimensional compact, simply connected Riemannian manifold without boundary and S²ⁿ be the unit sphere of 2n+1 dimension Euclidean space $\text{R}{}^{\mathrm{2n+1}}$. We prove in this note that if the sectional curvature K_M varies in (0,1] and the volume V(M) is not larger than $\text{(}\text{3}\text{2}\text{+η)V(S}{}^{\mathrm{2n}}\text{)}$ for some positive number η depending only on n, then M²ⁿ is homeomorphic to S²ⁿ. To cite this article: Y. Wen, C. R. Acad. Sci. Paris, Ser. I 338 (2004).     

Répartition des densités des sous-suites d'une suite d'entiers

Let $\text{A}$ denote a strictly increasing sequence of integers; for any integer n, define A(n) to be the number of positive elements of $\text{A}$ not exceeding n. The upper and lower asymptotic densities of $\text{A}$ are defined by

We describe the set of pairs (d$\text{B}$, $\text{d}$$\text{B}$), where $\text{B}$ runs over all subsequences of $\text{A}$, as being a closed convex region of the plane. The converse statement is also proved.