Subgraphs smaller than the girth

For graphs A, B, let () denote the number of subsets of nodes of A for which the induced subgraph is B. If G and H both have girth > k, and if () = () for every k-node tree T, then for every k-node forest F, () = (). Say the spread of a tree is the number of nodes in a longest path. If G is regular of degree d, on n nodes, with girth > k, and if F is a forest of total spread ≤k, then the value of () depends only on n and d.     

The size of strength-maximal graphs

Let G be a graph and let k′(G) be the edge-connectivity of G. The strength of G, denoted by k?′(G), is the maximum value of k′(H), where H runs over all subgraphs of G. A simple graph G is called k-maximal if k?′(G) ≤ k but for any edge e ∈ E(G^c), k?′(G + e) ≥ k + 1. Let G be a k-maximal graph of order n. In [3], Mader proved |E(G)| ≤ (n - k)k + (). In this note, we shall show (n - 1)k - () In?n/k + 2)? ≤ |E(G|, and characterize the extremal graphs. We shall also give a characterization of all k-maximal graphs.     

The chromatic index of graphs of even order with many edges

We show that, for r = 1, 2, a graph G with 2n + 2 (≥6) vertices and maximum degree 2n + 1 - r is of Class 2 if and only if |E(G/v)| > () - rn, where v is a vertex of G of minimum degree, and we make a conjecture for 1 ≤ r ≤ n, of which this result is a special case. For r = 1 this result is due to Plantholt.     

On three zero-sum Ramsey-type problems

For a graph G whose number of edges is divisible by k, let R(G,Z_k) denote the minimum integer r such that for every function f: E(K_r) ? Z_k there is a copy G¹ of G in K_r so that Σe∈E(G¹) f(e) = 0 (in Z_k). We prove that for every integer k₁ R(K_n, Z_k) ≤ n + O(k³ log k) provided n is sufficiently large as a function of k and k divides (). If, in addition, k is an odd prime-power then R(K_n, Z_k) ≤ n + 2k - 2 and this is tight if k is a prime that divides n. A related result is obtained for hypergraphs. It is further shown that for every graph G on n vertices with an even number of edges R(G,Z₂) ≤ n + 2. This estimate is sharp. © 1993 John Wiley & Sons, Inc.     

The Triebel - Lizorkin Scale of Function Spaces for the Fourier - Helgason Transform

We define and investigate the Triebel - Lizorkin scale of function spaces F, with 1< p < ∞, 1< q ≤ ∞ for the Fourier-Helgason transform on symmetric Riemannian manifolds of the noncompact type.     

A generalization of Plantholt's theorem

Let K denote the complete graph K_2n+1 with each edge replicated r times and let χ′(G) denote the chromatic index of a multigraph G. A multigraph G is critical if χ′(G) > χ′(G/e) for each edge e of G. Let S be a set of sn – 1 edges of K. We show that, for 0 < s ≦ r, G/S is critical and that χ′ (G/(S ∪{e})) = 2rn + r – s for all e ∈ E(G/S). Plantholt [M. Plantholt, The chromatic index of graphs with a spanning star. J. Graph Theory 5 (1981) 5–13] proved this result in the case when r = 1.     

Enumeration of graphs by degree sequence

The degree sequence (d₀, d₁, …, d_p-1) of a graph G of order p is defined by d_k = the number of points of G of degree k. Methods of Robinson are extended to produce a generating function F(x₀, x₁, x₂, …) where the coefficient of x…x is the number of graphs of order p having degree sequence (d₀, …, d_p-1).     

Graph minors and linkages

Bollobás and Thomason showed that every 22k‐connected graph is k‐linked. Their result used a dense graph minor. In this paper, we investigate the ties between small graph minors and linkages. In particular, we show that a 6‐connected graph with a K minor is 3‐linked. Further, we show that a 7‐connected graph with a K minor is (2,5)‐linked. Finally, we show that a graph of order n and size at least 7n?29 contains a K minor. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 75–91, 2005     

Entropy Numbers in Weighted Function Spaces and Eigenvalue Distributions of Some Degenerate Pseudodifferential Operators II

This paper is the continuation of [17]. We investigate mapping and spectral properties of pseudodifferential operators of type Ψ with χ χ ? ? and 0 ≤ γ ≤ 1 in the weighted function spaces B (?ⁿ, w(x)) and F (?ⁿ, w(x)) treated in [17]. Furthermore, we study the distribution of eigenvalues and the behaviour of corresponding root spaces for degenerate pseudodifferential operators preferably of type b₂(x) b(x, D) b₁(x), where b₁(x) and b₂(x) are appropriate functions and b(x, D) ? Ψ. Finally, on the basis of the Birman-Schwinger principle, we deal with the “negative spectrum” (bound states) of related symmetric operators in L₂.     

On the minimum size of tight hypergraphs

A k-graph, H = (V, E), is tight if for every surjective mapping f: V → {1,….k} there exists an edge α ? E sicj tjat f|_α is injective. Clearly, 2-graphs are tight if and only if they are connected. Bounds for the minimum number ? of edges in a tight k-graph with n vertices are given. We conjecture that ? for every n and prove the equality when 2n + 1 is prime. From the examples, minimal embeddings of complete graphs into surfaces follow. © 1992 John Wiley & Sons, Inc.     

The red‐shift effect and radiation decay on black hole spacetimes

We consider solutions to the linear wave equation □_g? = 0 on a (maximally extended) Schwarzschild spacetime with parameter M > 0, evolving from sufficiently regular initial data prescribed on a complete Cauchy surface Σ, where the data are assumed only to decay suitably at spatial infinity. (In particular, the support of ? may contain the bifurcate event horizon.) It is shown that the energy flux F(??) of the solution (as measured by a strictly timelike T? that asymptotically matches the static Killing field) through arbitrary achronal subsets ?? of the black hole exterior region satisfies the bound F(??) ≤ C E(v + u), where v and u denote the infimum of the Eddington‐Finkelstein advanced and retarded time of ??, v₊ denotes max{1, v}, and u₊ denotes max{1, u}, where C is a constant depending only on the parameter M, and E depends on a suitable norm of the solution on the hypersurface t ? u + v = 1. (The bound applies in particular to subsets ?? of the event horizon or null infinity.) It is also shown that ? satisfies the pointwise decay estimate |?| ≤ C Ev in the entire exterior region, and the estimates |r?| ≤ C_R?E(1 + |u|)^?1/2 and |r^1/2?| ≤ C_R?Eu in the region {r ≥ R?} ∩ J⁺(Σ) for any R? > 2M. The estimates near the event horizon exploit an integral energy identity normalized to local observers. This estimate can be thought to quantify the celebrated red‐shift effect. The results in particular give an independent proof of the classical result |?| ≥ C E of Kay and Wald without recourse to the discrete isometries of spacetime. © 2009 Wiley Periodicals, Inc.     

Extremal problems on set systems

For a family $\boldmath{F}(k) = \{{\mathcal F}_1^{(k)}, {\mathcal F}_2^{(k)},\ldots,{\mathcal F}_t^{(k)}\}$ of k‐uniform hypergraphs let ex (n, F (k)) denote the maximum number of k‐tuples which a k‐uniform hypergraph on n vertices may have, while not containing any member of F (k). Let r_k(n) denote the maximum cardinality of a set of integers Z?[n], where Z contains no arithmetic progression of length k. For any k≥3 we introduce families $\boldmath{F}(k) = \{{\mathcal F}_1^{(k)},{\mathcal F}_2^{(k)}\}$ and prove that n^k?2r_k(n)≤ex (n_k², F (k))≤c_kn^k?1 holds. We conjecture that ex(n, F (k))=o(n^k?1) holds. If true, this would imply a celebrated result of Szemerédi stating that r_k(n)=o(n). By an earlier result o Ruzsa and Szemerédi, our conjecture is known to be true for k=3. The main objective of this article is to verify the conjecture for k=4. We also consider some related problems. © 2002 Wiley Periodicals, Inc. Random Struct. Alg. 20: 131–164, 2002.     

Properly colored subgraphs and rainbow subgraphs in edge‐colorings with local constraints

We consider a canonical Ramsey type problem. An edge‐coloring of a graph is called m‐good if each color appears at most m times at each vertex. Fixing a graph G and a positive integer m, let f(m, G) denote the smallest n such that every m‐good edge‐coloring of K_n yields a properly edge‐colored copy of G, and let g(m, G) denote the smallest n such that every m‐good edge‐coloring of K_n yields a rainbow copy of G. We give bounds on f(m, G) and g(m, G). For complete graphs G = K_t, we have c₁mt²/ln t ≤ f(m, K_t) ≤ c₂mt², and cmt³/ln t ≤ g(m, K_t) ≤ cmt³/ln t, where c₁, c₂, c, c are absolute constants. We also give bounds on f(m, G) and g(m, G) for general graphs G in terms of degrees in G. In particular, we show that for fixed m and d, and all sufficiently large n compared to m and d, f(m, G) = n for all graphs G with n vertices and maximum degree at most d. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2003     

Z-cyclic triplewhist tournaments when the number of players involves primes of the form 8u + 5

When the number of players, v, in a whist tournament, Wh(v), is ≡ 1 (mod 4) the only instances of a Z-cyclic triplewhist tournament, TWh(v), that appear in the literature are for v = 21,29,37. In this study we present Z-cyclic TWh(v) for all v ∈ T = {v = 8u + 5: v is prime, 3 ≤ u ≤ 249}. Additionally, we establish (1) for all v ∈ T there exists a Z-cyclic TWh(vⁿ) for all n ≥ 1, and (2) if v_i ∈ T, i = 1,…,n, there exists a Z-cyclic TWh(v… v) for all ?_i ≥ 1. It is believed that these are the first instances of infinite classes of Z-cyclic TWh(v), v ≡ 1 (mod 4). © 1994 John Wiley & Sons, Inc.     

Perfect matchings in random uniform hypergraphs

Let ??_k(n, p) be the random k‐uniform hypergraph on V = [n] with edge probability p. Motivated by a theorem of Erd?s and Rényi 7 regarding when a random graph G(n, p) = ??₂(n, p) has a perfect matching, the following conjecture may be raised. (See J. Schmidt and E. Shamir 16 for a weaker version.) Conjecture. Let k|n for fixed k ≥ 3, and the expected degree d(n, p) = p(). Then (Erd?s and Rényi 7 proved this for G(n, p).) Assuming d(n, p)/n^1/2 → ∞, Schmidt and Shamir 16 were able to prove that ??_k(n, p) contains a perfect matching with probability 1 ? o(1). Frieze and Janson 8 showed that a weaker condition d(n, p)/n^1/3 → ∞ was enough. In this paper, we further weaken the condition to A condition for a similar problem about a perfect triangle packing of G(n, p) is also obtained. A perfect triangle packing of a graph is a collection of vertex disjoint triangles whose union is the entire vertex set. Improving a condition p ≥ cn^?2/3+1/15 of Krivelevich 12 , it is shown that if 3|n and p ? n^?2/3+1/18, then © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 111–132, 2003     

Entropy Numbers in Weighted Function Spaces and Eigenvalue Distributions of Some Degenerate Pseudodifferential Operators I

In this paper we study weighted function spaces of type B(?ⁿ, Q(x)) and F(?ⁿ, Q(x)), where Q(x) is a weight function of at most polynomial growth. Of special interest are the weight functions Q(x) = (1 + |x|²)^α/2 with α ? ?. The main result deals with estimates for the entropy numbers of compact embeddings between spaces of this type.     

On restricted min‐wise independence of permutations

A family of permutations ℱ ⊆ S_n with a probability distribution on it is called k-restricted min-wise independent if we have Pr[min π(X) = π(x)] = 1/|X| for every subset X ⊆ [n] with |X| ≤ k, every x ∈ X, and π ∈ ℱ chosen at random. We present a simple proof of a result of Norin: every such family has size at least Some features of our method might be of independent interest. The best available upper bound for the size of such family is 1 + ∑ (j − 1)(). We show that this bound is tight if the goal is to imitate not the uniform distribution on S_n, but a distribution given by assigning suitable priorities to the elements of [n] (the stationary distribution of the Tsetlin library, or self-organizing lists). This is analogous to a result of Karloff and Mansour for k-wise independent random variables. We also investigate the cases where the min-wise independence condition is required only for sets X of size exactly k (where we have only an Ω(log log n + k) lower bound), or for sets of size k and k − 1 (where we already obtain a lower bound of n − k + 2). © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2003     

On the well‐posedness of the Cauchy problem for an MHD system in Besov spaces

This paper is devoted to the study of the Cauchy problem of incompressible magneto‐hydrodynamics system in the framework of Besov spaces. In the case of spatial dimension n?3, we establish the global well‐posedness of the Cauchy problem of an incompressible magneto‐hydrodynamics system for small data and the local one for large data in the Besov space ? (?ⁿ), 1?p<∞ and 1?r?∞. Meanwhile, we also prove the weak–strong uniqueness of solutions with data in ? (?ⁿ)∩L²(?ⁿ) for n/2p+2/r>1. In the case of n=2, we establish the global well‐posedness of solutions for large initial data in homogeneous Besov space ? (?²) for 2<p<∞ and 1?r<∞. Copyright © 2008 John Wiley & Sons, Ltd.     

On the number of cycles of given length of a free word in several random permutations

Let w ≠ 1 be a free word in the symbols g₁,…, g_k and their inverses (i.e., an element of the free group F_k). For any s₁,…, s_k, in the group s_n of all permutation of n objects, we denote by w(s₁,…,s_k) ? S_n the permutation obtained by replacing g₁,…, g_k with s₁,…, s_k in the expression of w. Let X (s₁,…, s_k) denote the number of cycles of length L of w(s₁,…, s_k). For fixed w and L, we show that X, viewed as a random variable on S_n^k, has (for n →∞) a Poisson-type limit distribution, which can be computed precisely. © 1994 John Wiley & Sons, Inc.     

Tangential Convergence of Temperatures and Harmonic Functions in Besov and in Triebel-Lizorkin Spaces

We study the maximal function Mf(x) = sup |f(x + y, t)| when Ω is a region in the (y,t) Ω upper half space R and f(x, t) is the harmonic extension to R₊^N+1 of a distribution in the Besov space B^α_p,q(R^N) or in the Triebel-Lizorkin space F^α_p,q(R^N). In particular, we prove that when Ω= {|_y|^{N/ (N-αp)} < t < 1} the operator M is bounded from F (R^N) into L^p (R^N). The admissible regions for the spaces B (R^N) with p < q are more complicated.