Some results on general quadratic reflected BSDEs driven by a continuous martingale

We study the well-posedness of general reflected BSDEs driven by a continuous martingale, when the coefficient f$f$ of the driver has at most quadratic growth in the control variable Z$Z$, with a bounded terminal condition and a lower obstacle which is bounded above. We obtain the basic results in this setting: comparison and uniqueness, existence, stability. For the comparison theorem and the special comparison theorem for reflected BSDEs (which allows one to compare the increasing processes of two solutions), we give intrinsic proofs which do not rely on the comparison theorem for standard BSDEs. This allows to obtain the special comparison theorem under minimal assumptions. We obtain existence by using the fixed point theorem and then a series of perturbations, first in the case where f$f$ is Lipschitz in the primary variable Y$Y$, and then in the case where f$f$ can have slightly-superlinear growth and the case where f$f$ is monotonous in Y$Y$ with arbitrary growth. We also obtain a local Lipschitz estimate in BMO$BMO$ for the martingale part of the solution.     

Second order backward stochastic differential equations under a monotonicity condition

In a recent paper, Soner, Touzi and Zhang (2012) [19] have introduced a notion of second order backward stochastic differential equations (2BSDEs), which are naturally linked to a class of fully non-linear PDEs. They proved existence and uniqueness for a generator which is uniformly Lipschitz in the variables y$y$ and z$z$. The aim of this paper is to extend these results to the case of a generator satisfying a monotonicity condition in y$y$. More precisely, we prove existence and uniqueness for 2BSDEs with a generator which is Lipschitz in z$z$ and uniformly continuous with linear growth in y$y$. Moreover, we emphasize throughout the paper the major difficulties and differences due to the 2BSDE framework.     

Weak convergence of censored and reflected stable processes

It is shown that if a sequence of open n$n$-sets _Dk$D_k$ increases to an open n$n$-set D$D$ then reflected stable processes in _Dk$D_k$ converge weakly to the reflected stable process in D$D$ for every starting point x$x$ in D$D$. The same result holds for censored α$\alpha$-stable processes for every x$x$ in D$D$ if D$D$ and _Dk$D_k$ satisfy the uniform Hardy inequality. Using the method in the proof of the above results, we also prove the weak convergence of reflected Brownian motions in unbounded domains.     

Strongly quasi-Hamiltonian-connected semicomplete multipartite digraphs

A semicomplete multipartite or semicomplete c$c$-partite digraph D$D$ is a biorientation of a c$c$-partite graph. A semicomplete multipartite digraph D$D$ is called strongly quasi-Hamiltonian-connected, if for any two distinct vertices x$x$ and y$y$ of D$D$, there is a path P$P$ from x$x$ to y$y$ such that P$P$ contains at least one vertex from each partite set of D$D$.     

Quadratic reflected BSDEs with unbounded obstacles

In this paper, we analyze a real-valued reflected backward stochastic differential equation (RBSDE) with an unbounded obstacle and an unbounded terminal condition when its generator f$f$ has quadratic growth in the z$z$-variable. In particular, we obtain existence, uniqueness, and stability results, and consider the optimal stopping for quadratic g$g$-evaluations. As an application of our results we analyze the obstacle problem for semi-linear parabolic PDEs in which the non-linearity appears as the square of the gradient. Finally, we prove a comparison theorem for these obstacle problems when the generator is concave in the z$z$-variable.     

On probabilistic results for the discrepancy of a hybrid-Monte Carlo sequence

In many applications it has been observed that hybrid-Monte Carlo sequences perform better than Monte Carlo and quasi-Monte Carlo sequences, especially in difficult problems. For a mixed s$s$-dimensional sequence m$m$, whose elements are vectors obtained by concatenating d$d$-dimensional vectors from a low-discrepancy sequence q$q$ with (s−d)$(s-d)$-dimensional random vectors, probabilistic upper bounds for its star discrepancy have been provided. In a paper of G. Ökten, B. Tuffin and V. Burago [G. Ökten, B. Tuffin, V. Burago, J. Complexity 22 (2006), 435–458] it was shown that for arbitrary ε>0$\epsilon >0$ the difference of the star discrepancies of the first N$N$ points of m$m$ and q$q$ is bounded by ε$\epsilon$ with probability at least 1−2exp(−ε²N/2)$1-2exp(-{\epsilon }^{2}N/2)$ for N$N$ sufficiently large. The authors did not study how large N$N$ actually has to be and if and how this actually depends on the parameters s$s$ and ε$\epsilon$. In this note we derive a lower bound for N$N$, which significantly depends on s$s$ and ε$\epsilon$. Furthermore, we provide a probabilistic bound for the difference of the star discrepancies of the first N$N$ points of m$m$ and q$q$, which holds without any restrictions on N$N$. In this sense it improves on the bound of Ökten, Tuffin and Burago and is more helpful in practice, especially for small sample sizes N$N$. We compare this bound to other known bounds.     

Tournaments associated with multigraphs and a theorem of Hakimi

A tournament of order n$n$ is usually considered as an orientation of the complete graph _Kn$K_n$. In this note, we consider a more general definition of a tournament that we call aC$C$-tournament, where C$C$ is the adjacency matrix of a multigraph G$G$, and a C$C$-tournament is an orientation of G$G$. The score vector of a C$C$-tournament is the vector of outdegrees of its vertices. In 1965 Hakimi obtained necessary and sufficient conditions for the existence of a C$C$-tournament with a prescribed score vector R$R$ and gave an algorithm to construct such a C$C$-tournament which required, however, some backtracking. We give a simpler and more transparent proof of Hakimi’s theorem, and then provide a direct construction of such a C$C$-tournament which works even for weighted graphs.     

Quandle cocycles from invariant theory

Let G$G$ be a group. Any G$G$-module M$M$ has an algebraic structure called a G$G$-family of Alexander quandles. Given a 2-cocycle of a cohomology associated with this G$G$-family, topological invariants of (handlebody) knots in the 3-sphere are defined. We develop a simple algorithm to algebraically construct n$n$-cocycles of this G$G$-family from G$G$-invariant group n$n$-cocycles of the abelian group M$M$. We present many examples of 2-cocycles of these G$G$-families using facts from (modular) invariant theory.     

On topological entropy of commuting tree maps

Let T$T$ be a tree with s$s$ ends and f,g$f,g$ be continuous maps from T$T$ to T$T$ with f°g=g°f$f°g=g°f$. In this note we show that if there exists a positive integer m≥2$m\ge 2$ such that gcd(m,l)=1$gcd(m,l)=1$ for any 2≤l≤s$2\le l\le s$ and f,g$f,g$ share a periodic point which is a km$km$-periodic point of f$f$ for some positive integer k$k$, then the topological entropy of f°g$f°g$ is positive.     

Revenue in contests with many participants

We show that in a contest with a single prize, the expected effort made by the k$k$th highest valuation participant bounds the sum of the expected efforts made by all of the participants with valuations less than the k$k$th highest valuations. We also show that in the limit case of a contest with m$m$ prizes, the expected effort made by the k$k$th highest valuation participant when the bidders are risk-neutral is greater than the expected effort in the risk-averse case.     

Disjoint cycles with different length in 4-arc-dominated digraphs

A d$d$-arc-dominated digraph is a digraph D$D$ of minimum out-degree d$d$ such that for every arc (x,y)$(x,y)$ of D$D$, there exists a vertex u$u$ of D$D$ of out-degree d$d$ such that (u,x)$(u,x)$ and (u,y)$(u,y)$ are arcs of D$D$. Henning and Yeo [Vertex disjoint cycles of different length in digraphs, SIAM J. Discrete Math. 26 (2012) 687–694] conjectured that a digraph with minimum out-degree at least four contains two vertex-disjoint cycles of different length. In this paper, we verify this conjecture for 4-arc-dominated digraphs.     

Cone-separation and star-shaped separability with applications

Let X$X$ be a (real) Banach space, A$A$ be a subset of X$X$ and x∉A$x\notin A$. We present cone-separation in terms of separation by a collection of linear functionals defined on X$X$ and obtain necessary and sufficient conditions for cone-separability A$A$ and x$x$. Also, we give characterizations for star-shaped separability. Finally, as an application of separability, we characterize best approximation problem by elements of star-shaped sets.     

Oscillation of harmonic functions for subordinate Brownian motion and its applications

In this paper, we establish an oscillation estimate of nonnegative harmonic functions for a pure-jump subordinate Brownian motion. The infinitesimal generator of such subordinate Brownian motion is an integro-differential operator. As an application, we give a probabilistic proof of the following form of relative Fatou theorem for such subordinate Brownian motion X$X$ in a bounded κ$\kappa$-fat open set; if u$u$ is a positive harmonic function with respect to X$X$ in a bounded κ$\kappa$-fat open set D$D$ and h$h$ is a positive harmonic function in D$D$ vanishing on D^c$D^c$, then the non-tangential limit of u/h$u/h$ exists almost everywhere with respect to the Martin-representing measure of h$h$.     

Fixed point theorem for generalized Φ -pseudocontractive mappings

Let E$E$ be a real Banach space, C$C$ be a nonempty closed convex subset of E$E$ and T:C→C$T:C\to C$ be a continuous generalized Φ$\Phi$-pseudocontractive mapping. It is proved that T$T$ has a unique fixed point in C$C$.     

Every point is critical

We show that, for any compact Alexandrov surface S$S$ (without boundary) and any point y$y$ in S$S$, there exists a point x$x$ in S$S$ for which y$y$ is a critical point. Moreover, we prove that uniqueness characterizes the surfaces homeomorphic to the sphere among smooth orientable surfaces.     

On prime ideals and radicals of polynomial rings and graded rings

We extend some known results on radicals and prime ideals from polynomial rings and Laurent polynomial rings to Z$\mathbb{Z}$-graded rings, i.e, rings graded by the additive group of integers. The main of them concerns the Brown–McCoy radical G$G$ and the radical S$S$, which for a given ring A$A$ is defined as the intersection of prime ideals I$I$ of A$A$ such that A/I$A/I$ is a ring with a large center. The studies are related to some open problems on the radicals G$G$ and S$S$ of polynomial rings and situated in the context of Koethe’s problem.     

On the complexity of the bondage and reinforcement problems

Let G=(V,E)$G=(V,E)$ be a graph. A subset D⊆V$D\subseteq V$ is a dominating set if every vertex not in D$D$ is adjacent to a vertex in D$D$. A dominating set D$D$ is called a total dominating set if every vertex in D$D$ is adjacent to a vertex in D$D$. The domination (resp. total domination) number of G$G$ is the smallest cardinality of a dominating (resp. total dominating) set of G$G$. The bondage (resp. total bondage) number of a nonempty graph G$G$ is the smallest number of edges whose removal from G$G$ results in a graph with larger domination (resp. total domination) number of G$G$. The reinforcement (resp. total reinforcement) number of G$G$ is the smallest number of edges whose addition to G$G$ results in a graph with smaller domination (resp. total domination) number. This paper shows that the decision problems for the bondage, total bondage, reinforcement and total reinforcement numbers are all NP-hard.     

Modules satisfying the weak Nakayama property

Let R$R$ be a commutative ring with identity. We will say that an R$R$-module M$M$ satisfies the weak Nakayama property, if IM=M$IM=M$, where I$I$ is an ideal of R$R$, implies that for any x∈M$x\in M$ there exists a∈I$a\in I$ such that (a−1)x=0$(a-1)x=0$. In this paper, we will study modules satisfying the weak Nakayama property. It is proved that if R$R$ is a local ring, then R$R$ is a Max ring if and only if J(R)$J\left(R\right)$, the Jacobson radical of R$R$, is T$T$-nilpotent if and only if every R$R$-module satisfies the weak Nakayama property.     

Sensitivity of Boolean formulas

The sensitivity set of a Boolean function at a particular input is the set of input positions where changing that one bit changes the output. Analogously we define the sensitivity set of a Boolean formula in a conjunctive normal form at a particular truth assignment, it is the set of positions where changing that one bit of the truth assignment changes the evaluation of at least one of the conjunct in the formula. We consider Boolean formulas in a generalized conjunctive normal form. Given a set ?$?$ of Boolean functions, an ?$?$-constraint is an application of a function from ?$?$ to a tuple of literals built upon distinct variables, an ?$?$-formula is then a conjunction of ?$?$-constraints. In this framework, given a truth assignment I$I$ and a set of positions S$S$, we are able to enumerate all ?$?$-formulas that are satisfied by I$I$ and that have S$S$ as the sensitivity set at I$I$. We prove that this number depends on the cardinality of S$S$ only, and can be expressed according to the sensitivity of the Boolean functions in ?$?$.