On extremal problems of graphs and generalized graphs

Anr-graph is a graph whose basic elements are its vertices and r-tuples. It is proved that to everyl andr there is anε(l, r) so that forn>n ₀ everyr-graph ofn vertices andn ^{r−ε(l, r)} r-tuples containsr. l verticesx ^(j), 1≦j≦r, 1≦i≦l, so that all ther-tuples occur in ther-graph.     

Graphs whose every transitive orientation contains almost every relation

Given a graphG onn vertices and a total ordering ≺ ofV(G), the transitive orientation ofG associated with ≺, denotedP(G; ≺), is the partial order onV(G) defined by settingx<y inP(G; ≺) if there is a pathx=x ₁ x ₂…x _r=y inG such thatx ₁ ≺x _j for 1≦i<j≦r. We investigate graphsG such that every transitive orientation ofG contains ₂ ⁿ −o(n ²) relations. We prove that almost everyG _n,p satisfies this requirement if , but almost noG _n,p satisfies the condition if (pn log log logn)/(logn log logn) is bounded. We also show that every graphG withn vertices and at mostcn logn edges has some transitive orientation with fewer than ₂ ⁿ −δ(c)n ² relations. Partially supported by MCS Grant 8104854.     

The range of a projection of small norm inl 1 n

It is proved that there exists a positive function Φ(∈) defined for sufficiently small ∈ 〉 0 and satisfying lim_t→0 Φ(∈) =0 such that for any integersn 〉>0, ifQ is a projection ofl ₁ ⁿ onto ak-dimensional subspaceE with ‖|Q‖|≦1+∈ then there is an integerh〉=k(1−Φ(∈)) and anh-dimensional subspaceF ofE withd(F,l ₁ ^h ) 〈= 1+Φ (∈) whered(X, Y) denotes the Banach-Mazur distance between the Banach spacesX andY. Moreover, there is a projectionP ofl ₁ ⁿ ontoF with ‖|P‖| ≦1+Φ(∈). Author was partially supported by the N.S.F. Grant MCS 79-03042.     

On Lp-convergence of Grunwald interpolation

In this paper, the L_p-convergence of Grünwald interpolation G_n(f,x) based on the zeros of Jacobi polynomials J _n ^(α,β) (x)(−1<α,β<1) is considered. L_p-convergence (0<p<2) of Grünwald interpolation G_n(f,x) is proved for p·Max(α,β)<1. Moreover, L_p-convergence (p>0) of G_n(f,x) is obtained for −1<α,β≤0. Therefore, the results of [1] and [3–5] are improved.     

Graphs whose critical groups have larger rank

The critical group C(G) of a graph G is a refinement of the number of spanning trees of the graph and is closely connected with the Laplacian matrix. Let r(G) be the minimum number of generators (i.e., the rank) of the group C(G) and β(G) be the number of independent cycles of G. In this paper, some forbidden induced subgraphs are given for r(G) = n − 3 and all graphs with r(G) = β(G) = n − 3 are characterized.     

Examples of amalgamated products

The rank of a groupG is the minimal number of elements that generateG. For any natural numbern we construct two groups,G ₁ of rankr(G ₁)=n andG ₂ of rankr(G ₂)=2n such that their amalgamated product over an infinite cyclic subgroup, malnormal in both factors, is generated by 2n=r(G ₁)+r(G ₂)−n elements. We also consider an example of an amalgamated product ofn factors: such thatr(G)=n +1, andr(A)≥1. This example realizes the lower bound given by Weidmann [W1] (see Theorem 2 in the present paper).     

Two point problems and analyticity of solutions of abstract parabolic equations

Fort ∈ [a, b], letA(t) be the unbounded operator inH ^0,p (G) associated with an elliptic-boundary value problem that satisfies Agmon’s conditions on the rays λ=±iτ, τ ≥0. Existence and uniqueness results are obtained for weak and strict solutions of two-point problems of the type (du/dt)−A(t) u(t) =f(t),E ₁(α)u (α)=u _α,E ₂ (β)u (β)=u _β. Here [α, β) χ- [a, b],E ₁ (α) andE ₂ (β) are spectral projections associated withA(α) andA(β) respectively, andA(α)E ₁ (α) and =A (β)E ₂ (β) are infinitesimal generators of analytic semigroups. WhenA(t) andf(t) are analytic in a convex, complex neighborhoodO of [a, b] we show that for someθ _i ,i=1,2, any solution ofdu/dt =A(t)u (t)=f(t) in [a, b] is analytic and satisfies the above equation in the setO∩{t; t ≠ a, t ≠ b, | arg (t −a) | <θ ₁, | arg (b −t) |θ ₂}. Research partially supported by N. N. F. grant at Brandeis University.     

l p n Superspaces of spans of independent random variables

We show that for 1 ≦p < ∞,p ≠ 2, ifɛ > 0 is small enough andX ≦L _p is the span ofn independent Rademacher functions orn independent Gaussian random variables, then any superspaceY ofX satisfyingd(Y,L _p ^m ) ≦ 1 +ɛ has dimension larger thanr ⁿ, wherer =r(ɛ, p) > 1. This forms part of the author’s doctoral dissertation prepared at Texas A&M University under the direction of Professor W. B. Johnson. Supported in part by NSF DMS-85 00764.     

Large holes in sparse random graphs

We show that there is a function α(r) such that for each constantr≧3, almost everyr-regular graph onn vertices has a hole (vertex induced cycle) of size at least α(r)n asn→∞. We also show that there is a function β(c) such that forc>0 large enough,G _{n, p} ,p=c/n almost surely has a hole of size at least β(c)n asn→∞.     

On a problem of spencer

LetX ₁, ...,X _n be events in a probability space. Let ϱ_i be the probabilityX _i occurs. Let ϱ be the probability that none of theX _i occur. LetG be a graph on [n] so that for 1 ≦i≦n X _i is independent of ≈X _j ‖(i, j)∉G≈. Letf(d) be the sup of thosex such that if ϱ₁, ..., ϱ _n ≦x andG has maximum degree ≦d then ϱ>0. We showf(1)=1/2,f(d)=(d−1) ^d−1 d ^−d ford≧2. Hence df(d)=1/e. This answers a question posed by Spencer in [2]. We also find a sharp bound for ϱ in terms of the ϱ _i andG.     

Highest weight representations of a Lie algebra of Block type

For a field F of characteristic zero and an additive subgroup G of F, a Lie algebra B(G) of the Block type is defined with the basis {Lα,i, c|α∈G, -1≤i∈Z} and the relations [Lα,i,Lβ,j] = ((i 1)β- (j 1)α)Lα β,i j αδα,-βδi j,-2c,[c, Lα,i] = 0. Given a total order (?) on G compatible with its group structure, and anyα∈B(G)0*, a Verma B(G)-module M(A, (?)) is defined, and the irreducibility of M(A,(?)) is completely determined. Furthermore, it is proved that an irreducible highest weight B(Z )-module is quasifinite if and only if it is a proper quotient of a Verma module.     

Large Monotone Paths in Graphs with Bounded Degree

 We prove that for every ε>0 and positive integer r, there exists Δ₀=Δ₀(ε) such that if Δ>Δ₀ and n>n(Δ,ε,r) then there exists a packing of K _n with ⌊(n−1)/Δ⌋ graphs, each having maximum degree at most Δ and girth at least r, where at most εn ² edges are unpacked. This result is used to prove the following: Let f be an assignment of real numbers to the edges of a graph G. Let α(G,f) denote the maximum length of a monotone simple path of G with respect to f. Let α(G) be the minimum of α(G,f), ranging over all possible assignments. Now let α_Δ be the maximum of α(G) ranging over all graphs with maximum degree at most Δ. We prove that Δ+1≥α_Δ≥Δ(1−o(1)). This extends some results of Graham and Kleitman [6] and of Calderbank et al. [4] who considered α(K _n ). Received: March 15, 1999?Final version received: October 22, 1999     

Root differences for A n

Suppose W is a Weyl group with Φ = Φ(W) a root system of W. The set D of root differences is given by D = {α − β : α, β, ∈ Φ}. We define t(Φ) to be the maximum exponent of the torsion subgroup of for any In this article we show that if W is of type A_n, then t(Φ) = 2ⁿ. Received: 25 November 2004     

Augmented group systems and shifts of finite type

Let (G, χ, x) be a triple consisting of a finitely presented groupG, epimorphism χ:G →Z, and distinguished elementx ∈G such that χ(x)=1. Given a finite symmetric groupS _r, we construct a finite directed graph Γ that describes the set Φ _r of representations π: Ker χ →S _r as well as the mapping σ _x :Φ _r →Φ _r defined by (σ _x ϱ)(a) = ϱ(x ⁻¹ ax) for alla ∈ Ker χ. The pair (Φ _r ,σ _x has the structure of a shift of finite type, a well-known type of compact 0-dimensional dynamical system. We discuss basic properties and applications of therepresentation shift (Φ _r ,σ _x ), including applications to knot theory.     

Highest weight representations of a family of Lie algebras of Block type

For an additive subgroup G of a field F of characteristic zero, a Lie algebra B（G） of Block type is defined with basis {Lα,i｜ α∈G, i∈Z＋} and relations [Lα,i, Lβ,j] = （β-α）Lα＋β,i＋j＋（αj-βi）Lα＋β,Lα＋β,i＋j-1.It is proved that an irreducible highest weight B（Z）-module is quasifinite if and only if it is a proper quotient of a Verma module. Furthermore, for a total order λ on G and any ∧∈B（G）0^＊（the dual space of B（G）0 = span{L0,i｜i∈Z＋}）, a Verma B（G）-module M（∧,λ） is defined, and the irreducibility of M（A,λ） is completely determined.     

On Some Three-Color Ramsey Numbers

 In this paper we study three-color Ramsey numbers. Let K _i,j denote a complete i by j bipartite graph. We shall show that (i) for any connected graphs G ₁, G ₂ and G ₃, if r(G ₁, G ₂)≥s(G ₃), then r(G ₁, G ₂, G ₃)≥(r(G ₁, G ₂)−1)(χ(G ₃)−1)+s(G ₃), where s(G ₃) is the chromatic surplus of G ₃; (ii) (k+m−2)(n−1)+1≤r(K _1,k , K _1,m , K _n )≤ (k+m−1)(n−1)+1, and if k or m is odd, the second inequality becomes an equality; (iii) for any fixed m≥k≥2, there is a constant c such that r(K _k,m , K _k,m , K _n )≤c(n/logn), and r(C _2m , C _2m , K _n )≤c(n/logn) ^m/(m−1) for sufficiently large n. Received: July 25, 2000 Final version received: July 30, 2002 RID="*" ID="*" Partially supported by RGC, Hong Kong; FRG, Hong Kong Baptist University; and by NSFC, the scientific foundations of education ministry of China, and the foundations of Jiangsu Province Acknowledgments. The authors are grateful to the referee for his valuable comments. AMS 2000 MSC: 05C55     

A theorem on level lines of continuous functions

A property of a continuous functionf(x), x ∈ E ₂, similar to the classical intermediate value property is established. Namely, let a Jordan compactJ ⊂ E ₂ be the domain of definition off. Then, for each parametrizationx(t), 0≦t≦T,x(0)=x(T), of the boundary Fr(J) ofJ there exists a unique real λ and a unique connected component Φ of the level set {x ∈ J: f(x)=λ} with the following property: any connected subset Ω ofJ containing “opposite” points of Fr(J) (i.e. pointsx(t′) andx(t″) such thatt″−t′=T/2) has a common element with Φ.     

Universal PI-algebras and algebras of generic matrices

Let Ω[ξ] denote the polynomial algebra (with 1) in commutative indeterminates {ie65-1}, 1 ≦i, j ≦n, 1 ≦k < ∞, over a commutative ring Ω. Thealgebra of generic matrices Ω [Y] is defined to be the Ω-subalgebra ofM _n (Ω[ξ]) generated by the matricesY _k=({ie65-2}), 1 ≦i, j ≦n, 1 ≦k < ∞. This algebra has been studied extensively by Amitsur and by Procesi in particular Amitsur has used it to construct a finite dimensional, central division algebra Ω (Y) which is not a crossed product. In this paper we shall prove, for Ω a domain, that Ω(Y) has exponentn in the Brauer group (Amitsur may already know this fact); consequently, for Ω an infinite field andn a multiple of 4, iff(X ₁, …,X _m) is a polynomial linear in all theX _i but one (similar to Formanek’s central polynomials for matrix rings) andf ² is central forM _n (Ω), thenf is central forM _n (Ω). (The existence of a polynomial not central forM _n (Ω), but whose square is central forM _n(Ω) is equivalent to every central division algebra of degreen containing a quadratic extension of its center; well-known theory immediately shows this is the case of 4‖n and 8χn.) Also, information is obtained about Ω(Y) for arbitary Ω, most notably that the Jacobson radical is the set of nilpotent elements. Partial support for this work was provided by National Science Foundation grant NSF-GP 33591.     

A remark on presentations of certain Chevalley groups

Let Φ be a root system of typeA _ℓ, ℓ ≧ 2,D _ℓ, ℓ ≧ 4 orE _ℓ, 6 ≧ ℓ ≧ 8 andG a group generated by nonidentity abelian subgroupsA _r,r∈Φ, satisfying: