On the number of certain subgraphs contained in graphs with a given number of edges

All graphs considered are finite, undirected, with no loops, no multiple edges and no isolated vertices. For two graphsG, H, letN(G, H) denote the number of subgraphs ofG isomorphic toH. Define also, forl≧0,N(l, H)=maxN(G, H), where the maximum is taken over all graphsG withl edges. We determineN(l, H) precisely for alll≧0 whenH is a disjoint union of two stars, and also whenH is a disjoint union ofr≧3 stars, each of sizes ors+1, wheres≧r. We also determineN(l, H) for sufficiently largel whenH is a disjoint union ofr stars, of sizess ₁≧s ₂≧…≧s _r>r, provided (s ₁−s _r)²<s ₁+s _r−2r. We further show that ifH is a graph withk edges, then the ratioN(l, H)/l ^k tends to a finite limit asl→∞. This limit is non-zero iffH is a disjoint union of stars.     

On maximal (k,t)-sets

Summary This investigation was originally motivated by the problem of determining the maximum number of points in finiten-dimensional projective spacePG(n, s) based on the Galois fieldGF(s) of orders=p ^h (wherep andh are positive integers andp is the prime characteristic of the field), such that not of these chosen points are linearly dependent. A set ofk distinct points inPG(n, s), not linearly dependent, is called a (k, t)-set fork ₁ >k. The maximum value ofk is denoted bym _t (n+1, s). The purpose of this paper is to find new upper bounds for some values ofn, s andt. These bounds are of importance in the experimental design and information theory problems.     

Far field velocity potential induced by a rapidly decaying vorticity distribution

We study the velocity field induced by a vorticity distribution decaying rapidly in the distancer from the origin. In the far field, the vector potential for the velocity field can be represented by a series A ⁽ⁿ⁾, withA ⁽ⁿ⁾ proportional tor ^–n–1, forn=1, 2, .... We show thatA ⁽ⁿ⁾ can be expressed as a linear combination ofM _n linearly independent vector functions. The numberM _n is equal to 3 forn=1 and 4n forn2 and the coefficient of a vector function is defined by a linear combination of nth moments of vorticity. We then show that only 2n+1 linear combinations of thoseM _n vector functions contribute to the far field velocity which is irrotational. The corresponding scalar potential ⁽ⁿ⁾ is then represented by a linear combination of 2n+1 spherical harmonics ofnth order whose coefficients are again linear combinations ofnth moments of vorticity.

---

Zusammenfassung Die vorliegende Arbeit beschreibt das Geschwindigkeitsfeld fernab einer Wirbelverteilung, welche mit dem Abstandr vom Ursprung eines geeigneten Bezugssystems hinreichend schnell abklingt. Die Geschwindigkeit besitzt ein Vektorpotential, dessen Fernfeldverhalten einer Reihenentwicklung A ⁽ⁿ⁾, genügt. Dabei istA ⁽ⁿ⁾ proportional zur ^–n–1 fürn=1, 2, .... Wir entwickeln eine explizite Darstellung vonA ⁽ⁿ⁾ als Linearkombination vonM _n linear unabhängigen Vektorfunktionen. Die auftretenden Koeffizienten sind ihrerseits Kombinationenn-ter Momente der Wirbelverteilung. Die ZahlM ₁ ist gleich 3 und es istM _n=4n fürn2, während die Gesamtzahl dernten Momente beträgt. Weiterhin zeigen wir, da\ nur 2n+1 dieser Vektorfunktionen auch zum drehungsfreien Fernfeld der Geschwindigkeitn-ter Ordnung beitragen können und identifizieren die zugehörigen Kombinationen von Wirbelmomenten. Dieselben Kombinationen liefern dann auch die Koeffizienten in einer Entwicklung desskalaren Fernfeldpotentials nach Kugelfunktionen.

     

Integral Schur algebras forGL 2

The structure of Schur algebrasS(2,r) over the integral domainZ is intensively studied from the quasi-hereditary algebra point of view. We introduce certain new bases forS(2,r) and show that the Schur algebraS(2,r) modulo any ideal in the defining sequence is still such a Schur algebra of lower degree inr. A Wedderburn-Artin decomposition ofS _K (2,r) over a fieldK of characteristic 0 is described. Finally, we investigate the extension groups between two Weyl modules and classify the indecomposable Weyl-filtered modules for the Schur algebrasS _Zp(2,r) withr<p ² . Research supported by ARC Large Grant L20.24210     

Characterizations of the Poisson process as a renewal process via two conditional moments

Given two independent positive random variables, under some minor conditions, it is known that fromE(X^rX+Y)=a(X+Y)^r andE(X^sX+Y)=b(X+Y)^s, for certain pairs ofr ands, wherea andb are two constants, we can characterizeX andY to have gamma distributions. Inspired by this, in this article we will characterize the Poisson process among the class of renewal processes via two conditional moments. More precisely, let {A(t), t0} be a renewal process, with {S _k, k1} the sequence of arrival times, andF the common distribution function of the inter-arrival times. We prove that for some fixedn andk, kn, ifE(S _k ^r A(t)=n)=at^r andE(S _k ^s A(t)=n)=bt^s, for certain pairs ofr ands, wherea andb are independent oft, then {A(t), t0} has to be a Poisson process. We also give some corresponding results about characterizingFto be geometric whenF is discrete.Support for this research was provided in part by the National Science Council of the Republic of China, Grant No. NSC 81-0208-M110-06.     

A splitting theorem for connected moravaK-theories

LetX be a connected, locally finite spectrum and letk(n) (n>-1) denote the (−1)-connected cover of then-th MoravaK-Theory associated to the primep.k(n) is aBP-module spectrum with π_*(k(n)) ≅ ℤ _p [υ _n ] where |v _n | = 2(p ⁿ -1). We prove the following splitting theorem: Thek(n) ^*-torsion ofk(n) ^* (X) is already annihilated byv _n ^e (e≥1) if and only ifk(n)ΛX is homotopy equivalent to a wedge of spectrak(n) and ^r k(n) (0≤r≤e-1) where ^r k(n) denotes ther-th Postnikov factor ofk(n). Moreover we investigate splitting conditions for ^r k(n)ΛX.     

A result on the composition of distributions

LetF be a distribution and letf be a locally summable function. The distributionF(f) is defined as the neutrix limit of the sequenceF _n (f), whereF _n (x) = F(x) * δ _n (x) andδ _n (x) is a certain sequence of infinitely differentiable functions converging to the Dirac delta-functionδ(x). The distribution (x^r)^−s is valuated forr, s = 1,2, ….     

Equally-weighted formulas for numerical differentiation

Equally-weighted formulas for numerical differentiation at a fixed pointx=a, which may be chosen to be 0 without loss in generality, are derived for (1) whereR _2n =0 whenf(x) is any (2n)^th degree polynomial. Equation (1) is equivalent to (2) ,r=1,2,..., 2n. By choosingf(x)=1/(z–x),x _i fori=1,..., n andx _i fori=n+1,..., 2n are shown to be roots ofg _n (z) andh _n (z) respectively, satisfying (3) . It is convenient to normalize withk=(m–1)!. LetP _s (z) denotez ^s · numerator of the (s+1)^th diagonal member of the Padé table fore ^x , frx=1/z, that numerator being a constant factor times the general Laguerre polynomialL _s ^–2s–1 (x), and letP _s (X _i )=0, i=1, ...,s. Then for anym, solutions to (1) are had, for2n=2ms, forx _i , i=1, ...,ms, andx _i , i=ms+1,..., 2ms, equal to all them ^th rootsX _i ^1/m and (–X _i )^1/m respectively, and they give {(2s+1)m–1}^th degree accuracy. For2sm2n(2s+1)m–1, these (2sm)-point solutions are proven to be the only ones giving (2n)^th degree accuracy. Thex _i 's in (1) always include complex values, except whenm=1, 2n=2. For2sm<2n(2s+1)m–1,g _n (z) andh _n (z) are (n–sm)-parameter families of polynomials whose roots include those ofg _ms (z) andh _ms (z) respectively, and whose remainingn–ms roots are the same forg _n (z) andh _n (z). Form>1, and either 2n<2m or(2s+1)m–1<2n<(2s+2)m, it is proven that there are no non-trivial solutions to (1), real or complex. Form=1(1)6, tables ofx _i are given to 15D, fori=1(1)2n, where 2n=2ms ands=1(1) [12/m], so that they are sufficient for attaining at least 24^th degree accuracy in (1).Presented at the Twelfth International Congress of Mathematicians, Stockholm, Sweden, August 15–22, 1962.General Dynamics/Astronautics. A Division of General Dynamics Corporation.     

The structure of the set of satisfying assignments for a random <Emphasis Type="Italic">k</Emphasis>-CNF

Let F _k (n, m) be a random k-CNF obtained by a random, equiprobable, and independent choice of m brackets from among all k-literal brackets on n variables. We investigate the structure of the set of satisfying assignments of F _k (n, m). A method is proposed for finding r(k, s)such that the probability of presence of ns-dimensional faces (0 < s < 1) in the set of satisfying assignments of the formula F _k s(n, r(k, s)n) goes to 1 as n goes to infinity. We prove the existence of a sequential threshold for the property of having ns-dimensional faces (0 < s < 1). In other words, there exists a sequence r _n (k, s) such that the probability of having an ns-dimensional face in the set of satisfying assignments of the formula F _k (n, r _n (k, s)(1 + d)n) goes to 0 for all d > 0 and to 1 for all d < 0. __________ Translated from Prikladnaya Matematika i Informatika, No. 26, pp. 61–95, 2007.     

Stability for large forbidden subgraphs

In this note we strengthen the stability theorem of Erd?s and Simonovits. Write K_r(s₁, …, s_r) for the complete r‐partite graph with classes of sizes s₁, …, s_r and T_r(n) for the r‐partite Turán graph of order n. Our main result is: For all r≥2 and all sufficiently small c>0, ε>0, every graph G of sufficiently large order n with e(G)>(1?1/r?ε)n²/2 satisfies one of the conditions:

• (a) G contains a $K_{r+1} (\lfloor c\,\mbox{ln}\,n \rfloor,\ldots,\lfloor c\,\mbox{ln}\,n \rfloor,\lceil n^{{1}-\sqrt{c}}\rceil)In this note we strengthen the stability theorem of Erd?s and Simonovits. Write K_r(s₁, …, s_r) for the complete r‐partite graph with classes of sizes s₁, …, s_r and T_r(n) for the r‐partite Turán graph of order n. Our main result is: For all r≥2 and all sufficiently small c>0, ε>0, every graph G of sufficiently large order n with e(G)>(1?1/r?ε)n²/2 satisfies one of the conditions:
  • (a) G contains a $K_{r+1} (\lfloor c\,\mbox{ln}\,n \rfloor,\ldots,\lfloor c\,\mbox{ln}\,n \rfloor,\lceil n^{{1}-\sqrt{c}}\rceil)$;
  • (b) G differs from T_r(n) in fewer than (ε^1/3+c^1/(3r+3))n² edges.
  Letting µ(G) be the spectral radius of G, we prove also a spectral stability theorem: For all r≥2 and all sufficiently small c>0, ε>0, every graph G of sufficiently large order n with µ(G)>(1?1/r?ε)n satisfies one of the conditions:
  • (a) G contains a $K_{r+1}(\lfloor c\,\mbox{ln}\,n\rfloor,\ldots,\lfloor c\,\mbox{ln}\,n\rfloor,\lceil n^{1-\sqrt{c}}\rceil)$;
  • (b) G differs from T_r(n) in fewer than (ε^1/4+c^1/(8r+8))n² edges.
  © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 362–368, 2009     

Primarite DeL p(L r), 1<p,r<∞

In this article we show thatL ^p(L ^r) is primary forp andr in ]1,+∞[. If (h _k) _k≧1 denote the Haar basis, we begin with a study of the sequence (h _k ⊗h _i) and, in particular, the space generated by a subsequence of this sequence. In the first part we study the base ofL ^p(L ^r) and in the second part we show that this space is primary.     

On the peripheral spectrum of positive operators

We prove that ifE is a Banach lattice andS, T ∈ ℒ (E) are such that 0≦s≦T,r(s)=r(T) andr(T) is a Riesz point ofσ(T) thenr(S) is a Riesz point ofσ(S). We prove also some results on compact positive perturbations of positive irreducible operators and lattice homomorphisms.     

Kernel-type density and failure rate estimation for associated sequences

Let {X _n ,n1} be a strictly stationary sequence of associated random variables defined on a probability space (,B, P) with probability density functionf(x) and failure rate functionr(x) forX ₁. Letf _n (x) be a kerneltype estimator off(x) based onX ₁,...,X _n . Properties off _n (x) are studied. Pointwise strong consistency and strong uniform consistency are established under a certain set of conditions. An estimatorr _n (x) ofr(x) based onf _n (x) andF _n (x), the empirical survival function, is proposed. The estimatorr _n (x) is shown to be pointwise strongly consistent as well as uniformly strongly consistent over some sets.     

On 3-pushdown graphs with large separators

For an integers letl ^s (n), thes-iterated logarithm function, be defined inductively:l ⁰ (n)=n,l ^s+1 (n)=log₂ (l ² (n)) fors0. We show that for every fixeds and alln large enough, there is ann-vertex 3-pushdown graph whose smallest separator contains at least(n/l ^s (n)) vertices.The work of the first author was supported in part by NSF Grants MCS-83-03139, DCR-85-11713 and CCR-86-05353.The work of the second author was supported in part by NSF Grants MCS-84-16190.     

Hamilton decompositions of cartesian products of multicycles

We define the multicycle C^(r)_m as a cycle on m vertices where each edge has multiplicity r. So C^(r)_m can be decomposed into r Hamilton cycles. We provide a complete answer to the following question: for which positive integers m, n, r, s with m, n ≥ 3 can the Cartesian product of two multicycles C^(r)_m x C^(s)_n be decomposed into r + s Hamilton cycles? We find some interesting characterizations of Hamilton cycles of C_m x C_n while answering the above question. © 1997 John Wiley & Sons, Inc.     

The minimal number of circuits in a finite set inR 2k−1

The minimal number of circuits (i.e., minimal affinely dependent subsets) in a set ofs points inR ^2k−1 isr( ₃ ⁴ )+(k−r)( ₃ ^4⋅1 ) as conjectured by J.-P. Doignon, wheres=qk+r, 0≦r<q.     

Off‐diagonal and asymptotic results on the Ramsey number r(K2,m,K2,n)

An upper bound on the Ramsey number r(K_2,n‐s,K_2,n) where s ≥ 2 is presented. Considering certain r(K_2,n‐s,K_2,n)‐colorings obtained from strongly regular graphs, we additionally prove that this bound matches the exact value of r(K_2,n‐s,K_2,n) in infinitely many cases if holds. Moreover, the asymptotic behavior of r(K_2,m,K_2,n) is studied for n being sufficiently large depending on m. We conclude with a table of all known Ramsey numbers r(K_2,m,K_2,n) where m,n ≤ 10. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 252–268, 2003     

Cyclic homology and the Macdonald conjectures

Summary LetA+(k) denote the ring [t]/t ^k+1 and letG be a reductive complex Lie algebra with exponentsm ₁, ...,m n. This paper concerns the Lie algebra cohomology ofGA ₊(k) considered as a bigraded algebra (here one of the gradings is homological degree and the other, which we callweight, is inherited from the obvious grading ofGA ₊(k)). We conjecture that this Lie algebra cohomology is an exterior algebra withk+1 generators of homological degree 2m _s +1 fors=1,2, ...,n. Of thesek+1 generators of degree 2m _s +1, one has weight 0 and the others have weights (k+1)m _s +t fort=1,2, ...,k.It is shown that this conjecture about the Lie algebra cohomology of A ₊(k) implies the Macdonald root system conjectures. Next we consider the case thatG is a classical Lie algebra with root systemA _n ,B _n ,C _n , orD _n. It is shown that our conjecture holds in the limit onn asn approaches infinity which amounts to the computation of the cyclic and dihedral cohomologies ofA+(k). Lastly we discuss the relevance of this limiting case to the case of finiten in this situation.Partially supported by NSF grant number MCS-8401718 and a Bantrell Fellowship     

On the real roots of Euler polynomials

We show how are located the positive roots of the Euler polynomiale _n of degreen. We give an upper bound and a lower bound for the greatest root. This permits to determine an integerv _(n) such that the number of positive roots ofE _n is eitherv _(n) orv _(n) +2. We also study the behaviour of ther-th positive root ofE _n asn tends to infinity.     

Upper bounds for growth in the Ryll-Nardzewski function of anω-categorical,ω-stable theory

We establish a sharp upper bound for growth in the sequences _k (T):=the number ofk-types consistent withT, forT ω-categorical andω-stable. This paper forms part of the author’s doctoral dissertation written at the University of Maryland under the direction of David W. Kueker.