Linear recurrence relations for binomial coefficients modulo a prime

We investigate when the sequence of binomial coefficients modulo a prime p, for a fixed positive integer k, satisfies a linear recurrence relation of (positive) degree h in the finite range 0?i?k. In particular, we prove that this cannot occur if 2h?k<p−h. This hypothesis can be weakened to 2h?k<p if we assume, in addition, that the characteristic polynomial of the relation does not have −1 as a root. We apply our results to recover a known bound for the number of points of a Fermat curve over a finite field.     

On the Kurosh rank of the intersection of subgroups in free products of groups

The Kurosh rank rK(H) of a subgroup H of a free product of groups Gα, α∈I, is defined accordingly to the classic Kurosh subgroup theorem as the number of free factors of H. We prove that if H₁, H₂ are subgroups of and H₁, H₂ have finite Kurosh rank, then , where , q^∗ is the minimum of orders >2 of finite subgroups of groups Gα, α∈I, q^∗:=∞ if there are no such subgroups, and if q^∗=∞. In particular, if the factors Gα, α∈I, are torsion-free groups, then .     

A simple proof for a theorem of Luxemburg and Zaanen

In this paper a simple proof for the following theorem, due to Luxemburg and Zaanen is given: an Archimedean vector lattice A is Dedekind σ-complete if and only if A has the principal projection property and A is uniformly complete. As an application, we give a new and short proof for the following version of Freudenthal's spectral theorem: let A be a uniformly complete vector lattice with the principal projection property and let 0<u∈A. For any element w in A such that 0?w?u there exists a sequence in A which satisfies , where each element sn is of the form , with real numbers α₁,…,αk such that 0?αi?1 (i=1,…,k) and mutually disjoint components p₁,…,pk of u.     

Bandwidth of the corona of two graphs

The bandwidth B(G) of a graph G is the minimum of the quantity max{|f(u)-f(v)|:uv∈E(G)} taken over all injective integer numberings f of G. The corona of two graphs G and H, written as G°H, is the graph obtained by taking one copy of G and |V(G)| copies of H, and then joining the ith vertex of G to every vertex in the ith copy of H. In this paper, we investigate the bandwidth of the corona of two graphs. For a graph G, we denote the connectivity of G by κ(G). Let G be a graph on n vertices with B(G)=κ(G)=k?2 and let H be a graph of order m. Let c,p and q be three integers satisfying 1?c?k-1 and . We define h_i=(2k-1)m+(k-i)(⌊(2k-1)m/i⌋+1)+1 for i=1,2,…,k and b=max{⌈(n(m+1)-qm-1)/(p+2)⌉,⌈(n(m+1)+k-q-1)/(p+3)⌉}. Then, among other results, we prove that

     

Colouring graphs with bounded generalized colouring number

Given a graph G and a positive integer p, χ_p(G) is the minimum number of colours needed to colour the vertices of G so that for any i≤p, any subgraph H of G of tree-depth i gets at least i colours. This paper proves an upper bound for χ_p(G) in terms of the k-colouring number of G for k=2^p−2. Conversely, for each integer k, we also prove an upper bound for in terms of χ_k+2(G). As a consequence, for a class K of graphs, the following two statements are equivalent:

(a)

For every positive integer p, χ_p(G) is bounded by a constant for all G∈K.

(b)

For every positive integer k, is bounded by a constant for all G∈K.

It was proved by Nešet?il and Ossona de Mendez that (a) is equivalent to the following:

(c)

For every positive integer q, ∇_q(G) (the greatest reduced average density of G with rank q) is bounded by a constant for all G∈K.

Therefore (b) and (c) are also equivalent. We shall give a direct proof of this equivalence, by introducing ∇_q−(1/2)(G) and by showing that there is a function F_k such that . This gives an alternate proof of the equivalence of (a) and (c).     

Hardy space estimates for the wave equation on compact Lie groups

Let −L be the Laplacian. In this paper, we prove that on a compact Lie group G of dimension n, the multiplier operator , s∈(0,1], extends to a bounded operator on the Hardy space Hp(G), 0<p<∞, if and only if . The result is an analogue of a well-known theorem in Euclidean space.     

Linkability in iterated line graphs

We prove that for every graph H with the minimum degree δ?5, the third iterated line graph L³(H) of H contains as a minor. Using this fact we prove that if G is a connected graph distinct from a path, then there is a number k_G such that for every i?k_G the i-iterated line graph of G is -linked. Since the degree of Lⁱ(G) is even, the result is best possible.     

Haj?asz-Sobolev imbedding and extension

The author establishes some geometric criteria for a Haj?asz-Sobolev -extension (resp. -imbedding) domain of Rn with n?2, s∈(0,1] and p∈[n/s,∞] (resp. p∈(n/s,∞]). In particular, the author proves that a bounded finitely connected planar domain Ω is a weak α-cigar domain with α∈(0,1) if and only if for some/all s∈[α,1) and p=(2−α)/(s−α), where denotes the restriction of the Triebel-Lizorkin space on Ω.     

Operator space structure and amenability for Figà-Talamanca-Herz algebras

Column and row operator spaces—which we denote by COL and ROW, respectively—over arbitrary Banach spaces were introduced by the first-named author; for Hilbert spaces, these definitions coincide with the usual ones. Given a locally compact group G and p,p′∈(1,∞) with , we use the operator space structure on to equip the Figà-Talamanca-Herz algebra A_p(G) with an operator space structure, turning it into a quantized Banach algebra. Moreover, we show that, for p?q?2 or 2?q?p and amenable G, the canonical inclusion A_q(G)⊂A_p(G) is completely bounded (with cb-norm at most , where is Grothendieck's constant). As an application, we show that G is amenable if and only if A_p(G) is operator amenable for all—and equivalently for one—p∈(1,∞); this extends a theorem by Ruan.     

Finite jet determination of CR mappings

We prove the following finite jet determination result for CR mappings: Given a smooth generic submanifold M⊂CN, N?2, that is essentially finite and of finite type at each of its points, for every point p∈M there exists an integer ?p, depending upper-semicontinuously on p, such that for every smooth generic submanifold M^′⊂CN of the same dimension as M, if are two germs of smooth finite CR mappings with the same ?p jet at p, then necessarily for all positive integers k. In the hypersurface case, this result provides several new unique jet determination properties for holomorphic mappings at the boundary in the real-analytic case; in particular, it provides the finite jet determination of arbitrary real-analytic CR mappings between real-analytic hypersurfaces in CN of D'Angelo finite type. It also yields a new boundary version of H. Cartan's uniqueness theorem: if Ω,Ω^′⊂CN are two bounded domains with smooth real-analytic boundary, then there exists an integer k, depending only on the boundary ∂Ω, such that if are two proper holomorphic mappings extending smoothly up to ∂Ω near some point p∈∂Ω and agreeing up to order k at p, then necessarily H₁=H₂.     

Sequences and filters of characters characterizing subgroups of compact Abelian groups

Let H be a countable subgroup of the metrizable compact Abelian group G and a (not necessarily continuous) character of H. Then there exists a sequence of (continuous) characters of G such that limn→∞χn(α)=f(α) for all α∈H and does not converge whenever α∈G?H. If one drops the countability and metrizability requirement one can obtain similar results by using filters of characters instead of sequences. Furthermore the introduced methods allow to answer questions of Dikranjan et al.     

4-regular claw-free IM-extendable graphs

A graph G is induced matching extendable (shortly, IM-extendable), if every induced matching of G is included in a perfect matching of G. A graph G is claw-free, if G does not contain any induced subgraph isomorphic to K_1,3. The kth power of a graph G, denoted by G^k, is the graph with vertex set V(G) in which two vertices are adjacent if and only if the distance between them in G is at most k. In this paper, the 4-regular claw-free IM-extendable graphs are characterized. It is shown that the only 4-regular claw-free connected IM-extendable graphs are , and T_r, r?2, where T_r is the graph with 4r vertices u_i,v_i,x_i,y_i, 1?i?r, such that for each i with 1?i?r, {u_i,v_i,x_i,y_i} is a clique of T_r and . We also show that a 4-regular strongly IM-extendable graph must be claw-free. As a consequence, the only 4-regular strongly IM-extendable graphs are K₄×K₂, and .     

Boxicity of Halin graphs

A k-dimensional box is the Cartesian product R₁×R₂×?×R_k where each R_i is a closed interval on the real line. The boxicity of a graph G, denoted as is the minimum integer k such that G is the intersection graph of a collection of k-dimensional boxes. Halin graphs are the graphs formed by taking a tree with no degree 2 vertex and then connecting its leaves to form a cycle in such a way that the graph has a planar embedding. We prove that if G is a Halin graph that is not isomorphic to K₄, then . In fact, we prove the stronger result that if G is a planar graph formed by connecting the leaves of any tree in a simple cycle, then unless G is isomorphic to K₄ (in which case its boxicity is 1).     

Kuznietsov trace formula and weighted distribution of Hecke eigenvalues

Let (X,μ) be a measurable topological space. Let S₁,S₂,… be a family of finite subsets of X. Suppose each x∈S_i has a weight w_ix∈R⁺ assigned to it. We say {S_i} is {w_i}-distributed with respect to the measure μ if for any continuous function f on X, we have .Let S(N,k) be the space of modular cusp forms over Γ₀(N) of weight k and let be a basis which consists of Hecke eigenforms. Let a_r(h) be the rth Fourier coefficient of h. Let x_p^h be the eigenvalue of h relative to the normalized Hecke operator T′_p. Let ||·|| be the Petersson norm on S(N,k). In this paper we will show that for any even integer k?3, is -distributed with respect to a polynomial times the Sato-Tate measure when N→∞.     

Cubicity, boxicity, and vertex cover

A k-dimensional box is the cartesian product R₁×R₂×?×R_k where each R_i is a closed interval on the real line. The boxicity of a graph G, denoted as box(G), is the minimum integer k such that G is the intersection graph of a collection of k-dimensional boxes. A unit cube in k-dimensional space or a k-cube is defined as the cartesian product R₁×R₂×?×R_k where each R_i is a closed interval on the real line of the form [a_i,a_i+1]. The cubicity of G, denoted as cub(G), is the minimum k such that G is the intersection graph of a collection of k-cubes. In this paper we show that cub(G)≤t+⌈log(n−t)⌉−1 and , where t is the cardinality of a minimum vertex cover of G and n is the number of vertices of G. We also show the tightness of these upper bounds.F.S. Roberts in his pioneering paper on boxicity and cubicity had shown that for a graph G, and , where n is the number of vertices of G, and these bounds are tight. We show that if G is a bipartite graph then and this bound is tight. We also show that if G is a bipartite graph then . We point out that there exist graphs of very high boxicity but with very low chromatic number. For example there exist bipartite (i.e., 2 colorable) graphs with boxicity equal to . Interestingly, if boxicity is very close to , then chromatic number also has to be very high. In particular, we show that if , s≥0, then , where χ(G) is the chromatic number of G.