Learning from MOM’s principles: Le Cam’s approach

New robust estimators are introduced, derived from median-of-means principle and Le Cam’s aggregation of tests. Minimax sparse rates of convergence are obtained with exponential probability, under weak moment’s assumptions and possible contamination of the dataset. These derive from general risk bounds of the following informal structure $max\left(\text{minimax rate in the i.i.d. setup},\frac{\text{number of outliers}}{\text{number of observations}}\right).$In this result, the number of outliers may be as large as (number of data)$\times$(minimax rate) without affecting the rates. As an example, minimax rates $slog(ed∕s)∕N$ of recovery of $s$-sparse vectors in ${\mathbb{R}}^d$ holding with exponentially large probability, are deduced for median-of-means versions of the LASSO when the noise has $q_0$ moments for some $q_0>2$, the entries of the design matrix have $C_{0}log\left(ed\right)$ moments and the dataset is corrupted by up to $C_{1}slog(ed∕s)$ outliers.     

Common values of a class of linear recurrences

Let $\left(a_n\right),\left(b_n\right)$ be linear recursive sequences of integers with characteristic polynomials $A\left(X\right),B\left(X\right)\in \mathbb{Z}\left[X\right]$ respectively. Assume that $A\left(X\right)$ has a dominating and simple real root $\alpha$, while $B\left(X\right)$ has a pair of conjugate complex dominating and simple roots $\beta ,\stackrel{?}{\beta }$. Assume further that $\alpha ,\beta ,\alpha /\beta$ and $\stackrel{?}{\beta }/\beta$ are not roots of unity and $\delta =log\left|\beta \right|/log\left|\alpha \right|\in \mathbb{Q}$. Then there are effectively computable constants $c_0,c_1>0$ such that the inequality $|a_n?b_m|>{\left|a_n\right|}^{1?\left(c_0{log}^{2}n\right)/n}$holds for all $n,m\in {\mathbb{Z}}_{\ge 0}^2$ with $max\{n,m\}>c_1$. We present $c_0$ explicitly.     

On the nonexistence of pseudo-generalized quadrangles

In this paper, we consider the question of when a strongly regular graph with parameters $((s+1)(st+1),s(t+1),s-1,t+1)$ can exist. A strongly regular graph with such parameters is called a pseudo-generalized quadrangle. A pseudo-generalized quadrangle can be derived from a generalized quadrangle, but there are other examples which do not arise in this manner. If the graph is derived from a generalized quadrangle then $t\le s^2$ and $s\le t^2$, while for pseudo-generalized quadrangles we still have the former bound but not the latter. Previously, Neumaier has proved a bound for $s$ which is cubic in $t$, but we improve this to one which is quadratic. The proof involves a careful analysis of cliques and cocliques in the graph. This improved bound eliminates many potential parameter sets which were otherwise feasible.     

Nonlinear stochastic time-fractional slow and fast diffusion equations on Rd

This paper studies the nonlinear stochastic partial differential equation of fractional orders both in space and time variables: $\left({?}^{\beta }+\frac{\nu }{2}{(?\Delta )}^{\alpha ∕2}\right)u(t,x)=I_t^{\gamma }\left[\rho \left(u(t,x)\right)\stackrel{?}{W}(t,x)\right],t>0,x\in {\mathbb{R}}^d,$where $\stackrel{?}{W}$ is the space–time white noise, $\alpha \in (0,2]$, $\beta \in (0,2)$, $\gamma \ge 0$ and $\nu >0$. Fundamental solutions and their properties, in particular the nonnegativity, are derived. The existence and uniqueness of solution together with the moment bounds of the solution are obtained under Dalang’s condition: $d<2\alpha +\frac{\alpha }{\beta }min(2\gamma ?1,0)$. In some cases, the initial data can be measures. When $\beta \in (0,1]$, we prove the sample path regularity of the solution.     

Erdős–Gallai stability theorem for linear forests

The Erd?s–Gallai Theorem states that every graph of average degree more than $l?2$ contains a path of order $l$ for $l\ge 2$. In this paper, we obtain a stability version of the Erd?s–Gallai Theorem in terms of minimum degree. Let $G$ be a connected graph of order $n$ and $F=\left({?}_{i=1}^k{P}_{2a_i}\right)?\left({?}_{i=1}^l{P}_{2b_i+1}\right)$ be $k+l$ disjoint paths of order $2a_1,\dots ,2a_k,2b_1+1,\dots ,2b_l+1,$ respectively, where $k\ge 0$, $0\le l\le 2$, and $k+l\ge 2$. If the minimum degree $\delta \left(G\right)\ge {\sum }_{i=1}^k{a}_i+{\sum }_{i=1}^l{b}_i?1$, then $F?G$ except several classes of graphs for sufficiently large $n$, which extends and strengths the results of Ali and Staton for an even path and Yuan and Nikiforov for an odd path.     

Bijections between t-core partitions and t-tuples

This note introduces some bijections relating core partitions and tuples of integers. We apply these bijections to count the number of cores with various types of restriction, including fixed number of parts, limited size of parts, parts divisible by some integer, and distinct parts. For example, we prove that the number of $2t$-core partitions into $l$ even parts equals the number of $t$-core partitions into $l$ parts. We also generalize one expression for simultaneous cores, which was given by Baek, Nam and Yu, recently. Subsequently, we use this expression to obtain recurrence satisfied by numbers of $(s,s+1,\dots ,s+r)-$core partitions for $s\ge 1$.     

Properties of G-martingales with finite variation and the application to G-Sobolev spaces

As is known, if $B={\left(B_t\right)}_{t\in [0,T]}$ is a $G$-Brownian motion, a process of form ${\int }_0^t{\eta }_{s}d{〈B〉}_s?{\int }_0^{t}2G\left({\eta }_s\right)ds$, $\eta \in M_G^1(0,T)$, is a non-increasing $G$-martingale. In this paper, we shall show that a non-increasing $G$-martingale cannot be form of ${\int }_0^t{\eta }_{s}ds$ or ${\int }_0^t{\gamma }_{s}d{〈B〉}_s$, $\eta ,\gamma \in M_G^1(0,T)$, which implies that the decomposition for generalized $G$-Itô processes is unique: For arbitrary $\zeta \in H_G^1(0,T)$, $\eta \in M_G^1(0,T)$ and non-increasing $G$-martingales $K,L$, if ${\int }_0^t{\zeta }_{s}d{B}_s+{\int }_0^t{\eta }_{s}ds+K_t=L_t,t\in [0,T],$then we have $\eta \equiv 0$, $\zeta \equiv 0$ and$K_t=L_t$. As an application, we give a characterization to the $G$-Sobolev spaces introduced in Peng and Song (2015).     

Greedy metric minimum online matchings with random arrivals

We consider online metric minimum bipartite matching problems with random arrival order and show that the greedy algorithm assigning each request to the nearest unmatched server is $n$-competitive, where $n$ is the number of requests. This result is complemented by a lower bound exhibiting that the greedy algorithm has a competitive ratio of at least $n^{(ln3?ln2)∕ln4}\approx n^{0.292}$, even when the underlying metric space is the real line.     

Turán numbers for Berge-hypergraphs and related extremal problems

Let $F$ be a graph. We say that a hypergraph $H$ is a Berge-$F$ if there is a bijection $f:E\left(F\right)\to E\left(H\right)$ such that $e?f\left(e\right)$ for every $e\in E\left(F\right)$. Note that Berge-$F$ actually denotes a class of hypergraphs. The maximum number of edges in an $n$-vertex $r$-graph with no subhypergraph isomorphic to any Berge-$F$ is denoted ${\mathrm{ex}}_r(n,\text{Berge-}F)$. In this paper, we investigate the case when $F=K_{s,t}$ and establish an upper-bound when $r\ge 3$, and a lower-bound when $r=4$ and $t$ is large enough compared to $s$. Additionally, we prove a counting result for $r$-graphs of girth five that complements the asymptotic formula ${\text{ex}}_3(n,\text{Berge-}\{C_2,C_3,C_4\})=\frac{1}{6}{n}^{3∕2}+o\left(n^{3∕2}\right)$ of Lazebnik and Verstraëte (2003).