Graph switching, 2-ranks,and graphical Hadamard matrices

We study the behavior of the 2-rank of the adjacency matrix of a graph under Seidel and Godsil–McKay switching, and apply the result to graphs coming from graphical Hadamard matrices of order $4^m$. Starting with graphs from known Hadamard matrices of order 64, we find (by computer) many Godsil–McKay switching sets that increase the 2-rank. Thus we find strongly regular graphs with parameters $(63,32,16,16)$, $(64,36,20,20)$, and $(64,28,12,12)$ for almost all feasible 2-ranks. In addition we work out the behavior of the 2-rank for a graph product related to the Kronecker product for Hadamard matrices, which enables us to find many graphical Hadamard matrices of order $4^m$ for which the number of related strongly regular graphs with different 2-ranks is unbounded as a function of $m$. The paper extends results from the article ‘Switched symplectic graphs and their 2-ranks’ by the first and the last author.     

Forcing clique immersions through chromatic number

Building on recent work of Dvořák and Yepremyan, we show that every simple graph of minimum degree $7t+7$ contains $K_t$ as an immersion and that every graph with chromatic number at least $3.54t+4$ contains $K_t$ as an immersion. We also show that every graph on $n$ vertices with no independent set of size three contains $K_{2\lfloor n∕5\rfloor }$ as an immersion.     

Equivalences among Z2s-linear Hadamard codes

The ${\mathbb{Z}}_{2^s}$-additive codes are subgroups of ${\mathbb{Z}}_{2^s}^n$, and can be seen as a generalization of linear codes over ${\mathbb{Z}}_2$ and ${\mathbb{Z}}_4$. A ${\mathbb{Z}}_{2^s}$-linear Hadamard code is a binary Hadamard code which is the Gray map image of a ${\mathbb{Z}}_{2^s}$-additive code. A partial classification of these codes by using the dimension of the kernel is known. In this paper, we establish that some ${\mathbb{Z}}_{2^s}$-linear Hadamard codes of length $2^t$ are equivalent, once $t$ is fixed. This allows us to improve the known upper bounds for the number of such nonequivalent codes. Moreover, up to $t=11$, this new upper bound coincides with a known lower bound (based on the rank and dimension of the kernel). Finally, when we focus on $s\in \{2,3\}$, the full classification of the ${\mathbb{Z}}_{2^s}$-linear Hadamard codes of length $2^t$ is established by giving the exact number of such codes.     

Constructions of optimal orthogonal arrays with repeated rows

We construct orthogonal arrays ${\mathsf{OA}}_{\lambda }(k,n)$ (of strength two) having a row that is repeated $m$ times, where $m$ is as large as possible. In particular, we consider OAs where the ratio $m∕\lambda$ is as large as possible; these OAs are termed optimal. We provide constructions of optimal OAs for any $k\ge n+1$, albeit with large $\lambda$. We also study basic OAs; these are optimal OAs in which $gcd(m,\lambda )=1$. We construct a basic OA with $n=2$ and $k=4t+1$, provided that a Hadamard matrix of order $8t+4$ exists. This completely solves the problem of constructing basic OAs with $n=2$, modulo the Hadamard matrix conjecture.     

Minimum degree condition for a graph to be knitted

For a positive integer $k$, a graph is $k$-knitted if for each subset $S$ of $k$ vertices, and every partition of $S$ into (disjoint) parts $S_1,\dots ,S_t$ for some $t\ge 1$, one can find disjoint connected subgraphs $C_1,\dots ,C_t$ such that $C_i$ contains $S_i$ for each $i\in \left[t\right]?\{1,2,\dots ,t\}$. In this article, we show that if the minimum degree of an $n$-vertex graph $G$ is at least $n∕2+k∕2?1$ when $n\ge 2k+3$, then $G$ is $k$-knitted. The minimum degree is sharp. As a corollary, we obtain that $k$-contraction-critical graphs are $?\frac{k}{8}?$-connected.     

Point partition numbers: Decomposable and indecomposable critical graphs

Graphs considered in this paper are finite, undirected and loopless, but we allow multiple edges. The point partition number ${\chi }_t(G)$ is the least integer k for which G admits a coloring with k colors such that each color class induces a $(t?1)$-degenerate subgraph of G. So ${\chi }_1$ is the chromatic number and ${\chi }_2$ is the point arboricity. The point partition number ${\chi }_t$ with $t\ge 1$ was introduced by Lick and White. A graph G is called ${\chi }_t$-critical if every proper subgraph H of G satisfies ${\chi }_t(H)<{\chi }_t(G)$. In this paper we prove that if G is a ${\chi }_t$-critical graph whose order satisfies $|G|\le 2{\chi }_t(G)?2$, then G can be obtained from two non-empty disjoint subgraphs $G_1$ and $G_2$ by adding t edges between any pair $u,v$ of vertices with $u\in V(G_1)$ and $v\in V(G_2)$. Based on this result we establish the minimum number of edges possible in a ${\chi }_t$-critical graph G of order n and with ${\chi }_t(G)=k$, provided that $n\le 2k?1$ and t is even. For $t=1$ the corresponding two results were obtained in 1963 by Tibor Gallai.     

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.     

Small time convergence of subordinators with regularly or slowly varying canonical measure

We consider subordinators $X_{\alpha }={\left(X_{\alpha }\left(t\right)\right)}_{t\ge 0}$ in the domain of attraction at 0 of a stable subordinator ${\left(S_{\alpha }\left(t\right)\right)}_{t\ge 0}$ (where $\alpha \in (0,1)$); thus, with the property that ${\overline{\Pi }}_{\alpha }$, the tail function of the canonical measure of $X_{\alpha }$, is regularly varying of index $?\alpha \in (?1,0)$ as $x\downarrow 0$. We also analyse the boundary case, $\alpha =0$, when ${\overline{\Pi }}_{\alpha }$ is slowly varying at 0. When $\alpha \in (0,1)$, we show that ${\left(t{\overline{\Pi }}_{\alpha }\left(X_{\alpha }\left(t\right)\right)\right)}^{?1}$ converges in distribution, as $t\downarrow 0$, to the random variable ${\left(S_{\alpha }\left(1\right)\right)}^{\alpha }$. This latter random variable, as a function of $\alpha$, converges in distribution as $\alpha \downarrow 0$ to the inverse of an exponential random variable. We prove these convergences, also generalised to functional versions (convergence in $\mathbb{D}[0,1]$), and to trimmed versions, whereby a fixed number of its largest jumps up to a specified time are subtracted from the process. The $\alpha =0$ case produces convergence to an extremal process constructed from ordered jumps of a Cauchy subordinator. Our results generalise random walk and stable process results of Darling, Cressie, Kasahara, Kotani and Watanabe.     

Statistical inference for Vasicek-type model driven by Hermite processes

Let $Z$ denote a Hermite process of order $q\ge 1$ and self-similarity parameter $H\in (\frac{1}{2},1)$. This process is $H$-self-similar, has stationary increments and exhibits long-range dependence. When $q=1$, it corresponds to the fractional Brownian motion, whereas it is not Gaussian as soon as $q?2$. In this paper, we deal with a Vasicek-type model driven by $Z$, of the form $d{X}_t=a(b?X_t)dt+d{Z}_t$. Here, $a>0$ and $b\in \mathbb{R}$ are considered as unknown drift parameters. We provide estimators for $a$ and $b$ based on continuous-time observations. For all possible values of $H$ and $q$, we prove strong consistency and we analyze the asymptotic fluctuations.     

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).     

Maximal sets of Hamilton cycles in Knr;λ1,λ2

Let $K\left(n^r;{\lambda }_1,{\lambda }_2\right)$ be the $r$-partite multigraph in which each part has size $n$, where two vertices in the same part or different parts are joined by exactly ${\lambda }_1$ edges or ${\lambda }_2$ edges, respectively. It is proved that there exists a maximal set of $t$ edge-disjoint Hamilton cycles in $K\left(n^r;{\lambda }_1,{\lambda }_2\right)$ for ${\lambda }_{2}n\lfloor \frac{r+3}{4}\rfloor \le t\le min\left\{\lfloor \frac{{\lambda }_2{n}^2(r-1)}{2}\rfloor ,\lfloor \frac{{\lambda }_1(n-1)+{\lambda }_{2}n(r-1)}{2}\rfloor \right\}$, the upper bound being best possible. The results proved make use of the method of amalgamations.     

Non parametric estimation of the diffusion coefficients of a diffusion with jumps

In this article, we consider a jump diffusion process ${\left(X_t\right)}_{t\ge 0}$, with drift function $b$, diffusion coefficient $\sigma$ and jump coefficient ${\xi }^2$. This process is observed at discrete times $t=0,\Delta ,\dots ,n\Delta$. The sampling interval $\Delta$ tends to 0 and the time interval $n\Delta$ tends to infinity. We assume that ${\left(X_t\right)}_{t\ge 0}$ is ergodic, strictly stationary and exponentially $\beta$-mixing. We use a penalized least-square approach to compute adaptive estimators of the functions ${\sigma }^2+{\xi }^2$ and ${\sigma }^2$. We provide bounds for the risks of the two estimators.     

On bifurcation of eigenvalues along convex symplectic paths

We consider a continuously differentiable curve $t?\gamma (t)$ in the space of $2n\times 2n$ real symplectic matrices, which is the solution of the following ODE:

$\frac{\mathrm{d}\gamma }{\mathrm{d}t}(t)=J_{2n}A(t)\gamma (t),\gamma (0)\in \mathrm{Sp}(2n,\mathbb{R}),$

where $J=J_{2n}\stackrel{\text{def}}{=}\left[\begin{array}{cc}\hfill 0\hfill & \hfill {\mathrm{Id}}_n\hfill \\ \hfill ?{\mathrm{Id}}_n\hfill & \hfill 0\hfill \end{array}\right]$ and $A:t?A(t)$ is a continuous path in the space of $2n\times 2n$ real matrices which are symmetric. Under a certain convexity assumption (which includes the particular case that $A(t)$ is strictly positive definite for all $t\in \mathbb{R}$), we investigate the dynamics of the eigenvalues of $\gamma (t)$ when t varies, which are closely related to the stability of such Hamiltonian dynamical systems. We rigorously prove the qualitative behavior of the branching of eigenvalues and explicitly give the first order asymptotics of the eigenvalues. This generalizes classical Krein–Lyubarskii theorem on the analytic bifurcation of the Floquet multipliers under a linear perturbation of the Hamiltonian. As a corollary, we give a rigorous proof of the following statement of Ekeland: $\{t\in \mathbb{R}:\gamma (t)\text{ has a Krein indefinite eigenvalue of modulus }1\}$ is a discrete set.     

A scaling analysis of a star network with logarithmic weights

The paper investigates the properties of a class of resource allocation algorithms for communication networks: if a node of this network has $L$ requests to transmit and is idle, it tries to access the channel at a rate proportional to $log(1+L)$. A stochastic model of such an algorithm is investigated in the case of the star network, in which $J$ nodes can transmit simultaneously, but interfere with a central node 0 in such a way that node 0 cannot transmit while one of the other nodes does. One studies the impact of the log policy on these $J+1$ interacting communication nodes. A fluid scaling analysis of the network is derived with the scaling parameter $N$ being the norm of the initial state. It is shown that the asymptotic fluid behavior of the system is a consequence of the evolution of the state of the network on a specific time scale $(N^t,t\in (0,1))$. The main result is that, on this time scale and under appropriate conditions, the state of a node with index $j\ge 1$ is of the order of $N^{a_j\left(t\right)}$, with $0\le a_j\left(t\right)<1$, where $t?a_j\left(t\right)$ is a piecewise linear function. Convergence results on the fluid time scale and a stability property are derived as a consequence of this study.     

Two disjoint shortest paths problem with non-negative edge length

In the two disjoint shortest paths problem ( 2-DSPP), the input is a graph (or a digraph) and its vertex pairs $(s_1,t_1)$ and $(s_2,t_2)$, and the objective is to find two vertex-disjoint paths $P_1$ and $P_2$ such that $P_i$ is a shortest path from $s_i$ to $t_i$ for $i=1,2$, if they exist. In this paper, we give a first polynomial-time algorithm for the undirected version of the 2-DSPP with an arbitrary non-negative edge length function.