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>}}$.     

Derivations of Witt vectors with application to K2 of truncated polynomial rings and Laurent series

The absolute Kähler module $\text{Ω}{}_{\mathrm{w}}{}_{\mathrm{n}}{}^{\mathrm{(k)}}$ of the truncated generalized Witt vectors of a field k of positive characteristic is zero if and only if k is perfect. This recovers known information on $\text{K}{}_2\text{(}\text{k[t]}\text{(t}{}^{\mathrm{n}}\text{)}\text{)}$ with which the structure of K₂(k((t))) can be studied.     

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)}$

     

Bounds on path connectivity

The path-connectivity of a graph G is the maximal k for which between any k pairs of vertices there are k edge-disjoint paths (one between each pair). An upper bound for the path-connectivity of n^q(q<1) separable graphs [6] is shown to exist.If the edge-connectivity of a graph is K_E then between any two pairs of vertices and for every $\text{t?}\text{K}{}_{\mathrm{E}}$ there exists a t?t′?t+1 such that there are t′ paths between the first pair and $\text{K}{}_{\mathrm{E}}\text{?t′}$ between the second pair. All paths are edge-disjoint.     

Families of finite sets in which no set is covered by the union of two others

Let f^k(n) denote the maximum of k-subsets of an n-set satisfying the condition in the title. It is proven that f^{2t ? 1}(n) ? f^2t(n + 1) ? $\text{(}{}_{\mathrm{t}}{}^{\mathrm{n}}\text{)}\text{(}{}_{\mathrm{t}}{}^{\mathrm{2t?1}}\text{)}$ with equalities holding iff there exists a Steiner-system S(t, 2t ? 1, n). The bounds are approximately best possile for k ? 6 and of correct order of magnitude for k >/ 7, as well, even if the corresponding Steiner-systems do not exist.Exponential lower and upper bounds are obtained for the case if we do not put size restrictions on the members of the family (i.e., the nonuniform case).     

Some Ramsey numbers for directed graphs

Given k directed graphs G₁,…,G_k the Ramsey number R(G₁,…, G_k) is the smallest integer n such that for any partition (U₁,…,U_k) of the arcs of the complete symmetric directed graph K_n, there exists an integer i such that the partial graph generated by U₁ contains G₁ as a subgraph. In the article we give a necessary and sufficient condition for the existence of Ramsey numbers, and, when they exist an upper bound function. We also give exact values for some classes of graphs. Our main result is: $\text{R(}\text{P}{}_{\mathrm{n}}\text{,….}\text{P}{}_{\mathrm{nk-1}}\text{, G) = n}{}_1\text{…n}{}_{\mathrm{k-1}}\text{(p-1) + 1}$, where G is a hamltonian directed graph with p vertices and $\text{P}{}_{\mathrm{n}}{}_{\mathrm{i}}$ denotes the directed path of length n_t     

Binomial self-inverse sequences and tangent coefficients

This paper treats the class of sequences {a_n} that satisfy the recurrence relation

$\text{a}{}_{\mathrm{2n+1}}\text{=∑}{}_{\mathrm{<mtext>k=0</mtext>}}{}^{\mathrm{<mtext>n</mtext>}}\text{(?1)}{}^{\mathrm{<mtext>k</mtext>}}\text{(}\text{n}\text{k}\text{a}{}_{\mathrm{k}}\text{d}{}^{\mathrm{n?k}}$

between the odd and even terms of {a_n} that involves the coefficients of tan(t), namely

$\text{a}{}_{\mathrm{2n+1}}\text{=∑}{}_{\mathrm{<mtext>k=0</mtext>}}{}^{\mathrm{<mtext>n</mtext>}}\text{(?1)}{}^{\mathrm{<mtext>k</mtext>}}\text{(}\text{2}\text{n}\text{+1}\text{2}\text{k}\text{+1}\text{)}\text{T}{}_{\mathrm{k}}\text{(d/2)}{}^{\mathrm{2k+1}}\text{a}{}_{\mathrm{2n?2k}}$

A combinatorial setting is then provided to elucidate the appearance of the tangent coefficients in this equation.     

American Mathematical Society short course series: Fundamentals of applied combinatorics : August 12–13, 1977, University of Washington in Seattle,Seattle, Washington

A simple proof is given for the fact that the number of nonsingular similarity relations on {1, 2,… n}, for which the transitive closure of k blocks, equals $\text{(}{}^{\mathrm{2n?2k?1}}{}_{\mathrm{n?1}}\text{) ?(}{}^{\mathrm{2n?2k?1}}{}_{\mathrm{n}}\text{)}$1 ? k ? n > ?2. In particular, this implies a recent result of Shapiro about Catalan numbers and Fine's sequence.     

A note on Ramsey numbers

Upper bounds are found for the Ramsey function. We prove $\text{R(3, x) <}\text{cx}{}^2\text{ln}\text{x}$ and, for each k ? 3, $\text{R(k, x) <}\text{c}{}_{\mathrm{k}}\text{x}{}^{\mathrm{k\; ?\; 1}}\text{(}\text{ln}\text{x)}{}^{\mathrm{k\; ?\; 2}}$ asymptotically in x.     

Sublinear perturbations of the differential equation y(n) = 0 and of the analogous difference equation

According to a result of A. Ghizzetti, for any solution y(t) of the differential equation where $\text{y}{}^{\mathrm{(n)}}\text{(t)+}\text{∑}\text{i=0}\text{n?1}\text{g}{}_{\mathrm{i}}\text{(t) y}{}^{\mathrm{i}}\text{(t)=0}\text{(t ? 1)}$, $\text{∝}{}_1{}^{\mathrm{\infty }}\text{¦g}{}_{\mathrm{i}}\text{(x)¦x}{}^{\mathrm{n?I?1}}\text{dx < ∞}$ (0 ?i ? n ?1, either y(t) = 0 for t ? 1 or there is an integer r with 0 ? r ? n ? 1 such that $\text{lim}\text{t → ∞}\text{y(t)}\text{t}{}^{\mathrm{r}}$ exists and ≠0. Related results are obtained for difference and differential inequalities. A special case of the former has interesting applications in the study of orthogonal polynomials.     

Approximate solutions of functional differential equations

The author discusses the best approximate solution of the functional differential equation x′(t) = F(t, x(t), x(h(t))), 0 < t < l satisfying the initial condition x(0) = x₀, where x(t) is an n-dimensional real vector. He shows that, under certain conditions, the above initial value problem has a unique solution y(t) and a unique best approximate solution $\text{p}\text{?}{}_{\mathrm{k}}\text{(t)}$ of degree k (cf. [1]) for a given positive integer k. Furthermore, $\text{sup}{}_{\mathrm{0?t?l}}\text{¦}\text{p}\text{?}{}_{\mathrm{k}}\text{(t) ? y(t)¦ → 0}\text{as}\text{k → ∞}$, where ¦ · ¦ is any norm in Rⁿ.     

On a conjecture by D. Ž. D̄okovic

It is shown that if $\text{A?Ω}{}_{\mathrm{n}}\text{?{J}{}_{\mathrm{n}}\text{}}$ satisfies

$\text{nkσ}{}_{\mathrm{k}}\text{(A)?(n?k+1)}{}^2\text{σ}{}_{\mathrm{k?1}}\text{(A)}$

$\text{(k=1,2,…,n)}$

, where σ_k(A) denotes the sum of all kth order subpermanent of A, then Per[λJ_n+(1?λ)A] is strictly decreasing in the interval 0<λ<1.     

Factorization of fredholm operators on analytic functions

Let Ω be a simply connected domain in the complex plane, and $\text{A(Ω}{}^{\mathrm{n}}\text{)}$, the space of functions which are defined and analytic on $\text{Ω}{}^{\mathrm{n}}$, if K is the operator on elements $\text{u(t, a}{}_1\text{, …, a}{}_{\mathrm{n}}\text{)}\text{of}\text{A(Ω}{}^{\mathrm{n\; +\; 1}}\text{)}$ defined in terms of the kernels k_i(t, s, a₁, …, a_n) in $\text{A(Ω}{}^{\mathrm{n\; +\; 2}}\text{)}$ by is the identity operator on $\text{A(Ω}{}^{\mathrm{n\; +\; 1}}\text{)}$, then the operator I ? K may be factored in the form (I ? K)(M ? W) = (I ? ΠK)(M ? ΠW). Here, W is an operator on $\text{A(Ω}{}^{\mathrm{n\; +\; 1}}\text{)}$ defined in terms of a kernel w(t, s, a₁, …, a_n) in $\text{A(Ω}{}^{\mathrm{n\; +\; 2}}\text{)}$ by Wu = ∝_an^tw(t, s, a₁, …, a_n) u(s, a₁, …, a_n) ds. ΠW is the operator; ΠWu = ∝_{an ? 1}w(t, s, a₁, …, a_n) u(s, a₁, …, a_n) ds. ΠK is the operator; ΠKu = ∑_{i = 1}^{n ? 1} ∝_ai^tk_i(t, s, a₁, …, a_n) ds + ∝_{an ? 1}^tk_n(t, s, a₁, …, a_n) u(s, a₁, …, a_n) ds. The operator M is of the form m(t, a₁, …, a_n)I, where $\text{m ? A(Ω}{}^{\mathrm{n\; +\; 1}}\text{)}$ and maps elements of $\text{A(Ω}{}^{\mathrm{n\; +\; 1}}\text{)}$ into itself by multiplication. The function m is uniquely derived from K in the following manner. The operator K defines an operator $\text{K}{}^1$ on functions u in $\text{A(Ω}{}^{\mathrm{n\; +\; 2}}\text{)}$, by . A determinant $\text{δ(I ? K}{}^1\text{)}$ of the operator $\text{I ? K}{}^1$ is defined as an element $\text{m}{}^1\text{(t, a}{}_1\text{, …, a}{}_{\mathrm{n\; +\; 1}}\text{)}$ of $\text{A(Ω}{}^{\mathrm{n\; +\; 2}}\text{)}$. This is mapped into $\text{A(Ω}{}^{\mathrm{n\; +\; 1}}\text{)}$ by setting a_{n + 1} = t to give m(t, a₁, …, a_n). The operator I ? ΠK may be factored in similar fashion, giving rise to a chain factorization of I ? K. In some cases all the matrix kernels k_i defining K are separable in the sense that k_i(t, s, a₁, …, a_n) = P_i(t, a₁, …, a_n) Q_i(s, a₁, …, a_n), where P_i is a 1 × p_i matrix and Q_i is a p_i × 1 matrix, each with elements in $\text{A(Ω}{}_{\mathrm{n\; +\; 1}}\text{)}$, explicit formulas are given for the kernels of the factors W. The various results are stated in a form allowing immediate extension to the vector-matrix case.     

Deterministic version of Wigner's semicircle law for the distribution of matrix eigenvalues

It is proved that Wigner's semicircle law for the distribution of eigenvalues of random matrices, which is important in the statistical theory of energy levels of heavy nuclei, possesses the following completely deterministic version. Let A_n=(a_ij), 1?i, ?n, be the nth section of an infinite Hermitian matrix, {λ⁽ⁿ⁾}_1?k?n its eigenvalues, and {u_k⁽ⁿ⁾}_1?k?n the corresponding (orthonormalized column) eigenvectors. Let $\text{v}{}^1{}_{\mathrm{n}}\text{=(a}{}_{\mathrm{n1}}\text{,a}{}_{\mathrm{n2}}\text{,?,a}{}_{\mathrm{n,n?1}}\text{)}$, put

$\text{X}{}_{\mathrm{n}}\text{(t)=[n(n-1)]}{}^{\mathrm{<mtext>-1</mtext><mtext>2</mtext>}}\text{∑}\text{k=1}\text{[(n-1)t]}\text{|v}{}_{\mathrm{n}}{}^1\text{u}{}_{\mathrm{f}}{}^{\mathrm{(n-1)}}\text{|}{}^2\text{,}\text{0?t?1}$

(bookeeping function for the length of the projections of the new row v¹_n of A_n onto the eigenvectors of the preceding matrix A_n?1), and let finally

$\text{F}{}_{\mathrm{n}}\text{(x)=n}{}^{-1}\text{(}\text{number of}\text{λ}{}_{\mathrm{k}}{}^{\mathrm{(n)}}\text{?x}\text{n}\text{,1?k?n)}$

(empirical distribution function of the eigenvalues of $\text{A}{}_{\mathrm{n}}\text{n}$. Suppose (i) $\text{lim}{}_{\mathrm{n}}\text{a}{}_{\mathrm{nn}}\text{n}\text{=0}$, (ii) lim_nX_n(t)=Ct(0<C<∞,0?t?1). Then

$\text{F}{}_{\mathrm{n}}\text{?W(·,C)}\text{(n→∞)}$

,where W is absolutely continuous with (semicircle) density

$\text{w(x,C)=}\text{(2Cπ)}{}^{-1}\text{(4C-x}{}^2{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{for}\text{|x|?2}\text{C}\text{0}\text{for}\text{|x|?2}\text{C}$

     

On exponential bases for the Sobolev spaces over an interval

We suppose that K is a countable index set and that $\text{Λ = {λ}{}_{\mathrm{k}}\text{¦ k ? K}}$ is a sequence of distinct complex numbers such that forms a Riesz (strong) basis for L²[a, b], a < b. Let Σ = {σ₁, σ₂,…, σ_m} consist of m complex numbers not in Λ. Then, with p(λ) = Π_{k = 1}^m (λ ? σ_k), forms a Riesz (strong) bas Sobolev space H^m[a, b]. If we take σ₁, σ₂,…, σ_m to be complex numbers already in Λ, then, defining p(λ) as before, forms a Riesz (strong) basis for the space H^?m[a, b]. We also discuss the extension of these results to “generalized exponentials” tⁿe^λ_kt.     

On the probability that k positive integers are relatively prime II

Given a set S of positive integers let $\text{Z}{}_{\mathrm{k}}{}^{\mathrm{S}}\text{(t)}$ denote the number of k-tuples 〈m₁, …, m_k〉 for which $\text{m}{}_{\mathrm{i}}\text{∈ S ? [1, t]}$ and (m₁, …, m_k) = 1. Also let $\text{P}{}_{\mathrm{k}}{}^{\mathrm{S}}\text{(n)}$ denote the probability that k integers, chosen at random from $\text{S ? [1, n]}$, are relatively prime. It is shown that if P = {p₁, …, p_r} is a finite set of primes and S = {m : (m, p₁ … p_r) = 1}, then $\text{Z}{}_{\mathrm{k}}{}^{\mathrm{S}}\text{(t) = (td(S))}{}^{\mathrm{k}}\text{Π}{}_{\mathrm{\nu ?P}}\text{(1 ?}\text{1}\text{p}{}^{\mathrm{k}}\text{) + O(t}{}^{\mathrm{k?1}}\text{)}$ if k ≥ 3 and $\text{Z}{}_2{}^{\mathrm{S}}\text{(t) = (td(S))}{}^2\text{Π}{}_{\mathrm{p?P}}\text{(1 ?}\text{1}\text{p}{}^2\text{) + O(t}\text{log}\text{t)}$ where d(S) denotes the natural density of S. From this result it follows immediately that $\text{P}{}_{\mathrm{k}}{}^{\mathrm{S}}\text{(n) → Π}{}_{\mathrm{p?P}}\text{(1 ?}\text{1}\text{p}{}^{\mathrm{k}}\text{) = (ζ(k))}{}^{\mathrm{?1}}\text{Π}{}_{\mathrm{p\in P}}\text{(1 ?}\text{1}\text{p}{}^{\mathrm{k}}\text{)}{}^{\mathrm{?1}}$ as n → ∞. This result generalizes an earlier result of the author's where $\text{P = ?}$ and S is then the whole set of positive integers. It is also shown that if S = {p₁^x₁ … p_r^x_r : x_i = 0, 1, 2,…}, then $\text{P}{}_{\mathrm{k}}{}^{\mathrm{S}}\text{(n) → 0}$ as n → ∞.     

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.