Superharmonic extensions,mean values and Riesz measures

There are two interrelated themes to this paper. One is the generalization of recent harmonic and superharmonic extension theorems to the case where the removable set is not relatively closed, with the simultaneous weakening of other hypotheses in the harmonic case. The other is the use of results which are well-known in geometric measure theory, to prove theorems on the relative behaviour of the spherical mean values of a -subharmonic and a superharmonic function, and to establish new criteria for harmonic and superharmonic extensions. Some related theorems establish sufficient conditions for a polar set to be positive for the Riesz measure of a -subharmonic function, a useful formula for the restriction of such a measure to the infinity set of a superharmonic function, and a condition for such a restriction to be absolutely continuous with respect to an appropriate Hausdorff measure.     

An introduction to the k-defect polynomials

The 0-defect polynomial of a graph is just the chromatic polynomial. This polynomial has been widely studied in the literature. Yet little is known about the properties of k-defect polynomials of graphs in general, when 0 < k ≤ |E(G)|. In this survey we give some properties of k-defect polynomials, in particular we highlight the properties of chromatic polynomials which also apply to k-defect polynomials. We discuss further research which can be done on the k-defect polynomials.     

Sur le comportement asymptotique des potentiels d'une chaîne de Markov sur ℝ d

Résumé Dans cet article j'étudie le comportement à l'infini des potentiels des chaînes de Markov sur ^d (d3) proches du mouvement brownien, tout spécialement le cas des marches aléatoires, ainsi que des critères de transience et de récurrence inspirés de la méthode utilisée.

---

We study the asymptotic behaviour of potentials of Markov chains on ^d (d3), closed to Brownian motion, and particularly the case of random walks. Following a similar approach, we give transience and recurrence criteria.

     

Graph factors

This exposition is concerned with the main theorems of graph-factor theory, Hall’s and Ore’s Theorems in the bipartite case, and in the general case Petersen’s Theorem, the 1-Factor Theorem and thef-Factor Theorem. Some published extensions of these theorems are discussed and are shown to be consequences rather than generalizations of thef-Factor Theorem. The bipartite case is dealt with in Section 2. For the proper presentation of the general case a preliminary theory of “G-triples” and “f-barriers” is needed, and this is set out in the next three Sections. Thef-Factor Theorem is then proved by an argument of T. Gallai in a generalized form. Gallai’s original proof derives the 1-Factor Theorem from Hall’s Theorem. The generalization proceeds analogously from Ore’s Theorem to thef-Factor Theorem.     

Lipschitz continuity of Cheeger-harmonic functions in metric measure spaces

We use the heat equation to establish the Lipschitz continuity of Cheeger-harmonic functions in certain metric spaces. The metric spaces under consideration are those that are endowed with a doubling measure supporting a (1,2)-Poincaré inequality and in addition supporting a corresponding Sobolev-Poincaré-type inequality for the modification of the measure obtained via the heat kernel. Examples are given to illustrate the necessity of our assumptions on these spaces. We also provide an example to show that in the general setting the best possible regularity for the Cheeger-harmonic functions is Lipschitz continuity.     

Extremal problems,partition theorems,symmetric hypergraphs

We compare extremal theorems such as Turán’s theorem with their corresponding partition theorems such as Ramsey’s theorem. We derive a general inequality involving chromatic number and independence number of symmetric hypergraphs. We give applications to Ramsey numbers and to van der Waerden numbers.     

Martin compactification for discrete potential theory and the mean value property

A converse of the well-known theorem on themean value property of harmonic functions is given. It is shown that a positive measurable function is harmonic if it possesses arestricted mean value property. Earlier proofs obtained using the probabilistic techniques were given by Veech, Heath and Baxter. Our approach is based on a Martin type compactification built up with the help of some quite elementarya priori inequalities foraveraging kernels.     

Linearity of grid minors in treewidth with applications through bidimensionality

We prove that any H-minor-free graph, for a fixed graph H, of treewidth w has an Ω(w) × Ω(w) grid graph as a minor. Thus grid minors suffice to certify that H-minorfree graphs have large treewidth, up to constant factors. This strong relationship was previously known for the special cases of planar graphs and bounded-genus graphs, and is known not to hold for general graphs. The approach of this paper can be viewed more generally as a framework for extending combinatorial results on planar graphs to hold on H-minor-free graphs for any fixed H. Our result has many combinatorial consequences on bidimensionality theory, parameter-treewidth bounds, separator theorems, and bounded local treewidth; each of these combinatorial results has several algorithmic consequences including subexponential fixed-parameter algorithms and approximation algorithms. A preliminary version of this paper appeared in the ACM-SIAM Symposium on Discrete Algorithms (SODA 2005) [16].     

Sparse ramsey graphs

IfH is a Ramsey graph for a graphG thenH is rich in copies of the graphG. Here we prove theorems in the opposite direction. We find examples ofH such that copies ofG do not form short cycles inH. This provides a strenghtening also, of the following well-known result of Erdős: there exist graphs with high chromatic number and no short cycles. In particular, we solve a problem of J. Spencer. Dedicated to Paul Erdős on his seventieth birthday     

Laplacians and the Cheeger Inequality for Directed Graphs

We consider Laplacians for directed graphs and examine their eigenvalues. We introduce a notion of a circulation in a directed graph and its connection with the Rayleigh quotient. We then define a Cheeger constant and establish the Cheeger inequality for directed graphs. These relations can be used to deal with various problems that often arise in the study of non-reversible Markov chains including bounding the rate of convergence and deriving comparison theorems.Received September 8, 2004     

On switching paths polyhedra

A class of integer polyhedra with totally dual integral (tdi) systems is proposed, which generalizes and unifies the “Switching Paths Polyhedra” of Hoffman (introduced in his generalization of Max Flow-Min Cut) and such polyhedra as the convex hull of (the incidence vectors of) all “path-closed sets” of an acyclic digraph, or the convex hull of all sets partitionable intok path-closed sets. As an application, new min-max theorems concerning the mentioned sets are given. A general lemma on when a tdi system of inequalities is box tdi is also given and used.     

On the convergence of type I Hermite–Padé approximants

Padé approximation has two natural extensions to vector rational approximation through the so-called type I and type II Hermite–Padé approximants. The convergence properties of type II Hermite–Padé approximants have been studied. For such approximants Markov and Stieltjes type theorems are available. To the present, such results have not been obtained for type I approximants. In this paper, we provide Markov and Stieltjes type theorems on the convergence of type I Hermite–Padé approximants for Nikishin systems of functions.     

Nonlinear Markov operators associated with symmetric Markov kernels and energy minimizing maps between singular spaces

We present a theory of harmonic maps where the target is a complete geodesic space (N,d) of nonpositive curvature in the sense of A. D. Alexandrov and the domain is a measure space with a symmetric Markov kernel p on it. Our theory is a nonlinear generalization of the theory of symmetric Markov kernels and reversible Markov chains on M. It can also be regarded as a particular case of the theory of generalized (= nonlinear) Dirichlet forms and energy minimizing maps between singular spaces, initiated by Jost (1994) and Korevaar, Schoen (1993) and developed further by Jost (1997a), (1998) and Sturm (1997). We investigate the discrete and continuous time heat flow generated by p and show that various properties of the linear heat flow carry over to this nonlinear heat flow. In particular, we study harmonic maps, i.e. maps which are invariant under the heat flow. These maps are identified with the minimizers of the energy. Received April 2, 2000 / Accepted May 9, 2000 /Published online November 9, 2000     

Effilement minimal en une singularité isolée de l'équation de Schrödinger et application au principe de Picard

In this paper, the generalized Schrödinger equation (–)u=0 on the punctured unit disk of ² is investigated. If is rotation free and satisfies the Picard principle at the origin, it is shown that if a setE is minimal thin relatively to an extremal harmonic functionh with zero boundary values at {|x|=1}, there exists a sequence (r _n ) converging to zero such that B(O,r _n ) C E. Lete be the -unit. It is proved that if a measure satisfies _\E e h d<, for a minimal thin, relatively toh , setE then the Picard principle is valid for the measure + .

     

Fonctions finement harmoniques et l'axiome de domination

In a harmonic space with the domination Axiom (axiom D), B. Fuglede [5] has introduced the sheaf property of the cones of the finely hyperharmonic functions (defined in the fine opens). In [7], [8], J. Luke, J. Malý and L. Zajíek have studied a notion analogous to the finely hyperharmonic functions without supposing axiom D, and have proved ([8] theorem 12.16) that if the cones of the positive finely hyperharmonic functions make a sheaf, then axiom D is satisfied. See N. Boboc, Gh. Bucur and A. Cornea [3] for the first result of this type given within the context of theH-cones.In this paper, we prove axiom D is a consequence of the sheaf property even for the smallest class of the functions (the class of the finely harmonic functions; absolute-value bounded in a convenient sense). This result implies that of Lukeet al. cited above. Consequently, the tow fine properties of the sheaf are equivalent, which has not been evident previously.

     

Markov processes associated with L p -resolvents and applications to stochastic differential equations on Hilbert space

We give general conditions on a generator of a C₀-semigroup (resp. of a C₀-resolvent) on L^p(E,μ), p ≥ 1, where E is an arbitrary (Lusin) topological space and μ a σ-finite measure on its Borel σ-algebra, so that it generates a sufficiently regular Markov process on E. We present a general method how these conditions can be checked in many situations. Applications to solve stochastic differential equations on Hilbert space in the sense of a martingale problem are given. Dedicated to Giuseppe Da Prato on the occasion of his 70th birthday     

Some properties of the riesz charge associated with a δ-subharmonic function

The first property is a refinement of earlier results of Ch. de la Vallée Poussin, M. Brelot, and A. F. Grishin. Let w=u–v with u, v superharmonic on a suitable harmonic space (for example an open subset of R ⁿ ), and let [w]=[u]–[v] denote the associated Riesz charge. If w0, and if E denotes the set of those points of at which the lim inf of w in thefine topology is 0, then the restriction of [w] to E is 0. Another property states that, if e denotes a polar subset of such that the fine lim inf of |w| at each point of e is finite, then the restriction of [w] to e is 0.     

Heat kernel estimates for jump processes of mixed types on metric measure spaces

In this paper, we investigate symmetric jump-type processes on a class of metric measure spaces with jumping intensities comparable to radially symmetric functions on the spaces. The class of metric measure spaces includes the Alfors d-regular sets, which is a class of fractal sets that contains geometrically self-similar sets. A typical example of our jump-type processes is the symmetric jump process with jumping intensity where ν is a probability measure on , c(α, x, y) is a jointly measurable function that is symmetric in (x, y) and is bounded between two positive constants, and c ₀(x, y) is a jointly measurable function that is symmetric in (x, y) and is bounded between γ₁ and γ₂, where either γ₂ ≥ γ₁ > 0 or γ₁ = γ₂ = 0. This example contains mixed symmetric stable processes on as well as mixed relativistic symmetric stable processes on . We establish parabolic Harnack principle and derive sharp two-sided heat kernel estimate for such jump-type processes. Dedicated to Professor Masatoshi Fukushima on the occasion of his 70th birthday. The research of Zhen-Qing Chen is supported in part by NSF Grants DMS-0303310 and DMS-06000206. The research of Takashi Kumagai is supported in part by the Grant-in-Aid for Scientific Research (B) 18340027.     

The ergodic theory of Markov chains in random environments

Summary A general formulation of the stochastic model for a Markov chain in a random environment is given, including an analysis of the dependence relations between the environmental process and the controlled Markov chain, in particular the problem of feedback. Assuming stationary environments, the ergodic theory of Markov processes is applied to give conditions for the existence of finite invariant measure (equilibrium distributions) and to obtain ergodic theorems, which provide results on convergence of products of random stochastic matrices. Coupling theory is used to obtain results on direct convergence of these products and the structure of the tail -field. State properties including classification and communication properties are discussed.     

Construction of Markov processes and associated multiplicative functionals from given harmonic measures

Summary LetE be a noncompact locally compact second countable Hausdorff space. We consider the question when, given a family of finite nonzero measures onE that behave like harmonic measures associated with all relatively compact open sets inE (i.e. that satisfy a certain consistency condition), one can construct a Markov process onE and a multiplicative functional with values in [0, ) such that the hitting distributions of the process inflated by the multiplicative functional yield the given harmonic measures. We achieve this construction under weak continuity and local transience conditions on these measures that are natural in the theory of Markov processes, and a mild growth restriction on them. In particular, if the spaceE equipped with the measures satisfies the conditions of a harmonic space, such a Markov process and associated multiplicative functional exist. The result extends in a new direction the work of many authors, in probability and in axiomatic potential theory, on constructing Markov processes from given hitting distributions (i.e. from harmonic measures that have total mass no more than 1).