Hypercube subgraphs with minimal detours

Define a minimal detour subgraph of the n-dimensional cube to be a spanning subgraph G of Q_n having the property that for vertices x, y of Q_n, distances are related by d_G(x, y) ≤ d_Qn(x, y) + 2. Let f(n) be the minimum number of edges of such a subgraph of Q_n. After preliminary work on distances in subgraphs of product graphs, we show that The subgraphs we construct to establish this bound have the property that the longest distances are the same as in Q_n, and thus the diameter does not increase. We establish a lower bound for f(n), show that vertices of high degree must be distributed throughout a minimal detour subgraph of Q_n, and end with conjectures and questions. © 1996 John Wiley & Sons, Inc.     

Exponential bounds of mean error for the kernel estimates of regression functions

Let (X, Y), (X₁, Y₁), …, (X_n, Y_n) be i.d.d. R^r × R-valued random vectors with E|Y| < ∞, and let Q_n(x) be a kernel estimate of the regression function Q(x) = E(Y|X = x). In this paper, we establish an exponential bound of the mean deviation between Q_n(x) and Q(x) given the training sample Zⁿ = (X₁, Y₁, …, X_n, Y_n), under conditions as weak as possible.     

Multivariable monotonic optimization over multivalued logics and rectangular design lattices

A minimum dichotomous direct search procedure is given for finding the optimum combination of N variables, each having M(n) possible values, when a certain monotonicity condition is satisfied. The least upper bound on the number of objective function evaluations is 1 + Σ^N_n=1Q(n), where Q(n) is defined by 2^Q(n)-1<M(n) < 2^Q(n), whereas the total number of possibilities is Π^N_R=1M(n). An example shows where the procedure applies to restricted problems in multivalued logic and engineering design.     

A lower bound on the independence number of arbitrary hypergraphs

We present a lower bound on the independence number of arbitrary hypergraphs in terms of the degree vectors. The degree vector of a vertex v is given by d(v) = (d₁(v), d₂(v), …) where d_m(v) is the number of edges of size m containing v. We define a function f with the property that any hypergraph H = (V, E) satisfies α(H) ≥ Σ_v∈V f(d(v)). This lower bound is sharp when H is a match, and it generalizes known bounds of Caro/Wei and Caro/Tuza for ordinary graphs and uniform hypergraphs. Furthermore, an algorithm for computing independent sets of size as guaranteed by the lower bound is given. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 213–221, 1999     

Syzygies and Diagonal Resolutions for Dihedral Groups

Let G be a finite group with integral group ring Λ =Z[G]. The syzygies Ω_r(Z) are the stable classes of the intermediate modules in a free Λ-resolution of the trivial module. They are of significance in the cohomology theory of G via the “co-represention theorem” H^r(G, N) = Hom_𝒟er(Ω_r(Z), N). We describe the Ω_r(Z) explicitly for the dihedral groups D_4n+2, so allowing the construction of free resolutions whose differentials are diagonal matrices over Λ.     

Sharp bounds for the largest eigenvalue of the signless Laplacian of a graph

Let G be a simple connected graph with n vertices and m edges. Denote the degree of vertex v_i by d(v_i). The matrix Q(G)=D(G)+A(G) is called the signless Laplacian of G, where D(G)=diag(d(v₁),d(v₂),…,d(v_n)) and A(G) denote the diagonal matrix of vertex degrees and the adjacency matrix of G, respectively. Let q₁(G) be the largest eigenvalue of Q(G). In this paper, we first present two sharp upper bounds for q₁(G) involving the maximum degree and the minimum degree of the vertices of G and give a new proving method on another sharp upper bound for q₁(G). Then we present three sharp lower bounds for q₁(G) involving the maximum degree and the minimum degree of the vertices of G. Moreover, we determine all extremal graphs which attain these sharp bounds.     

Cleaning Random d-Regular Graphs with Brooms

A model for cleaning a graph with brushes was recently introduced. Let α = (v ₁, v ₂, . . . , v _n ) be a permutation of the vertices of G; for each vertex v _i let ${N^+(v_i)=\{j: v_j v_i \in E {\rm and} j>\,i\}}${N^+(v_i)=\{j: v_j v_i \in E {\rm and} j>\,i\}} and N^-(v_i)={j: v_j v_i ? E and j <  i}{N^-(v_i)=\{j: v_j v_i \in E {\rm and} j<\,i\}} ; finally let b_a(G)=?_i=1ⁿ max{|N⁺(v_i)|-|N^-(v_i)|,0}{b_{\alpha}(G)=\sum_{i=1}^n {\rm max}\{|N^+(v_i)|-|N^-(v_i)|,0\}}. The Broom number is given by B(G) =  max _α b _α (G). We consider the Broom number of d-regular graphs, focusing on the asymptotic number for random d-regular graphs. Various lower and upper bounds are proposed. To get an asymptotically almost sure lower bound we use a degree-greedy algorithm to clean a random d-regular graph on n vertices (with dn even) and analyze it using the differential equations method (for fixed d). We further show that for any d-regular graph on n vertices there is a cleaning sequence such at least n(d + 1)/4 brushes are needed to clean a graph using this sequence. For an asymptotically almost sure upper bound, the pairing model is used to show that at most n(d+2?{d ln2})/4{n(d+2\sqrt{d \ln 2})/4} brushes can be used when a random d-regular graph is cleaned. This implies that for fixed large d, the Broom number of a random d-regular graph on n vertices is asymptotically almost surely \fracn4(d+Q(?d)){\frac{n}{4}(d+\Theta(\sqrt{d}))}.     

An integral formula for the heat kernel of tubular neighborhoods of complete (connected) Riemannian manifolds

Let M be a complete connected Riemannian manifold and let N be a submanifold of M. Let v: E _v»N be the normal bundle of N and exp _v : E _v»M its exponential map.Let (exp _infv ^/sup-1 , M ₀) be the Fermi chart relative to the submanifold N. Then, by using the Fermi coordinates we obtain an integral formula for the Dirichlet heat kernel p _t ^m (-,-). That is, we obtain a probabilistic representation for the integral _N f(y)p _t ^M (x,y) dywhere f is any measurable function of compact support in M ₀. This representation involves a submanifold semi-classical Brownian Riemannian bridge process. Then applying the integral formula via a Riemannian submersion in [5], we obtain heat kernel formulae for the complex projective space cP ⁿ, the quaternionic projective space QP ⁿ and the Caley line CaP ¹. The case of the Caley plane CaP ² eludes us due to the lack of a submersion theorem.This work is part of a Ph.D. Thesis which was undertaken under Professor K. D. Elworthy, Mathematics Institute, Warwick University, Coventry CV47AL, England, Great Britain.     

Universal entire functions with gap power series

Let be the family of all compact sets in which have connected complement. For K ε M we denote by A(K) the set of all functions which are continuous on K and holomorphic in its interior.Suppose that {z_n} is any unbounded sequence of complex numbers and let Q be a given sub-sequence of ₀.If Q has density Δ(Q) = 1 then there exists a universal entire function with lacunary power series

1. (1) (z) = ε^∞_{v = 0 v}Z^v, _v = 0 for v Q, which has for all K ε M the following properties simultaneously

2. (2) the sequence {(Z + Z_n)} is dense in A(K)

3. (3) the sequence { (ZZ_n)} is dense in A(K) if 0 K.

Also a converse result is proved: If is an entire function of the form (1) which satisfies (3), then Q must have maximal density Δ_max(Q) = 1.     

On the diameter and radius of randon subgraphs of the cube

The n-dimensional cube Qⁿ is the graph whose vertices are the subsets of {1,…n}, with two vertices adjacent if and only if their symmetric difference is a singleton. Clearly Qⁿ has diameter and radious n. Write M = n2^n-1 = e(Qⁿ) for the size of Qⁿ. Let Q = (Q_t)_o^M be a random Qⁿ-process. Thus Q^t is a spanning subgraph of Qⁿ of size t, and Q_t is obtained from Q_t–1 by the random addition of an edge of Qⁿ not in Q_t–1, Let t^(k) = τ(Q;δ?k) be the hitting time of the property of having minimal degree at least k. We show that the diameter d_t = diam (Q_t) of Q_t in almost every Q? behaves as follows: d_t starts infinite and is first finite at time t⁽¹⁾, it equals n + 1 for t⁽¹⁾ ? t⁽²⁾ and d_t, = n for t ? t⁽²⁾. We also show that the radius of Q_t, is first finite for t = t⁽¹⁾, when it assumes the value n. These results are deduced from detailed theorems concerning the diameter and radius of the almost surely unique largest component of Q_t, for t = Ω(M). © 1994 John Wiley & Sons, Inc.     

Existence of T*(3, 4,v)‐codes

A word of length k over an alphabet Q of size v is a vector of length k with coordinates taken from Q. Let Q^*₄ be the set of all words of length 4 over Q. A T^*(3, 4, v)‐code over Q is a subset C^*? Q^*₄ such that every word of length 3 over Q occurs as a subword in exactly one word of C^*. Levenshtein has proved that a T^*(3, 4, vv)‐code exists for all even v. In this paper, the notion of a generalized candelabra t‐system is introduced and used to show that a T^*(3, 4, v)‐code exists for all odd v. Combining this with Levenshtein's result, the existence problem for a T^*(3,4, v)‐code is solved completely. © 2004 Wiley Periodicals, Inc. J Combin Designs 13: 42–53, 2005.     

Decomposition of complete multigraphs into crown graphs

Let λ K _v be the complete multigraph, G a finite simple graph. A G-design of λ K _v is denoted by GD(v,G,λ). The crown graph Q _n is obtained by joining single pendant edge to each vertex of an n-cycle. We give new constructions for Q _n -designs. Let v and λ be two positive integers. For n=4, 6, 8 and λ≥1, there exists a GD(v,Q _n ,λ) if and only if either (1) v>2n and λ v(v?1)≡0 (mod 4n), or (2) v=2n and λ≡0 (mod 4). Let n≥4 be even. Then (1) there exists a GD(2n,Q _n ,λ) if and only if λ≡0 (mod 4). (2) There exists a GD(2n+1,Q _n ,λ) when λ≡0 (mod 4).     

Extremal cover times for random walks on trees

Let C_ν(T) denote the “cover time” of the tree T from the vertex v, that is, the expected number of steps before a random walk starting at v hits every vertex of T. Asymptotic lower bounds for C_ν(T) (for T a tree on n vertices) have been obtained recently by Kahn, Linial, Nisan and Saks, and by Devroye and Sbihi; here, we obtain the exact lower bound (approximately 2n In n) by showing that C_ν(T) is minimized when T is a star and v is one of its leaves. In addition, we show that the time to cover all vertices and then return to the starting point is minimized by a star (beginning at the center) and maximized by a path (beginning at one of the ends).     

Surjective partial differential operators on real analytic functions defined on open convex sets

Let P(D) be a partial differential operator with constant coefficients which is surjective on the space A(Ω) of real analytic functions on a covex open set Ω⊂ℝ ⁿ . Let L(P _m ) denote the localizations at ∞ (in the sense of H?rmander) of the principal part P _m . Then Q(x+iτN)≠ 0 for (x,τ)∈ℝ ⁿ ×(ℝ\{ 0}) for any Q∈L(P _m ) if N is a normal to δΩ which is noncharacteristic for Q. Under additional assumptions this implies that P _m must be locally hyperbolic. Received: 24 January 2000     

Neighborhood unions and hamilton cycles

Let G be a graph on n vertices and N₂(G) denote the minimum size of N(u) ∪ N(v) taken over all pairs of independent vertices u, v of G. We show that if G is 3-connected and N₂(G) ? ½(n + 1), then G has a Hamilton cycle. We show further that if G is 2-connected and N₂(G) ? ½(n + 3), then either G has a Hamilton cycle or else G belongs to one of three families of exceptional graphs.     

Q 2-free Families in the Boolean Lattice

For a family F{{\cal F}} of subsets of [n] = {1, 2, ..., n} ordered by inclusion, and a partially ordered set P, we say that F{{\cal F}} is P-free if it does not contain a subposet isomorphic to P. Let ex(n, P) be the largest size of a P-free family of subsets of [n]. Let Q ₂ be the poset with distinct elements a, b, c, d, a < b,c < d; i.e., the 2-dimensional Boolean lattice. We show that 2N − o(N) ≤ ex(n, Q ₂) ≤ 2.283261N + o(N), where N = \binomn?n/2 ?N = \binom{n}{\lfloor n/2 \rfloor}. We also prove that the largest Q ₂-free family of subsets of [n] having at most three different sizes has at most 2.20711N members.     

Sharp anisotropic estimates for the Boltzmann collision operator and its entropy production

This article provides sharp constructive upper and lower bound estimates for the Boltzmann collision operator with the full range of physical non-cut-off collision kernels (γ>−n and s∈(0,1)) in the trilinear L²(Rn) energy 〈Q(g,f),f〉. These new estimates prove that, for a very general class of g(v), the global diffusive behavior (on f) in the energy space is that of the geometric fractional derivative semi-norm identified in the linearized context in our earlier works (Gressman and Strain, 2010 [15], 2011 [16]). We further prove new global entropy production estimates with the same anisotropic semi-norm. This resolves the longstanding, widespread heuristic conjecture about the sharp diffusive nature of the non-cut-off Boltzmann collision operator in the energy space L²(Rn).     

On the Support Problem for Drinfeld Modules

Let Φ be a Drinfeld A-module over an A-field K of generic characteristic. We will prove the following two results which are analogous to ones in number fields. Case 1. Φ is of rank one. Suppose that P and Q are two nontorsion points in Φ(K). If for any element a ? A and almost all prime ideals 𝒫 in  one has that Φ _a (P) ≡ 0 (mod 𝒫) ? Φ _a (Q) ≡ 0 (mod 𝒫), then Q = Φ _m (P) for some m ? A. Case 2. Φ is of general rank ≥ 1. Let x, y ? Φ(K) be two K-rational points. Denote  = End _K (Φ) which is commutative and Λ =  · y which is a cyclic -module. Let red _v :Φ(K) → Φ(k _v ) be the reduction map at a place v of K with residue field k _v . If red _v (x) ? red _v (Λ) for almost all places v of K. Then f(x) = g(y), for some nonzero elements f and g in .     

The asymptotic number of labeled connected graphs with a given number of vertices and edges

Let c(n, q) be the number of connected labeled graphs with n vertices and q ≤ N = (2n ) edges. Let x = q/n and k = q ? n. We determine functions w_k ? 1. a(x) and φ(x) such that c(n, q) ? w_k(q^N)eⁿφ(x)+a(x) uniformly for all n and q ≥ n. If ? > 0 is fixed, n→ ∞ and 4q > (1 + ?)n log n, this formula simplifies to c(n, q) ? (N^q) exp(–ne^?2q/n). on the other hand, if k = o(n^1/2), this formula simplifies to c(n, n + k) ? 1/2 w_k (3/π)^1/2 (e/12k)^k/2nⁿ?^(3k?1)/2.