On the h-triangles of sequentially (S r ) simplicial complexes via algebraic shifting

Recently, Haghighi, Terai, Yassemi, and Zaare-Nahandi introduced the notion of a sequentially (S _r ) simplicial complex. This notion gives a generalization of two properties for simplicial complexes: being sequentially Cohen–Macaulay and satisfying Serre’s condition (S _r ). Let Δ be a (d?1)-dimensional simplicial complex with Γ(Δ) as its algebraic shifting. Also let (h _i,j (Δ))_{0≤j≤i≤d} be the h-triangle of Δ and (h _i,j (Γ(Δ)))_{0≤j≤i≤d} be the h-triangle of Γ(Δ). In this paper, it is shown that for a Δ being sequentially (S _r ) and for every i and j with 0≤j≤i≤r?1, the equality h _i,j (Δ)=h _i,j (Γ(Δ)) holds true.     

Isomorphism of circulant graphs and digraphs

Let S? {1, …, n?1} satisfy ?S = S mod n. The circulant graph G(n, S) with vertex set {v₀, v₁,…, v_n?1} and edge set E satisfies v_iv_j?E if and only if j ? i ∈ S, where all arithmetic is done mod n. The circulant digraph G(n, S) is defined similarly without the restriction S = ? S. Ádám conjectured that $\text{G(n, S) ? G(n, S′)}$ if and only if S = uS′ for some unit u mod n. In this paper we prove the conjecture true if n = pq where p and q are distinct primes. We also show that it is not generally true when n = p², and determine exact conditions on S that it be true in this case. We then show as a simple consequence that the conjecture is false in most cases when n is divisible by p² where p is an odd prime, or n is divisible by 2⁴.     

Finite factorizable groups with solvable ℙ2-subnormal subgroups

A subgroup H of a finite group G is called ?²-subnormal whenever there exists a subgroup chain H = H ₀ ≤ H ₁ ≤ ... ≤ H _n = G such that |H _i+1: H _i | divides prime squares for all i. We study a finite group G = AB on assuming that A and B are solvable subgroups and the indices of subgroups in the chains joining A and B with the group divide prime squares. In particular, we prove that a group of this type is solvable without using the classification of finite simple groups.     

Asymptotic joint distribution of the largest roots of several multivariate F matrices I. Quasi-independent case

An asymptotic expansion of the joint distribution of k largest characteristic roots C_M⁽ⁱ⁾(S_iS₀^?1), i = 1,…, k, is given, where S'_is and S₀ are independent Wishart matrices with common covariance matrix Σ. The modified second-approximation procedure to the upper percentage points of the maximum of C_M⁽ⁱ⁾(S_iS₀^?1), i = 1,…, k, is also considered. The evaluation of the expansion is based on the idea for studentization due to Welch and James with the use of differential operators and of the perturbation procedure.     

Sur les arborescences dans un graphe oriente

The main result of this paper is the following theorem: Let G = (X,E) be a digraph without loops or multiple edges, |X| ?3, and h be an integer ?1, if G contains a spanning arborescence and if d⁺_G(x)+d^?_G(x)+d^?_G(y)+d^?_G(y)? 2|X |?2h?1 for all x, y?X, x ≠ y, non adjacent in G, then G contains a spanning arborescence with ?h terminal vertices. A strengthening of Gallai-Milgram's theorem is also proved.     

A law of the iterated logarithm for random walk in random scenery with deterministic normalizers

LetX, X _i ,i≥1, be a sequence of independent and identically distributed ? ^d -valued random vectors. LetS _o=0 and \(S_n = \sum\nolimits_{i = 1}^n {X_i } \) forn≤1. Furthermore letY, Y(α), α∈? ^d , be independent and identically distributed ?-valued random variables, which are independent of theX _i . Let \(Z_n = \sum\nolimits_{i = 0}^n {Y(S_i )} \) . We will call (Z _n ) arandom walk in random scenery. In this paper, we consider the law of the iterated logarithm for random walk in random scenery where deterministic normalizers are utilized. For example, we show that if (S _n ) is simple, symmetric random walk in the plane,E[Y]=0 andE[Y ²]=1, then $$\mathop {\overline {\lim } }\limits_{n \to \infty } \frac{{Z_n }}{{\sqrt {2n\log (n)\log (\log (n))} }} = \sqrt {\frac{2}{\pi }} a.s.$$      

Asymptotic behavior of number fields with prescribed ℓ-class numbers

Let K be a cyclic Galois extension of the rational numbers Q of degree ?, where ? is a prime number. Let h_? denote the order of the Sylow ?-subgroup of the ideal class group of K. If h_? = ?^s(s ≥ 0), it is known that the number of (finite) primes that ramify in K/Q is at most s + 1 (or s + 2 if K is real quadratic). This paper shows that “most” of these fields K with h_? = ?^s have exactly s + 1 ramified primes (or s + 2 ramified primes if K is real quadratic). Furthermore the Sylow ?-subgroup of the ideal class group is elementary abelian when h_? = ?^s and there are s + 1 ramified primes (or s + 2 ramified primes if K is real quadratic).     

Groups with a positive law on commutators

Let p be a prime number and let G be a finitely generated group that is residually a finite p-group. We prove that if G satisfies a positive law on all elements of the form [a,b][c,d]ⁱ, a,b,c,d∈G and i?0, then the entire derived subgroup G^′ satisfies a positive law. In fact, G^′ is an extension of a nilpotent group by a locally finite group of finite exponent.     

Möbius Isoparametric Hypersurfaces in S n+1 with Two Distinct Principal Curvatures

A hypersurface x : M → S ⁿ⁺¹ without umbilic point is called a Möbius isoparametric hypersurface if its Möbius form Φ = ?ρ ^?2∑ _i (e _i (H) + ∑ _j (h _ij ?Hδ _ij )e _j (log ρ))θ _i vanishes and its Möbius shape operator $ {\Bbb {S}}A hypersurface x : M → S ^{n +1} without umbilic point is called a M?bius isoparametric hypersurface if its M?bius form Φ = −ρ⁻²∑ _i (e _i (H) + ∑ _j (h _ij −Hδ _ij )e _j (log ρ))θ _i vanishes and its M?bius shape operator ? = ρ⁻¹(S−Hid) has constant eigenvalues. Here {e _i } is a local orthonormal basis for I = dx·dx with dual basis {θ _i }, II = ∑ _ij h _ij θ _i ⊗θ _i is the second fundamental form, and S is the shape operator of x. It is clear that any conformal image of a (Euclidean) isoparametric hypersurface in S ^{n +1} is a M?bius isoparametric hypersurface, but the converse is not true. In this paper we classify all M?bius isoparametric hypersurfaces in S ^{n +1} with two distinct principal curvatures up to M?bius transformations. By using a theorem of Thorbergsson [1] we also show that the number of distinct principal curvatures of a compact M?bius isoparametric hypersurface embedded in S ^{n +1} can take only the values 2, 3, 4, 6. Received September 7, 2001, Accepted January 30, 2002     

Low Frequency Estimates and Local Energy Decay for Asymptotically Euclidean Laplacians

For Riemannian metrics G on ? ^d which are long range perturbations of the flat one, we prove estimates for (? Δ _G  ? λ ?iε)^?n as λ → 0, which are uniform with respect to ε, for all n ≤ [d/2] +1 in odd dimension and n ≤ d/2 in even dimension. We also give applications to the time decay of Schrödinger and Wave (or Klein–Gordon) equations.     

Difference scheme for an initial–boundary value problem for a singularly perturbed transport equation

An initial–boundary value problem for a singularly perturbed transport equation with a perturbation parameter ε multiplying the spatial derivative is considered on the set ? = G ∪ S, where ? = D? × [0 ≤ t ≤ T], D? = {0 ≤ x ≤ d}, S = S ^l ∪ S, and S ^l and S₀ are the lateral and lower boundaries. The parameter ε takes arbitrary values from the half-open interval (0,1]. In contrast to the well-known problem for the regular transport equation, for small values of ε, this problem involves a boundary layer of width O(ε) appearing in the neighborhood of S ^l ; in the layer, the solution of the problem varies by a finite value. For this singularly perturbed problem, the solution of a standard difference scheme on a uniform grid does not converge ε-uniformly in the maximum norm. Convergence occurs only if h=dN^-1 ? ε and N₀^-1 ? 1, where N and N₀ are the numbers of grid intervals in x and t, respectively, and h is the mesh size in x. The solution of the considered problem is decomposed into the sum of regular and singular components. With the behavior of the singular component taken into account, a special difference scheme is constructed on a Shishkin mesh, i.e., on a mesh that is piecewise uniform in x and uniform in t. On such a grid, a monotone difference scheme for the initial–boundary value problem for the singularly perturbed transport equation converges ε-uniformly in the maximum norm at an ?(N^?1 + N₀^?1) rate.     

The asymptotic ruin problem when the healthy and sick periods form an alternating renewal process

Let {T₁, Y₁}^∞_i=1 be a sequence of positive independent random variables. Let, also, Z₁ = βY′₁ ? πT_i, i = 1, 2, …, where Y′₁ = Max(0, Y_i ? w), w ? 0, and where β < 0 and π is such that E(Z₁) < 0. We consider the random walk of partial sums S_n = ?ⁿ_i=1Z_i in the presence of an absorbing region (u, ∞), u ? 0, and S₀ ≡ 0. Of interest is $\text{ψ(u) = Pr(}\text{S}\text{?}\text{≤ u)}$ where S? = Sup(0, S₁, S₂, …, S_n, …).     

Sharp bounds for the number of 3‐independent partitions and the chromaticity of bipartite graphs

Given a graph G and an integer k ≥ 1, let α(G, k) denote the number of k‐independent partitions of G. Let ??^?s(p,q) (resp., ??₂^?s(p,q)) denote the family of connected (resp., 2‐connected) graphs which are obtained from the complete bipartite graph K_p,q by deleting a set of s edges, where p ≥ q ≥ 2. This paper first gives a sharp upper bound for α(G,3), where G ∈ ?? ^?s(p,q) and 0 ≤ s ≤ (p ? 1)(q ? 1) (resp., G ∈ ?? ₂^?s(p,q) and 0 ≤ s ≤ p + q ? 4). These bounds are then used to show that if G ∈ ?? ^?s(p,q) (resp., G ∈ ?? ₂^?s (p,q)), then the chromatic equivalence class of G is a subset of the union of the sets ??^?s_i(p+i,q?i) where max and s_i = s ? i(p?q+i) (resp., a subset of ??₂^?s(p,q), where either 0 ≤ s ≤ q ? 1, or s ≤ 2q ? 3 and p ≥ q + 4). By applying these results, we show finally that any 2‐connected graph obtained from K_p,q by deleting a set of edges that forms a matching of size at most q ? 1 or that induces a star is chromatically unique. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 48–77, 2001     

Generalized n-tuple colorings of a graph: A counterexample to a conjecture of Brigham and Dutton

In their papers (Technical Report CS-TR 50, University of Central Florida, 1980; J. Combin. Theory Ser. B32 (1982), 90–94) Brigham and Dutton introduce the notion of (n : i)-chromatic numbers of a graph, a generalization of Stahl's nth chromatic numbers (J. Combin. Theory Ser. B20, (1976), 185–203). The (n : i)-chromatic number of a graph G, denoted by χ_nⁱ(G), is the smallest integer m such that each vertex of G can be colored with a set of n colors in {1, 2,…, m} in such a way that any two adjacent vertices have exactly i colors in common. Brigham and Dutton conjecture at the end of loc cit that for all integers n and i with 0 ≤ i ≤ n ? 1, and for every graph G, χ_nⁱ⁺¹(G) ≤ χ_nⁱ(G). We prove this conjecture in some special cases and disprove it in the general case.     

The topological type of the α-sections of convex sets

An α=(α₁,…,αk)(0?αi?1) section of a family {K₁,…,Kk} of convex bodies in Rd is a transversal halfspace H⁺ for which Vold(Ki∩H⁺)=αi⋅Vold(Ki) for every 1?i?k. Our main result is that for any well-separated family of strictly convex sets, the space of α-sections is diffeomorphic to Sd−k.     

The maximal Fejér operator on the spacesH p (R×···×R)

It is shown that the maximal operator of the Fejér means of a tempered distribution is bounded from thed-dimensional Hardy spaceH _p (R×···×R) toL _p (R ^d ) (1/2<p<∞) and is of weak type (H ₁ ^?i ,L ₁) (i=1,…,d), where the Hardy spaceH ₁ ^?i is defined by a hybrid maximal function. As a consequence, we obtain that the Fejér means of a functionf ∈H ₁ ^?i ?L(logL) ^d?1 converge a.e. to the function in question. Moreover, we prove that the Fejér means are uniformly bounded onH _p (R×···×R) whenever 1/2<p<∞. Thus, in casef ∈H _p (R×···×R) the Fejér means converge tof inH _p (R×···×R) norm. The same results are proved for the conjugate Fejér means, too.     

Vertex partitions and maximum degenerate subgraphs

Let G be a graph with maximum degree d≥ 3 and ω(G)≤ d, where ω(G) is the clique number of the graph G. Let p₁ and p₂ be two positive integers such that d = p₁ + p₂. In this work, we prove that G has a vertex partition S₁, S₂ such that G[S₁] is a maximum order (p₁‐1)‐degenerate subgraph of G and G[S₂] is a (p₂‐1)‐degenerate subgraph, where G[S_i] denotes the graph induced by the set S_i in G, for i = 1,2. On one hand, by using a degree‐equilibrating process our result implies a result of Bollobas and Marvel [ 1 ]: for every graph G of maximum degree d≥ 3 and ω(G)≤ d, and for every p₁ and p₂ positive integers such that d = p₁ + p₂, the graph G has a partition S₁,S₂ such that for i = 1,2, Δ(G[S_i])≤ p_i and G[S_i] is (p_i‐1)‐degenerate. On the other hand, our result refines the following result of Catlin in [ 2 ]: every graph G of maximum degree d≥ 3 has a partition S₁,S₂ such that S₁ is a maximum independent set and ω(G[S₂])≤ d‐1; it also refines a result of Catlin and Lai [ 3 ]: every graph G of maximum degree d≥ 3 has a partition S₁,S₂ such that S₁ is a maximum size set with G[S₁] acyclic and ω(G[S₂])≤ d‐2. The cases d = 3, (d,p₁) = (4,1) and (d,p₁) = (4,2) were proved by Catlin and Lai [ 3 ]. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 227–232, 2007     

Combinational properties of sets of residues modulo a prime and the Erdős—Graham problem

Consider an arbitrary ε > 0 and a sufficiently large prime p > 2. It is proved that, for any integer a, there exist pairwise distinct integers x ₁, x ₂, ..., x _N , where N = 8([1/ε + 1/2] + 1)² such that 1 ≤ x _i ≤ p ^ε, i = 1, ..., N, and $$a \equiv x_1^{ - 1} + \cdots + x_N^{ - 1} (\bmod p)$$ , where x _i ^?1 is the least positive integer satisfying x _i ^?1 x _i ≡ 1 (modp). This improves a result of Sparlinski.     

Intersection theorems for group divisible difference sets

Let D be an (m,n;k;λ₁,λ₂)-group divisible difference set (GDDS) of a group G, written additively, relative to H, i.e. D is a k-element subset of G, H is a normal subgroup of G of index m and order n and for every nonzero element g of G,?{(d₁,d₂)?,d₁,d₂?D,d₁?d₂=g}? is equal to λ₁ if g is in H, and equal to λ₂ if g is not in H. Let H₁,H₂,…,H_m be distinct cosets of H in G and S_i=D∩H_i for all i=1,2,…,m. Some properties of S₁,S₂,…,S_m are studied here. Table 1 shows all possible cardinalities of S_i's when the order of G is not greater than 50 and not a prime. A matrix characterization of cyclic GDDS's with λ₁=0 implies that there exists a cyclic affine plane of even order, say n, only if n is divisible by 4 and there exists a cyclic (n?1,$\text{1}\text{2}$n?1,$\text{1}\text{4}$n?1)-difference set.     

The k-factor conjecture is true

A sequence 〈d_i〉, 1≤i≤n, is called graphical if there exists a graph whose i^th vertex has degree d_i for all i. It is shown that the sequences 〈d_i〉 and 〈d_i-k〉 are graphical only if there exists a graph G whose degree sequence is 〈d_i〉 and which has a regular subgraph with k lines at each vertex. Similar theorems have been obtained for digraphs. These theorems resolve comjectures given by A.R. Rao and S.B. Rao, and by B. Grünbaum.