Irreducible posets with large height exist

The dimension of a poset (X, P) is the minimum number of linear extensions of P whose intersection is P. A poset is irreducible if the removal of any point lowers the dimension. If A is an antichain in X and X ? A ≠ Ø, then dim X ≤ 2 width ((X ? A) + 1. We construct examples to show that this inequality is best possible; these examples prove the existence of irreducible posets of arbitrarily large height. Although many infinite families of irreducible posets are known, no explicity constructed irreducible poset of height larger than four has been found.     

Embedding finite posets in cubes

In this paper we define the n-cube Q_n as the poset obtained by taking the cartesian product of n chains each consisting of two points. For a finite poset X, we then define dim₂X as the smallest positive integer n such that X can be embedded as a subposet of Q_n. For any poset X we then have log₂ |X| ? dim₂X ? |X|. For the distributive lattice $\text{L =}\text{2}{}^{\mathrm{X}}$, dim₂L = |X| and for the crown S^k_n, dim₂ (S^k_n) = n + k. For each k ? 2, there exist positive constants c₁ and c₂ so that for the poset X consisting of all one element and k-element subsets of an n-element set, the inequality c₁ log₂n < dim₂(X) < c₂ log₂n holds for all n with k < n. A poset is called Q-critical if dim₂ (X ? x) < dim₂(X) for every x ? X. We define a join operation ⊕ on posets under which the collection Q of all Q-critical posets which are not chains forms a semigroup in which unique factorization holds. We then completely determine the subcollection $\text{M}$ ? Q consisting of all posets X for which dim₂ (X) = |X|.     

k-dimensional skeletoids in Rn and the Hilbert cube

In their paper on pseudo-boundaries and pseudo-interiors R. Geoghegan and R.R. Summerhill construct k-dimensional pseudo-boundaries in $\text{R}$ⁿ, where they used West's notion of a pseudo-boundary, rather than Toruńczyk's. In this paper we construct pseudo-boundaries in the sense of Toruńczyk (skeletoids) in $\text{R}$ⁿ and use this result to find k-dimensional skeletoids in the Hilbert cube.     

On the spectral synthesis problem for hypersurfaces of RN

Let F¹(Rⁿ) denote the Fourier algebra on $\text{R}$ⁿ, and $\text{D}$($\text{R}$ⁿ) the space of test functions on $\text{R}$ⁿ. A closed subset E of $\text{R}$ⁿ is said to be of spectral synthesis if the only closed ideal J in F¹(Rⁿ) which has E as its hull

$\text{h(J)={x ? R}{}^{\mathrm{n}}\text{:f(x)=0}\text{for all}\text{f ? J}}$

is the ideal

$\text{k(E)={f?F}{}^1\text{(R}{}^{\mathrm{n}}\text{):f(E)=0}}$

. We consider sufficiently regular compact subsets of smooth submanifolds of $\text{R}$ⁿ with constant relative nullity. For such sets E we give an estimate of the degree of nilpotency of the algebra $\text{(k(E)∩D(R}{}^{\mathrm{n}}\text{))}{}^{\mathrm{?}}\text{j(E)}$, where j(E) denotes the smallest closed ideal in F¹(Rⁿ) with hull E. Especially in the case of hypersurfaces this estimate turns out to be exact. Moreover for this case we prove that k(E)∩D(Rⁿ) is dense in k(E). Together this solves the synthesis problem for such sets.     

On the series Σk = 1∞(k2k)−1k−n and related sums

Series of the form $\text{Σ}{}_{\mathrm{k\; =\; 1}}{}^{\mathrm{\infty }}\text{(}\text{2k}\text{2k}\text{)}{}^{\mathrm{?1}}\text{k}{}^{\mathrm{?n}}$ may be expressed as log sin integrals and are shown to be summable exactly in terms of Dirichlets L-series for values of n up to and including 5. Other related series are also discussed and several exact results are given.     

3-Interval irreducible partially ordered sets

In this paper we discuss the characterization problem for posets of interval dimension at most 2. We compile the minimal list of forbidden posets for interval dimension 2. Members of this list are called 3-interval irreducible posets. The problem is related to a series of characterization problems which have been solved earlier. These are: The characterization of planar lattices, due to Kelly and Rival [5], the characterization of posets of dimension at most 2 (3-irreducible posets) which has been obtained independently by Trotter and Moore [8] and by Kelly [4] and the characterization of bipartite 3-interval irreducible posets due to Trotter [9].We show that every 3-interval irreducible poset is a reduced partial stack of some bipartite 3-interval irreducible poset. Moreover, we succeed in classifying the 3-interval irreducible partial stacks of most of the bipartite 3-interval irreducible posets. Our arguments depend on a transformationP B(P), such that IdimP=dimB(P). This transformation has been introduced in [2].Supported by the DFG under grant FE 340/2–1.     

On some covering designs

Let n ? k ? t be positive integers, and let Ω be a set of n elements. Let C(n, k, t) denote the number of k-tuples of Ω in a minimal system of k-tuples such that every t-tuple is contained in at least one k-tuple of the system. C(n, k, t) has been determined in all cases for which $\text{C(n, k, t) ?}\text{3(t + 1)}\text{2}$ [W. H. Mills, Ars Combinatoria8 (1979), 199–315]. C(n, k, t) is determined in the case $\text{3(t + 1)}\text{2}\text{< C(n, k, t) ?}\text{3(t + 2)}\text{2}$.     

The enumeration of shift register sequences

A study is made of the number of cycles of length k which can be produced by a general n-stage feedback shift register. This problem is equivalent to finding the number of cycles of length k on the so-called de Bruijn-Good graph (Proc. K. Ned. Akad. Wet.49 (1946), 758–764; J. London Math. Soc.21 (3) (1946), 169–172). The number of cycles of length k in such a graph is denoted by β(n, k). From the-de Bruijn-Good graph, it can be shown that β(n, k) is also the number of cyclically distinct binary sequences of length k which have all k successive sets of n adjacent digits (called “n windows”) distinct (the sequence to be considered cyclically). After listing some known results for β(n, k), we show that

$\text{β(k?3, k)=β(k, k)?2φ}{}_{\mathrm{k,\; 2}}\text{+2}\text{for}\text{k?5}$

, where $\text{φ}{}_{\mathrm{k,\; r}}\text{?}$ the number of integers l ? k such that (k, l) ? r, and (k, l) denotes the greatest common divisor of k and l. From the results of several computer programs, it is conjectured that

$\text{β(k?4, k)=β(k, k)?4φ}{}_{\mathrm{k,\; 3}}\text{?2(k, 2)+10 (k?8)}$

,

$\text{β(k?5, k)=β(k, k)?8φ}{}_{\mathrm{k,\; 4}}\text{?(k, 3)+19 (k?11)}$

$\text{β(k?6, k)=β(k, k)?16φ}{}_{\mathrm{k,\; 5}}\text{?4(k, 2)?2(k, 3)+48 (k?15)}$

     

Size Ramsey numbers involving stars

We calculate some size Ramsey numbers involving stars. For example we prove that for t ? k ? 2 and n sufficiently large the size Ramsey number.

$\text{r}{}_{\mathrm{n}}\text{(K}{}_{\mathrm{1,k}}\text{K}{}_{\mathrm{t}}\text{+}\text{K}{}_{\mathrm{n}}\text{=}\text{k(t?1)+1}\text{2}\text{+(k(t?1)+1)(n+k?1).}$

     

Hecke operators and an identity for the dedekind sums

If h, k ∈ Z, k > 0, the Dedekind sum is given by

$\text{s(h,k) =}\text{∑}\text{μ=1}\text{k}\text{μ}\text{k}\text{hμ}\text{k}$

, with

$\text{((x)) = x ? [x] ?}\text{1}\text{2}\text{, x?Z}$

,

$\text{=0 , x∈Z}$

. The Hecke operators T_n for the full modular group SL(2, Z) are applied to log η(τ) to derive the identities (n ∈ Z⁺)

$\text{∑ ∑ s(ah+bk,dk) = σ(n)s(h,k)}$

,

$\text{ad=n b(}\text{mod}\text{d)}$

$\text{d>0}$

where (h, k) = 1, k > 0 and σ(n) is the sum of the positive divisors of n. Petersson had earlier proved (1) under the additional assumption k ≡ 0, h ≡ 1 (mod n). Dedekind himself proved (1) when n is prime.     

An upper bound on the Ramsey numbers R(3, k)

Ajtai, Komlós, and Szemerédi (J. Combin. Theory Ser. A29 (1980), 354–360) recently announced that $\text{R(3, k) <}\text{100k}{}^2\text{ln}\text{k}$. This follows from the discovery of a (polynomial) algorithm to find in any triangle-free graph on n vertices with average degree t an independent set of size at least $\text{n}\text{ln}\text{t}\text{100t}$. Here, their algorithm is modified to improve both bounds, replacing 100 by 2.4, and carefully working out the details of the proof.     

Codimension one spheres in Rn with double tangent balls

In contrast to the situation in $\text{R}$³, where a 2-sphere with double tangent balls at each point must be tamely embedded in $\text{R}$³, there exist wild (n?1)-spheres in $\text{R}$ⁿ for n>3 with this same geometric property. However, if the sphere Σ is tame moduio a subset X that lies in a polyhedron P that is tame in Σ, the dimension of P is less than n?2, n>4, and Σ has double tangent balls over X, then Σ must be tame in $\text{R}$ⁿ. Also if the tangent balls extend over P and are pairwise congruent, the dimensional restriction on P can be dropped. Examples are given to support the necessity of the hypotheses of the included theorems.     

Multiplicativity of lp norms for matrices. II

For 1 ? p ? ∞, let

$\text{|A|}{}_{\mathrm{p}}\text{=}\text{Σ}\text{i=1}\text{m}\text{Σ}\text{j=1}\text{n}\text{, |α}{}_{\mathrm{ij}}\text{|}{}^{\mathrm{p}}{}^{\mathrm{<mtext>1</mtext><mtext>p</mtext>}}$

, be the l_p norm of an m × n complex A = (α_ij) ?C_{m × n}. The main purpose of this paper is to find, for any p, q ? 1, the best (smallest) possible constants τ(m, k, n, p, q) and σ(m, k, n, p, q) for which inequalities of the form

$\text{|AB|}{}_{\mathrm{p}}\text{? τ(m, k, n, p, q) |A|}{}_{\mathrm{p}}\text{|B|}{}_{\mathrm{q}}\text{, |AB|}{}_{\mathrm{p}}\text{? σ (m, k, n, p, q)|A|}{}_{\mathrm{q}}\text{|B|}{}_{\mathrm{p}}$

hold for all A?C_{m × k}, B?C_{k × n}. This leads to upper bounds for inner products on C^k and for ordinary l_p operator norms on C_{m × n}.     

Minimally k-connected graphs of low order and maximal size

Let G be a minimally k-connected graph of order n and size e(G).Mader [4] proved that (i) $\text{e(G)?kn?(}\text{k+1}\text{2}\text{)}$; (ii) e(G)?k(n?k) if n?3k?2, and the complete bipartite graph K_k,n?k is the only minimally k-connected graph of order; n and size k(n?k) when k?2 and n?3k?1.The purpose of the present paper is to determine all minimally k-connected graphs of low order and maximal size. For each n such that k+1?n?3k?2 we prove $\text{e(G)??}\text{(n+k)}{}^2\text{8}\text{?}$ and characterize all minimally k-connected graphs of order n and size $\text{?(}\text{(n+k)}{}^2\text{8}\text{?}$.     

On Sperner families in which no K sets have an empty intersection

Let n(r, k) denote the maximal cardinality of Sperner families on a r-element set in which no k ? 3 sets have an empty intersection. Frankl determined n(r, 3) for r sufficiently large. In this paper we prove

$\text{n(r,k)=}\text{r ? 1}\text{[}\text{r ? 1}\text{2}\text{]}$

for k ? 4 and r arbitrary and for k = 3 when r is odd except for 12 values of r. For k = 3 when r? {4, 6, 7} or sufficiently large (e.g. r ? 400)

$\text{n(r,k)=}\text{r ? 1}\text{[}\text{r ? 1}\text{2}\text{]}\text{+ 1}$

is proven. The extremal families are determined also.     

Extremal uncrowded hypergraphs

Let G be a (k + 1)-graph (a hypergraph with each hyperedge of size k + 1) with n vertices and average degreee t. Assume k ? t ? n. If G is uncrowded (contains no cycle of size 2, 3, or 4) then there exists and independent set of size $\text{c}{}_{\mathrm{k}}\text{(}\text{n}\text{t}\text{)(}\text{ln}\text{t)}{}^{\mathrm{<mtext>1</mtext><mtext>k</mtext>}}$.     

A lower bound for v in a t − (v,k, λ) design

In this paper it is shown that if v ? k + 1 then $\text{v ? t ? 1 + (k ? t + 1)(k ? t + 2)}\text{λ}$, where v, k, λ and t are the characteristic parameters of a t ? (v, k, λ) design. We compare this bound with the known lower bounds on v.     

A homological approach to representations of algebras I: The wild case

We prove that the pure global dimension of a polynomial ring over an integral domain k in a finite or countable number n?2 of commuting (non-commuting, resp.) variables is t + 1, provided $\text{|k| = ?}{}_{\mathrm{t}}$. As an application, we determine the pure global dimension of wild algebras of quiver type, also (in case k is an algebraically closed field) of the wild local and wild commutative algebras of finite k-dimension.     

An intersection problem whose extremum is the finite projective space

Suppose that $\text{A}$ is a finite set-system of N elements with the property |A ∩ A′| = 0, 1 or k for any two different A, A′ ?A. We show that for N > k¹⁴

$\text{|a|=?}\text{N(N?1)(N?k)}\text{(k}{}^2\text{?k+1)(k}{}^2\text{?2k+1)}\text{+}\text{N(N?1)}\text{k(k?1)}\text{+N+1}$

where equality holds if and only if k = q + 1 (q is a prime power) $\text{N =}\text{(q}{}^{\mathrm{t+1}}\text{? 1)}\text{(q ? 1)}$ and $\text{A}$ is the set of subspaces of dimension at most two of the t-dimensional finite projective space of order q.     

Lp estimates for the wave equation

Let u(x, t) be the solution of u_tt ? Δ_xu = 0 with initial conditions $\text{u(x, 0) = g(x)}\text{and}\text{u}{}_{\mathrm{t}}\text{(x, 0) = ?;(x)}$. Consider the linear operator $\text{T: ?; → u(x, t)}$. (Here g = 0.) We prove for t fixed the following result. Theorem 1: T is bounded in L^p if and only if . Theorem 2: If the coefficients are variables in C and constant outside of some compact set we get: (a) If n = 2k the result holds for $\text{¦ p}{}^{\mathrm{?1}}\text{? 2}{}^{\mathrm{?1}}\text{¦ < (n ? 1)}{}^{\mathrm{?1}}$. (b) If n = 2k ? 1, the result is valid for $\text{¦ p}{}^{\mathrm{?1}}\text{? 2}{}^{\mathrm{?1}}\text{¦ ? (n ? 1)}$. This result are sharp in the sense that for p such that $\text{¦ p}{}^{\mathrm{?1}}\text{? 2}{}^{\mathrm{?1}}\text{¦ > (n ? 1)}{}^{\mathrm{?1}}$ we prove the existence of $\text{?; ? L}{}^{\mathrm{P}}$ in such a way that $\text{T?; ? L}{}^{\mathrm{P}}$. Several applications are given, one of them is to the study of the Klein-Gordon equation, the other to the completion of the study of the family of multipliers $\text{m(ξ) = ψ(ξ) e}{}^{\mathrm{i¦\xi ¦}}\text{¦ ξ ¦}{}^{\mathrm{?b}}$ and finally we get that the convolution against the kernel $\text{K(x) = ?(x)(1 ? ¦ x ¦)}{}^{\mathrm{?1}}$ is bounded in H¹.