Improved bound on the oriented diameter of graphs with given minimum degree

In 2015, Bau and Dankelmann showed that every bridgeless graph $G$ of order $n$ and minimum degree $\delta$ has an orientation of diameter at most $11\frac{n}{\delta +1}+9$. As they were convinced that this bound is not best possible, they posed the problem of improving it.In this paper, we prove that such a graph $G$ has an orientation of diameter less than $7\frac{n}{\delta +1}$ and give a polynomial-time algorithm to construct one.     

A sharp bound on the expected number of upcrossings of an L2-bounded Martingale

For a martingale $M$ starting at $x$ with final variance ${\sigma }^2$, and an interval $(a,b)$, let $\Delta =\frac{b?a}{\sigma }$ be the normalized length of the interval and let $\delta =\frac{|x?a|}{\sigma }$ be the normalized distance from the initial point to the lower endpoint of the interval. The expected number of upcrossings of $(a,b)$ by $M$ is at most $\frac{\sqrt{1+{\delta }^2}?\delta }{2\Delta }$ if ${\Delta }^2\le 1+{\delta }^2$ and at most $\frac{1}{1+{(\Delta +\delta )}^2}$ otherwise. Both bounds are sharp, attained by Standard Brownian Motion stopped at appropriate stopping times. Both bounds also attain the Doob upper bound on the expected number of upcrossings of $(a,b)$ for submartingales with the corresponding final distribution. Each of these two bounds is at most $\frac{\sigma }{2(b?a)}$, with equality in the first bound for $\delta =0$. The upper bound $\frac{\sigma }{2}$ on the length covered by $M$ during upcrossings of an interval restricts the possible variability of a martingale in terms of its final variance. This is in the same spirit as the Dubins & Schwarz sharp upper bound $\sigma$ on the expected maximum of $M$ above $x$, the Dubins & Schwarz sharp upper bound $\sigma \sqrt{2}$ on the expected maximal distance of $M$ from $x$, and the Dubins, Gilat & Meilijson sharp upper bound $\sigma \sqrt{3}$ on the expected diameter of $M$.     

Primitive idempotents of irreducible cyclic codes and self-dual cyclic codes over Galois rings

Let $R$ be the Galois ring $GR(p^k,s)$ of characteristic $p^k$ and cardinality $p^{sk}$. Firstly, we give all primitive idempotent generators of irreducible cyclic codes of length $n$ over $R$, and a $p$-adic integer ring with $gcd(p,n)=1$. Secondly, we obtain all primitive idempotents of all irreducible cyclic codes of length $r{l}^m$ over $R$, where $r,l,$ and $t$ are three primes with $2?l$, $r|(q^t?1)$, $l^v\parallel (q^t?1)$ and $gcd(rl,q(q?1))=1$. Finally, as applications, weight distributions of all irreducible cyclic codes for $t=2$ and generator polynomials of self-dual cyclic codes of length $l^m$ and $r{l}^m$ over $R$ are given.     

Diameter of orientations of graphs with given minimum degree

We show that every bridgeless graph of order $n$ and minimum degree $\delta$ has a strongly connected orientation of diameter at most $\frac{11}{\delta +1}n+9$, and such an orientation can be found in polynomial time.     

A note on Bartholdi zeta function and graph invariants based on resistance distance

Let $G$ be a finite connected graph. In this note, we show that the complexity of $G$ can be obtained from the partial derivatives at $(1?\frac{1}{t},t)$ of a determinant in terms of the Bartholdi zeta function of $G$. Moreover, the second order partial derivatives at $(1?\frac{1}{t},t)$ of this determinant can all be expressed as the linear combination of the Kirchhoff index, the additive degree-Kirchhoff index, and the multiplicative degree-Kirchhoff index of the graph $G$.     

Boundary estimates in homogenization of systems of elasticity on Lipschitz domains: Lp theory

The primary purpose of this paper is to investigate a family of elliptic systems of linear elasticity with rapidly oscillating periodic coefficients, arising in the theory of homogenization in Lipschitz domains. As a consequence, for $d\ge 4$, we prove that the $L^p$ Neumann and $L^p$ Dirichlet boundary value problems for systems of second order linear elasticity are uniquely solvable for $\frac{2(d?1)}{d+1}?\delta <p<2+\delta$ and $2?\delta <p<\frac{2(d?1)}{d?3}+\delta$ respectively.     

Energy dissipation in the Smagorinsky model of turbulence

The Smagorinsky model often severely over-dissipates flows and, consistently, previous estimates of its energy dissipation rate blow up as $Re\to \infty$. This report estimates time averaged model dissipation, $〈{\epsilon }_S〉$, under periodic boundary conditions as$〈{\epsilon }_S〉\le 2\frac{U^3}{L}+{\mathrm{Re}}^{-1}\frac{U^3}{L}+\frac{32}{27}{C}_S^2{\left(\frac{\delta }{L}\right)}^2\frac{U^3}{L}\text{,}$ where $U,L$ are global velocity and length scales and $C_S\simeq 0.1,\delta <1$ are model parameters. Thus, in the absence of boundary layers, the Smagorinsky model does not over dissipate.     

Trees and languages with periodic signature

The signature of a labelled tree (and hence of its prefix-closed branch language) is the sequence of the degrees of the nodes of the tree in the breadth-first traversal. In a previous work, we have characterised the signatures of the regular languages. Here, the trees and languages that have the simplest possible signatures, namely the periodic ones, are characterised as the sets of representations of the integers in rational base numeration systems.For any pair of co-prime integers $p$ and $q$, $p>q>1$, the language  $L_{\frac{p}{q}}$ of representations of the integers in base  $\frac{p}{q}$ looks chaotic and does not fit in the classical Chomsky hierarchy of formal languages. On the other hand, the most basic example given by  $L_{\frac{3}{2}}$, the set of representations in base  $\frac{3}{2}$, exhibits a remarkable regularity: its signature is the infinite periodic sequence: $2,1,2,1,2,1,\dots$We first show that  $L_{\frac{p}{q}}$ has a periodic signature and the period (a sequence of $q$ integers whose sum is $p$) is directly derived from the Christoffel word of slope  $\frac{p}{q}$. Conversely, we give a canonical way to label a tree generated by any periodic signature; its branch language then proves to be the set of representations of the integers in a rational base (determined by the period) and written with a non-canonical alphabet of digits. This language is very much of the same kind as a  $L_{\frac{p}{q}}$ since rational base numeration systems have the key property that, even though  $L_{\frac{p}{q}}$ is not regular, normalisation is realised by a finite letter-to-letter transducer.     

Rough path properties for local time of symmetric α stable process

In this paper, we first prove that the local time associated with symmetric $\alpha$-stable processes is of bounded $p$-variation for any $p>\frac{2}{\alpha ?1}$ partly based on Barlow’s estimation of the modulus of the local time of such processes.  The fact that the local time is of bounded $p$-variation for any $p>\frac{2}{\alpha ?1}$ enables us to define the integral of the local time ${\int }_{?\infty }^{\infty }{?}_{?}^{\alpha ?1}f\left(x\right)d_x{L}_t^x$ as a Young integral for less smooth functions being of bounded $q$-variation with $1\le q<\frac{2}{3?\alpha }$. When $q\ge \frac{2}{3?\alpha }$, Young’s integration theory is no longer applicable. However, rough path theory is useful in this case. The main purpose of this paper is to establish a rough path theory for the integration with respect to the local times of symmetric $\alpha$-stable processes for $\frac{2}{3?\alpha }\le q<4$.