On graphs determining links with maximal number of components via medial construction

Let G be a connected plane graph, D(G) be the corresponding link diagram via medial construction, and μ(D(G)) be the number of components of the link diagram D(G). In this paper, we first provide an elementary proof that μ(D(G))≤n(G)+1, where n(G) is the nullity of G. Then we lay emphasis on the extremal graphs, i.e. the graphs with μ(D(G))=n(G)+1. An algorithm is given firstly to judge whether a graph is extremal or not, then we prove that all extremal graphs can be obtained from K₁ by applying two graph operations repeatedly. We also present a dual characterization of extremal graphs and finally we provide a simple criterion on structures of bridgeless extremal graphs.     

RELATIVE WIDTH OF SMOOTH CLASSES OF MULTIVARIATE PERIODIC FUNCTIONS WITH RESTRICTIONS ON ITERATED LAPLACE DERIVATIVES IN THE L2-METRIC

For two subsets W and V of a Banach space X, let Kn(W, V, X) denote the relative Kolmogorov n-width of W relative to V defined by Kn (W, V, X) := inf sup Ln f∈W g∈V∩Ln inf ‖f-g‖x,where the infimum is taken over all n-dimensional linear subspaces Ln of X. Let W2(△r) denote the class of 2w-periodic functions f with d-variables satisfying ∫[-π,π]d |△rf(x)|2dx ≤ 1,while △r is the r-iterate of Laplace operator △. This article discusses the relative Kolmogorov n-width of W2(△r) relative to W2(△r) in Lq([-r, πr]d) (1 ≤ q ≤∞), and obtain its weak asymptotic result.     

Representations for the first associated q-classical orthogonal polynomials

Let {p_k(x; q)} be any system of the q-classical orthogonal polynomials, and let be the corresponding weight function, satisfying the q-difference equation D_q(σ)=τ, where σ and τ are polynomials of degree at most 2 and exactly 1, respectively. Further, let {p_k⁽¹⁾(x;q)} be associated polynomials of the polynomials {p_k(x; q)}. Explicit forms of the coefficients b_n,k and c_n,k in the expansions

are given in terms of basic hypergeometric functions. Here _k(x) equals x^k if σ⁺(0)=0, or (x;q)_k if σ⁺(1)=0, where σ⁺(x)σ(x)+(q−1)xτ(x). The most important representatives of those two classes are the families of little q-Jacobi and big q-Jacobi polynomials, respectively.Writing the second-order nonhomogeneous q-difference equation satisfied by p_n−1⁽¹⁾(x;q) in a special form, recurrence relations (in k) for b_n,k and c_n,k are obtained in terms of σ and τ.     

Uniform bound in the central limit theorem for Banach space valued dependent random variables

Let F be a Banach space with a sufficiently smooth norm. Let (X_i)_i≤n be a sequence in L_F², and T be a Gaussian random variable T which has the same covariance as X = Σ_i≤nX_i. Assume that there exists a constant G such that for s, δ≥0, we have P(sTs+δ)Gδ. (*) We then give explicit bounds of Δ(X) = sup_i|P(|X|≤t)−P(|T|≤t)| in terms of truncated moments of the variables X_i. These bounds hold under rather mild weak dependence conditions of the variables. We also construct a Gaussian random variable that violates (^*).     

Bounds on margin distributions in learning problems

Let be a probability space and let P_n be the empirical measure based on i.i.d. sample (X₁,…,X_n) from P. Let be a class of measurable real valued functions on For define F_f(t):=P{ft} and F_n,f(t):=P_n{ft}. Given γ(0,1], define _n,γ(δ):=1/(n^1−γ/2δ^γ). We show that if the L₂(P_n)-entropy of the class grows as ^−α for some α(0,2), then, for all and all δ(0,Δ_n), Δ_n=O(n^1/2),

and

where and c(σ)↓1 as σ↓0 (the above inequalities hold for any fixed σ(0,1] with a high probability). Also, define

Then for all

uniformly in and with probability 1 (for the above ratio is bounded away from 0 and from ∞). The results are motivated by recent developments in machine learning, where they are used to bound the generalization error of learning algorithms. We also prove some more general results of similar nature, show the sharpness of the conditions and discuss the applications in learning theory.     

Cyclic Difference Packing and Covering Arrays

Let n and k be positive integers. Let C_q be a cyclic group of order q. A cyclic difference packing (covering) array, or a CDPA(k, n; q) (CDCA(k, n; q)), is a k × n array (a_ij) with entries a_ij (0 ≤ i ≤ k−1, 0 ≤ j ≤ n−1) from C_q such that, for any two rows t and h (0 ≤ t < h ≤ k−1), every element of C_q occurs in the difference list at most (at least) once. When q is even, then n ≤ q−1 if a CDPA(k, n; q) with k ≥ 3 exists, and n ≥ q+1 if a CDCA(k, n; q) with k ≥ 3 exists. It is proved that a CDCA(4, q+1; q) exists for any even positive integers, and so does a CDPA(4, q−1; q) or a CDPA(4, q−2; q). The result is established, for the most part, by means of a result on cyclic difference matrices with one hole, which is of interest in its own right.     

On the number of queries necessary to identify a permutation

Let p and q be two permutations over {1, 2,…, n}. We denote by m(p, q) the number of integers i, 1 ≤ i ≤ n, such that p(i) = q(i). For each fixed permutation p, a query is a permutation q of the same size and the answer a(q) to this query is m(p, q). We investigate the problem of finding the minimum number of queries required to identify an unknown permutation p. A polynomial-time algorithm that identifies a permutation of size n by O(n · log₂n) queries is presented. The lower bound of this problem is also considered. It is proved that the problem of determining the size of the search space created by a given set of queries and answers is #P-complete. Since this counting problem is essential for the analysis of the lower bound, a complete analysis of the lower bound appears infeasible. We conjecture, based on some preliminary analysis, that the lower bound is Ω(n · log₂n).     

Minimum degree of minimal defect -extendable bipartite graphs

A near perfect matching is a matching saturating all but one vertex in a graph. If G is a connected graph and any n independent edges in G are contained in a near perfect matching, then G is said to be defect n-extendable. If for any edge e in a defect n-extendable graph G, G−e is not defect n-extendable, then G is minimal defect n-extendable. The minimum degree and the connectivity of a graph G are denoted by δ(G) and κ(G) respectively. In this paper, we study the minimum degree of minimal defect n-extendable bipartite graphs. We prove that a minimal defect 1-extendable bipartite graph G has δ(G)=1. Consider a minimal defect n-extendable bipartite graph G with n≥2, we show that if κ(G)=1, then δ(G)≤n+1 and if κ(G)≥2, then 2≤δ(G)=κ(G)≤n+1. In addition, graphs are also constructed showing that, in all cases but one, there exist graphs with minimum degree that satisfies the established bounds.     

On deviations between empirical and quantile processes for mixing random variables

Let {X_n} be a strictly stationary φ-mixing process with Σ_j=1^∞ φ^1/2(j) < ∞. It is shown in the paper that if X₁ is uniformly distributed on the unit interval, then, for any t [0, 1], |F_n⁻¹(t) − t + F_n(t) − t| = O(n^−3/4(log log n)^3/4) a.s. and sup_0≤t≤1 |F_n⁻¹(t) − t + F_n(t) − t| = (O(n^−3/4(log n)^1/2(log log n)^1/4) a.s., where F_n and F_n⁻¹(t) denote the sample distribution function and tth sample quantile, respectively. In case {X_n} is strong mixing with exponentially decaying mixing coefficients, it is shown that, for any t [0, 1], |F_n⁻¹(t) − t + F_n(t) − t| = O(n^−3/4(log n)^1/2(log log n)^3/4) a.s. and sup_0≤t≤1 |F_n⁻¹(t) − t + F_n(t) − t| = O(n^−3/4(log n)(log log n)^1/4) a.s. The results are further extended to general distributions, including some nonregular cases, when the underlying distribution function is not differentiable. The results for φ-mixing processes give the sharpest possible orders in view of the corresponding results of Kiefer for independent random variables.     

Block Primitive 2- (v, k, 1) Designs Admitting a Ree Simple Group

In this paper, we prove that if D is a 2- (v, k, 1) design withG  ≤  Aut(D) block primitive and soc (G)  =  ²G₂(q) then D is a Ree unital with parameters 2- (q³ +  1, q +  1, 1).     

Some extremal results in cochromatic and dichromatic theory

For a graph G, the cochromatic number of G, denoted z(G), is the least m for which there is a partition of the vertex set of G having order m. where each part induces a complete or empty graph. We show that if {G_n} is a family of graphs where G_n has o(n² log²(n)) edges, then z(G_n) = o(n). We turn our attention to dichromatic numbers. Given a digraph D, the dichromatic number of D is the minimum number of parts the vertex set of D must be partitioned into so that each part induces an acyclic digraph. Given an (undirected) graph G, the dichromatic number of G, denoted d(G), is the maximum dichromatic number of all orientations of G. Let m be an integer; by d(m) we mean the minimum size of all graphs G where d(G) = m. We show that d(m) = θ(m² ln²(m)).     

The greedy coloring is a bad probabilistic algorithm

Given a graph G and an ordering p of its vertices, denote by A(G, p) the number of colors used by the greedy coloring algorithm when applied to G with vertices ordered by p. Let , , Δ be positive constants. It is proved that for each n there is a graph G_n such that the chromatic number of G_n is at most n, but the probability that A(G_n, p) < (1 − )n/log₂ n for a randomly chosen ordering p is O(n^−Δ).     

Bounds for Covering Codes over Large Alphabets

Let K_q(n,R) denote the minimum number of codewords in any q-ary code of length n and covering radius R. We collect lower and upper bounds for K_q(n,R) where 6 ≤ q ≤ 21 and R ≤ 3. For q ≤ 10, we consider lengths n ≤ 10, and for q ≥ 11, we consider n ≤ 8. This extends earlier results, which have been tabulated for 2 ≤ q ≤ 5. We survey known bounds and obtain some new results as well, also for s-surjective codes, which are closely related to covering codes and utilized in some of the constructions.AMS Classification: 94B75, 94B25, 94B65Gerzson Kéri - Supported in part by the Hungarian National Research Fund, Grant No. OTKA-T029572.Patric R. J. Östergård - Supported in part by the Academy of Finland, Grants No. 100500 and No. 202315.     

Strong and weak convergence theorems for asymptotically nonexpansive mappings

Suppose K is a nonempty closed convex nonexpansive retract of a real uniformly convex Banach space E with P as a nonexpansive retraction. Let T :K→E be an asymptotically nonexpansive nonself-map with sequence {k_n}_n1[1,∞), limk_n=1, F(T):={xK: Tx=x}≠. Suppose {x_n}_n1 is generated iteratively by

where {α_n}_n1(0,1) is such that ε<1−α_n<1−ε for some ε>0. It is proved that (I−T) is demiclosed at 0. Moreover, if ∑_n1(k_n²−1)<∞ and T is completely continuous, strong convergence of {x_n} to some x^*F(T) is proved. If T is not assumed to be completely continuous but E also has a Fréchet differentiable norm, then weak convergence of {x_n} to some x^*F(T) is obtained.     

Diameters of finite upper half plane graphs

Let GF(q) be a finite field of q elements. Let G denote the group of matrices M(x, y) = (^{y x}_{0 1}) over GF(q) with y ≠ 0. Fix an irreducible polynomial For each a ϵ GF(q), let X_a be the graph whose vertices are the q² − q elements of G, with two vertices M(x, y), M(v, w) joined by an edge if and only if The graphs X_a with a ϵ/ {0, t² − 4n} are (q + 1)-regular connected graphs which have received recent attention, as they've been shown to be Ramanujan graphs. We determine the diameter of these graphs X_a. © 1996 John Wiley & Sons, Inc.     

Permanence and global stability in a Lotka-Volterra predator-prey system with delays

Consider the permanence and global asymptotic stability of models governed by the following Lotka-Volterra-type system:

, with initial conditions

x_i(t) = φ_i(t) ≥ o, t ≤ t₀, and φ_i(t₀) > 0. 1 ≤ i ≤n

. We define x₀(t) = x_n+1(t)≡0 and suppose that φ_i(t), 1 ≤ i ≤ n, are bounded continuous functions on [t₀, + ∞) and γ_i, α_i, c_i > 0,γ_i,j ≥ 0, for all relevant i,j.Extending a technique of Saito, Hara and Ma[1] for n = 2 to the above system for n ≥ 2, we offer sufficient conditions for permanence and global asymptotic stability of the solutions which improve the well-known result of Gopalsamy.     

Rates of convergence for classes of functions: The non-i.i.d. case

Let X_i, i ≥ 1, be a sequence of φ-mixing random variables with values in a sample space (X, A). Let L(X_i) = P_(i) for all i ≥ 1 and let _n, n ≥ 1, be classes of real-valued measurable functions on (X, A). Given any function g on (X, A), let S_n(g) = Σ_{i = 1}ⁿ {g(X_i) − Eg(X_i)}. Under weak metric entropy conditions on _n and under growth conditions on both the mixing coefficients and the maximal variance V V(n) max_{i ≤ n} sup_{g n} ∫ g² dP_(i), we show that there is a numerical constant U < ∞ such that

Full-size image

a.s. ^*, where _{i = 1}^xP_(i) and H H(n) is the square root of the entropy of the class _n. Additionally, the rate of convergence H⁻¹(n/V)^1/2 cannot, in general, be improved upon. Applications of this result are considered.     

Second-order linearity of the general signed-rank statistic

Let X₁,…, X_n be i.i.d. random variables symmetric about zero. Let R_i(t) be the rank of |X_i − tn^−1/2| among |X₁ − tn^−1/2|,…, |X_n − tn^−1/2| and T_n(t) = Σ_{i = 1}ⁿφ((n + 1)⁻¹R_i(t))sign(X_i − tn^−1/2). We show that there exists a sequence of random variables V_n such that sup_{0 ≤ t ≤ 1} |T_n(t) − T_n(0) − tV_n| → 0 in probability, as n → ∞. V_n is asymptotically normal.     

Error bounds for least squares approximation by polynomials

Let f ε Cⁿ⁺¹[−1, 1] and let H[f](x) be the nth degree weighted least squares polynomial approximation to f with respect to the orthonormal polynomials q_k associated with a distribution dα on [−1, 1]. It is shown that if q_n+1/q_n max(q_n+1(1)/q_n(1), −q_n+1(−1)/q_n(−1)), then f − H[f] f^{n + 1} · q_n+1/q_{n + 1}^{(n + 1)}, where · denotes the supremum norm. Furthermore, it is shown that in the case of Jacobi polynomials with distribution (1 − t)^α (1 + t)^β dt, α, β > −1, the condition on q_n+1/q_n is satisfied when either max(α,β) −1/2 or −1 < α = β < −1/2.