Global nonparametric estimation of conditional quantile functions and their derivatives

Let (X, Y) be a random vector such that X is d-dimensional, Y is real valued, and θ(X) is the conditional αth quantile of Y given X, where α is a fixed number such that 0 < α < 1. Assume that θ is a smooth function with order of smoothness p > 0, and set r = (p − m)/(2p + d), where m is a nonnegative integer smaller than p. Let T(θ) denote a derivative of θ of order m. It is proved that there exists estimate of T(θ), based on a set of i.i.d. observations (X₁, Y₁), …, (X_n, Y_n), that achieves the optimal nonparametric rate of convergence n^−r in L_q-norms (1 ≤ q < ∞) restricted to compacts under appropriate regularity conditions. Further, it has been shown that there exists estimate of T(θ) that achieves the optimal rate (n/log n)^−r in L_∞-norm restricted to compacts.     

Some cardinal invariants on the space

Let C_α(X,Y) be the set of all continuous functions from X to Y endowed with the set-open topology where α is a hereditarily closed, compact network on X such that closed under finite unions. We define two properties (E1) and (E2) on the triple (α,X,Y) which yield new equalities and inequalities between some cardinal invariants on C_α(X,Y) and some cardinal invariants on the spaces X, Y such as: Theorem If Y is an equiconnected space with a base consisting of φ-convex sets, then for each fC(X,Y), χ(f,C_α(X,Y))=αa(X).w_e(f(X)).Corollary Let Y be a noncompact metric space and let the triple (α,X,Y) satisfy (E1). The following are equivalent:

(i) C_α(X,Y) is a first-countable space.

(ii) π-character of the space C_α(X,Y) is countable.

(iii) C_α(X,Y) is of pointwise countable type.

(iv) There exists a compact subset K of C_α(X,Y) such that π-character of K in the space C_α(X,Y) is countable.

(v) αa(X)₀.

(vi) C_α(X,Y) is metrizable.

(vii) C_α(X,Y) is a q-space.

(viii) There exists a sequence of nonempty open subset of C_α(X,Y) such that each sequence with g_nO_n for each nω, has a cluster point in C_α(X,Y).

Vertex Set Partitions Preserving Conservativeness

Let G be an undirected graph and ={X₁, …, X_n} be a partition of V(G). Denote by G/ the graph which has vertex set {X₁, …, X_n}, edge set E, and is obtained from G by identifying vertices in each class X_i of the partition . Given a conservative graph (G, w), we study vertex set partitions preserving conservativeness, i.e., those for which (G/ , w) is also a conservative graph. We characterize the conservative graphs (G/ , w), where is a terminal partition of V(G) (a partition preserving conservativeness which is not a refinement of any other partition of this kind). We prove that many conservative graphs admit terminal partitions with some additional properties. The results obtained are then used in new unified short proofs for a co-NP characterization of Seymour graphs by A. A. Ageev, A. V. Kostochka, and Z. Szigeti (1997, J. Graph Theory34, 357–364), a theorem of E. Korach and M. Penn (1992, Math. Programming55, 183–191), a theorem of E. Korach (1994, J. Combin. Theory Ser. B62, 1–10), and a theorem of A. V. Kostochka (1994, in “Discrete Analysis and Operations Research. Mathematics and its Applications (A. D. Korshunov, Ed.), Vol. 355, pp. 109–123, Kluwer Academic, Dordrecht).     

An ergodic Markov chain is not determined by any p-marginals

We prove that if X = (X_n)_nεZ is a finite state space ergodic Markov chain, then for any natural number p, there exist ergodic non-Markovian processes Y = (Y_n)_nεZ with positive entropy, such that for all integers n₁, …, n_p, the joint distribution of Y_n1, …, Y_np is identical to the joint distribution of X_n1, …, X_np.     

On the transition from a Markov chain to a continuous time process

Starting from a real-valued Markov chain X₀,X₁,…,X_n with stationary transition probabilities, a random element {Y(t);t[0, 1]} of the function space D[0, 1] is constructed by letting Y(k/n)=X_k, k= 0,1,…,n, and assuming Y (t) constant in between. Sample tightness criteria for sequences {Y(t);t[0,1]};_n of such random elements in D[0, 1] are then given in terms of the one-step transition probabilities of the underlying Markov chains. Applications are made to Galton-Watson branching processes.     

Finite subgraphs of uncountably chromatic graphs

It is consistent that for every function f:ω → ω there is a graph with size and chromatic number ?₁ in which every n‐chromatic subgraph contains at least f(n) vertices (n ≥ 3). This solves a $ 250 problem of Erd?s. It is consistent that there is a graph X with Chr(X)=|X|=?₁ such that if Y is a graph all whose finite subgraphs occur in X then Chr(Y)≤?₂ (so the Taylor conjecture may fail). It is also consistent that if X is a graph with chromatic number at least ?₂ then for every cardinal λ there exists a graph Y with Chr(Y)≥λ all whose finite subgraphs are induced subgraphs of X. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 28–38, 2005     

Asymptotically optimal selection of a piecewise polynomial estimator of a regression function

Let (X, Y) be a pair of random variables such that X = (X₁,…, X_d) ranges over a nondegenerate compact d-dimensional interval C and Y is real-valued. Let the conditional distribution of Y given X have mean θ(X) and satisfy an appropriate moment condition. It is assumed that the distribution of X is absolutely continuous and its density is bounded away from zero and infinity on C. Without loss of generality let C be the unit cube. Consider an estimator of θ having the form of a piecewise polynomial of degree k_n based on m_n^d cubes of length 1/m_n, where the m_n^d(_d^k_n+d) coefficients are chosen by the method of least squares based on a random sample of size n from the distribution of (X, Y). Let (k_n, m_n) be chosen by the FPE procedure. It is shown that the indicated estimator has an asymptotically minimal squared error of prediction if θ is not of the form of piecewise polynomial.     

Acyclic graphoidal covers and path partitions in a graph

An acyclic graphoidal cover of a graph G is a collection ψ of paths in G such that every path in ψ has at least two vertices, every vertex of G is an internal vertex of at most one path in ψ and every edge of G is in exactly one path in ψ. The minimum cardinality of an acyclic graphoidal cover of G is called the acyclic graphoidal covering number of G and is denoted by η_a. A path partition of a graph G is a collection P of paths in G such that every edge of G is in exactly one path in P. The minimum cardinality of a path partition of G is called thepath partition number of G and is denoted by π. In this paper we determine η_a and π for several classes of graphs and obtain a characterization of all graphs with Δ 4 and η_a = Δ − 1. We also obtain a characterization of all graphs for which η_a = π.     

Consistency of a recursive nearest neighbor regression function estimate

Let (X, Y) be an ^d × -valued random vector and let (X₁, Y₁),…,(X_N, Y_N) be a random sample drawn from its distribution. Divide the data sequence into disjoint blocks of length l₁, …, l_n, find the nearest neighbor to X in each block and call the corresponding couple (X_i^*, Y_i^*). It is shown that the estimate m_n(X) = Σ_{i = 1}ⁿ w_niY_i^*/Σ_{i = 1}ⁿ w_ni of m(X) = E{Y|X} satisfies E{|m_n(X) − m(X)|^p} 0 (p ≥ 1) whenever E{|Y|^p} < ∞, l_n ∞, and the triangular array of positive weights {w_ni} satisfies sup_{i ≤ n}w_ni/Σ_{i = 1}ⁿ w_ni 0. No other restrictions are put on the distribution of (X, Y). Also, some distribution-free results for the strong convergence of E{|m_n(X) − m(X)|^p|X₁, Y₁,…, X_N, Y_N} to zero are included. Finally, an application to the discrimination problem is considered, and a discrimination rule is exhibited and shown to be strongly Bayes risk consistent for all distributions.     

Direct and Inverse Problems of Baire Classification of Integrals Depending on a Parameter

We study the problem of the Baire classification of integrals g (y) = (If)(y) = ∫ _X f(x, y)dμ(x), where y is a parameter that belongs to a topological space Y and f are separately continuous functions or functions similar to them. For a given function g, we consider the inverse problem of constructing a function f such that g = If. In particular, for compact spaces X and Y and a finite Borel measure μ on X, we prove the following result: In order that there exist a separately continuous function f : X × Y → ℝ such that g = If, it is necessary and sufficient that all restrictions g| _{Y n} of the function g: Y → ℝ be continuous for some closed covering { Y _n : n ∈ ℕ} of the space Y.__________Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 56, No. 11, pp. 1443–1457, November, 2004.     

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.     

The Terwilliger Algebra Associated with a Set of Vertices in a Distance-Regular Graph

Let Γ be a distance-regular graph of diameter D. Let X denote the vertex set of Γ and let Y be a nonempty subset of X. We define an algebra τ = τ(Y). This algebra is finite dimensional and semisimple. If Y consists of a single vertex then τ is the corresponding subconstituent algebra defined by P. Terwilliger. We investigate the irreducible τ-modules. We define endpoints and thin condition on irreducible τ-modules as a generalization of the case when Y consists of a single vertex. We determine when an irreducible module is thin. When the module is generated by the characteristic vector of Y, it is thin if and only if Y is a completely regular code of Γ. By considering a suitable subset Y, every irreducible τ(x)-module of endpoint i can be regarded as an irreducible τ(Y)-module of endpoint 0.This research was partially supported by the Grant-in-Aid for Scientific Research (No. 12640039), Japan Society of the Promotion of Science. A part of the research was done when the author was visiting the Ohio State University.     

A full-invariant theorem and some applications

Let (X,τ₁) and (Y,τ₂) be two Hausdorff locally convex spaces with continuous duals X′ and Y′, respectively, L(X,Y) be the space of all continuous linear operators from X into Y, K(X,Y) be the space of all compact operators of L(X,Y). Let WOT and UOT be the weak operator topology and uniform operator topology on K(X,Y), respectively. In this paper, we characterize a full-invariant property of K(X,Y); that is, if the sequence space λ has the signed-weak gliding hump property, then each λ-multiplier WOT-convergent series ∑_iT_i in K(X,Y) must be λ-multiplier convergent with respect to all topologies between WOT and UOT if and only if each continuous linear operator T :(X,τ₁)→(λ^β,σ(λ^β,λ)) is compact. It follows from this result that the converse of Kalton's Orlicz–Pettis theorem is also true.     

ContributionsGraph partitions with minimum degree constraints

Given a graph with n nodes and minimum degree δ, we give a polynomial time algorithm that constructs a partition of the nodes of the graph into two sets X and Y such that the sum of the minimum degrees in X and in Y is at least δ and the cardinalities of X and Y differ by at most δ(δ + 1 if n ≠ δ(mod 2)). The existence of such a partition was shown by Sheehan (1988).     

L1-optimal estimates for a regression type function in R

Let X₁, X₂, …, X_n be random vectors that take values in a compact set in R^d, d ≥ 1. Let Y₁, Y₂, …, Y_n be random variables (“the responses”) which conditionally on X₁ = x₁, …, X_n = x_n are independent with densities f(y | x_i, θ(x_i)), i = 1, …, n. Assuming that θ lives in a sup-norm compact space Θ_q,d of real valued functions, an optimal L₁-consistent estimator of θ is constructed via empirical measures. The rate of convergence of the estimator to the true parameter θ depends on Kolmogorov's entropy of Θ_q,d.     

Deconvolving a Density from Partially Contaminated Observations

We consider the problem of estimating a continuous bounded probability density function when independent data X₁, ..., X_n from the density are partially contaminated by measurement error. In particular, the observations Y₁, ..., Y_n are such that P(Y_j = X_j) = p and P(Y_j = X_j + ε_j) = 1 − p, where the errors ε_j are independent (of each other and of the X_j) and identically distributed from a known distribution. When p = 0 it is well known that deconvolution via kernel density estimators suffers from notoriously slow rates of convergence. For normally distributed ε_j the best possible rates are of logarithmic order pointwise and in mean square error. In this paper we demonstrate that for merely partially(0 < p <1) contaminated observations (where of course it is unknown which observations are contaminated and which are not) under mild conditions almost sure rates of order O(((log h⁻¹)/nh)^1/2) with h = h(n) = const(log n/n)^1/5 are achieved for convergence in L_∞-norm. This is equal to the optimal rate available in ordinary density estimation from direct uncontaminated observations (p = 1). A corresponding result is obtained for the mean integrated squared error.     

A Kernel Estimator of a Conditional Quantile

Let (X₁, Y₁), (X₂, Y₂), …, be two-dimensional random vectors which are independent and distributed as (X, Y). For 0<p<1, letξ(px) be the conditionalpth quantile ofYgivenX=x; that is,ξ(px)=inf{y : P(YyX=x)p}. We consider the problem of estimatingξ(px) from the data (X₁, Y₁), (X₂, Y₂), …, (X_n, Y_n). In this paper, a new kernel estimator ofξ(px) is proposed. The asymptotic normality and a law of the iterated logarithm are obtained.     

Constructions of infinite graphs with Ramsey property

For every infinite cardinal λ and 2 ≤ n < ω there is a directed graph D of size λ such that D does not contain directed circuits of length ≤n and if its vertices are colored with <λ colors, then there is a monochromatic directed circuit of length n + 1. For every infinite cardinal λ and finite graph X there is a λ-sized graph Y such that if the vertices of Y are colored with <λ colors, then there is a monochromatic induced copy of X. Further, Y does not contain larger cliques or shorter odd circuits than X. The constructions are using variants of Specker-type graphs.     

The Erd s-Sós conjecture for graphs of girth 5

We prove that every graph of girth at least 5 with minimum degree δ k/2 contains every tree with k edges, whose maximum degree does not exceed the maximum degree of the graph. An immediate consequence is that the famous Erd s-Sós Conjecture, saying that every graph of order n with more than n(k − 1)/2 edges contains every tree with k edges, is true for graphs of girth at least 5.     

Algorithms for graph partitioning on the planted partition model

The NP‐hard graph bisection problem is to partition the nodes of an undirected graph into two equal‐sized groups so as to minimize the number of edges that cross the partition. The more general graph l‐partition problem is to partition the nodes of an undirected graph into l equal‐sized groups so as to minimize the total number of edges that cross between groups. We present a simple, linear‐time algorithm for the graph l‐partition problem and we analyze it on a random “planted l‐partition” model. In this model, the n nodes of a graph are partitioned into l groups, each of size n/l; two nodes in the same group are connected by an edge with some probability p, and two nodes in different groups are connected by an edge with some probability r<p. We show that if p−r≥n^−1/2+ϵ for some constant ϵ, then the algorithm finds the optimal partition with probability 1− exp(−n^Θ(ε)). © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 116–140, 2001