The dichromatic number $\vec{\chi}(G)$ of a digraph $G$ is the least integer $k$ such that $G$ can be partitioned into $k$ acyclic digraphs. A digraph is $k$-dicritical if $\vec{\chi}(G) = k$ and each proper subgraph $H$ of $G$ satisfies $\vec{\chi}(H) \leq k-1$. %An oriented graph is a digraph with no cycle of length $2$. We prove various bounds on the minimum number of arcs in a $k$-dicritical digraph, a structural result on $k$-dicritical digraphs and a result on list-dicolouring. We characterise $3$-dicritical digraphs $G$ with $(k-1)|V(G)| + 1$ arcs. For $k \geq 4$, we characterise $k$-dicritical digraphs $G$ on at least $k+1$ vertices and with $(k-1)|V(G)| + k-3$ arcs, generalising a result of Dirac. We prove that, for $k \geq 5$, every $k$-dicritical digraph $G$ has at least $(k-1/2 - 1/(k-1)) |V(G)| - k(1/2 - 1/(k-1))$ arcs, which is the best known lower bound. We prove that the number of connected components induced by the vertices of degree $2(k-1)$ of a $k$-dicritical digraph is at most the number of connected components in the rest of the digraph, generalising a result of Stiebitz. Finally, we generalise a Theorem of Thomassen on list-chromatic number of undirected graphs to list-dichromatic number of digraphs.
Given a square pencil $A+ \lambda B$, where $A$ and $B$ are complex matrices, we consider the problem of finding the singular pencil nearest to it in the Frobenius distance. This problem is known to be very difficult, and the few algorithms available in the literature can only deal efficiently with pencils of very small size. We show that the problem is equivalent to minimizing a certain objective function over the Riemannian manifold $SU(n) \times SU(n)$, where $SU(n)$ denotes the special unitary group. With minor modifications, the same approach extends to the case of finding a nearest singular pencil with a specified minimal index. This novel perspective is based on the generalized Schur form of pencils, and yields a competitive numerical method, by pairing it with an algorithm capable of doing optimization on a Riemannian manifold. We provide numerical experiments that show that the resulting method allows us to deal with pencils of much larger size than alternative techniques, yielding candidate minimizers of comparable or better quality. In the course of our analysis, we also obtain a number of new theoretical results related to the generalized Schur form of a (regular or singular) square pencil and to the minimal index of a singular square pencil whose nullity is $1$.
Eigenvalue density generated by embedded Gaussian unitary ensemble with $k$-body interactions for two species (say $\mathbf{\pi}$ and $\mathbf{\nu}$) fermion systems is investigated by deriving formulas for the lowest six moments. Assumed in constructing this ensemble, called EGUE($k:\mathbf{\pi} \mathbf{\nu}$), is that the $\mathbf{\pi}$ fermions ($m_1$ in number) occupy $N_1$ number of degenerate single particle (sp) states and similarly $\mathbf{\nu}$ fermions ($m_2$ in number) in $N_2$ number of degenerate sp states. The Hamiltonian is assumed to be $k$-body preserving $(m_1,m_2)$. Formulas with finite $(N_1,N_2)$ corrections and asymptotic limit formulas both show that the eigenvalue density takes $q$-normal form with the $q$ parameter defined by the fourth moment. The EGUE($k:\mathbf{\pi} \mathbf{\nu}$) formalism and results are extended to two species boson systems. Results in this work show that the $q$-normal form of the eigenvalue density established only recently for identical fermion and boson systems extends to two species fermion and boson systems.
We consider a linear implicit-explicit (IMEX) time discretization of the Cahn-Hilliard equation with a source term, endowed with Dirichlet boundary conditions. For every time step small enough, we build an exponential attractor of the discrete-in-time dynamical system associated to the discretization. We prove that, as the time step tends to 0, this attractor converges for the symmmetric Hausdorff distance to an exponential attractor of the continuous-in-time dynamical system associated with the PDE. We also prove that the fractal dimension of the exponential attractor (and consequently, of the global attractor) is bounded by a constant independent of the time step. The results also apply to the classical Cahn-Hilliard equation with Neumann boundary conditions.
We introduce a new stochastic algorithm to locate the index-1 saddle points of a function $V:\mathbb R^d \to \mathbb R$, with $d$ possibly large. This algorithm can be seen as an equivalent of the stochastic gradient descent which is a natural stochastic process to locate local minima. It relies on two ingredients: (i) the concentration properties on index-1 saddle points of the first eigenmodes of the Witten Laplacian (associated with $V$) on $1$-forms and (ii) a probabilistic representation of a partial differential equation involving this differential operator. Numerical examples on simple molecular systems illustrate the efficacy of the proposed approach.
We establish error bounds of the Lie-Trotter time-splitting sine pseudospectral method for the nonlinear Schr\"odinger equation (NLSE) with semi-smooth nonlinearity $ f(\rho) = \rho^\sigma$, where $\rho=|\psi|^2$ is the density with $\psi$ the wave function and $\sigma>0$ is the exponent of the semi-smooth nonlinearity. Under the assumption of $ H^2 $-solution of the NLSE, we prove error bounds at $ O(\tau^{\frac{1}{2}+\sigma} + h^{1+2\sigma}) $ and $ O(\tau + h^{2}) $ in $ L^2 $-norm for $0<\sigma\leq\frac{1}{2}$ and $\sigma\geq\frac{1}{2}$, respectively, and an error bound at $ O(\tau^\frac{1}{2} + h) $ in $ H^1 $-norm for $\sigma\geq \frac{1}{2}$, where $h$ and $\tau$ are the mesh size and time step size, respectively. In addition, when $\frac{1}{2}<\sigma<1$ and under the assumption of $ H^3 $-solution of the NLSE, we show an error bound at $ O(\tau^{\sigma} + h^{2\sigma}) $ in $ H^1 $-norm. Two key ingredients are adopted in our proof: one is to adopt an unconditional $ L^2 $-stability of the numerical flow in order to avoid an a priori estimate of the numerical solution for the case of $ 0 < \sigma \leq \frac{1}{2}$, and to establish an $ l^\infty $-conditional $ H^1 $-stability to obtain the $ l^\infty $-bound of the numerical solution by using the mathematical induction and the error estimates for the case of $ \sigma \ge \frac{1}{2}$; and the other one is to introduce a regularization technique to avoid the singularity of the semi-smooth nonlinearity in obtaining improved local truncation errors. Finally, numerical results are reported to demonstrate our error bounds.
For a state $\rho_{A_1^n B}$, we call a sequence of states $(\sigma_{A_1^k B}^{(k)})_{k=1}^n$ an approximation chain if for every $1 \leq k \leq n$, $\rho_{A_1^k B} \approx_\epsilon \sigma_{A_1^k B}^{(k)}$. In general, it is not possible to lower bound the smooth min-entropy of such a $\rho_{A_1^n B}$, in terms of the entropies of $\sigma_{A_1^k B}^{(k)}$ without incurring very large penalty factors. In this paper, we study such approximation chains under additional assumptions. We begin by proving a simple entropic triangle inequality, which allows us to bound the smooth min-entropy of a state in terms of the R\'enyi entropy of an arbitrary auxiliary state while taking into account the smooth max-relative entropy between the two. Using this triangle inequality, we create lower bounds for the smooth min-entropy of a state in terms of the entropies of its approximation chain in various scenarios. In particular, utilising this approach, we prove an approximate version of entropy accumulation and also provide a solution to the source correlation problem in quantum key distribution.
In this article, we study the inconsistency of systems of $\min-\rightarrow$ fuzzy relational equations. We give analytical formulas for computing the Chebyshev distances $\nabla = \inf_{d \in \mathcal{D}} \Vert \beta - d \Vert$ associated to systems of $\min-\rightarrow$ fuzzy relational equations of the form $\Gamma \Box_{\rightarrow}^{\min} x = \beta$, where $\rightarrow$ is a residual implicator among the G\"odel implication $\rightarrow_G$, the Goguen implication $\rightarrow_{GG}$ or Lukasiewicz's implication $\rightarrow_L$ and $\mathcal{D}$ is the set of second members of consistent systems defined with the same matrix $\Gamma$. The main preliminary result that allows us to obtain these formulas is that the Chebyshev distance $\nabla$ is the lower bound of the solutions of a vector inequality, whatever the residual implicator used. Finally, we show that, in the case of the $\min-\rightarrow_{G}$ system, the Chebyshev distance $\nabla$ may be an infimum, while it is always a minimum for $\min-\rightarrow_{GG}$ and $\min-\rightarrow_{L}$ systems.
We establish error bounds of the Lie-Trotter time-splitting sine pseudospectral method for the nonlinear Schr\"odinger equation (NLSE) with semi-smooth nonlinearity $ f(\rho) = \rho^\sigma$, where $\rho=|\psi|^2$ is the density with $\psi$ the wave function and $\sigma>0$ is the exponent of the semi-smooth nonlinearity. Under the assumption of $ H^2 $-solution of the NLSE, we prove error bounds at $ O(\tau^{\frac{1}{2}+\sigma} + h^{1+2\sigma}) $ and $ O(\tau + h^{2}) $ in $ L^2 $-norm for $0<\sigma\leq\frac{1}{2}$ and $\sigma\geq\frac{1}{2}$, respectively, and an error bound at $ O(\tau^\frac{1}{2} + h) $ in $ H^1 $-norm for $\sigma\geq \frac{1}{2}$, where $h$ and $\tau$ are the mesh size and time step size, respectively. In addition, when $\frac{1}{2}<\sigma<1$ and under the assumption of $ H^3 $-solution of the NLSE, we show an error bound at $ O(\tau^{\sigma} + h^{2\sigma}) $ in $ H^1 $-norm. Two key ingredients are adopted in our proof: one is to adopt an unconditional $ L^2 $-stability of the numerical flow in order to avoid an a priori estimate of the numerical solution for the case of $ 0 < \sigma \leq \frac{1}{2}$, and to establish an $ l^\infty $-conditional $ H^1 $-stability to obtain the $ l^\infty $-bound of the numerical solution by using the mathematical induction and the error estimates for the case of $ \sigma \ge \frac{1}{2}$; and the other one is to introduce a regularization technique to avoid the singularity of the semi-smooth nonlinearity in obtaining improved local truncation errors. Finally, numerical results are reported to demonstrate our error bounds.
The complex Helmholtz equation $(\Delta + k^2)u=f$ (where $k\in{\mathbb R},u(\cdot),f(\cdot)\in{\mathbb C}$) is a mainstay of computational wave simulation. Despite its apparent simplicity, efficient numerical methods are challenging to design and, in some applications, regarded as an open problem. Two sources of difficulty are the large number of degrees of freedom and the indefiniteness of the matrices arising after discretisation. Seeking to meet them within the novel framework of probabilistic domain decomposition, we set out to rewrite the Helmholtz equation into a form amenable to the Feynman-Kac formula for elliptic boundary value problems. We consider two typical scenarios, the scattering of a plane wave and the propagation inside a cavity, and recast them as a sequence of Poisson equations. By means of stochastic arguments, we find a sufficient and simulatable condition for the convergence of the iterations. Upon discretisation a necessary condition for convergence can be derived by adding up the iterates using the harmonic series for the matrix inverse -- we illustrate the procedure in the case of finite differences. From a practical point of view, our results are ultimately of limited scope. Nonetheless, this unexpected -- even paradoxical -- new direction of attack on the Helmholtz equation proposed by this work offers a fresh perspective on this classical and difficult problem. Our results show that there indeed exists a predictable range $k<k_{max}$ in which this new ansatz works with $k_{max}$ being far below the challenging situation.
We study empirical variants of the halfspace (Tukey) depth of a probability measure $\mu$, which are obtained by replacing $\mu$ with the corresponding weighted empirical measure. We prove analogues of the Marcinkiewicz--Zygmund strong law of large numbers and of the law of the iterated logarithm in terms of set inclusions and for the Hausdorff distance between the theoretical and empirical variants of depth trimmed regions. In the special case of $\mu$ being the uniform distribution on a convex body $K$, the depth trimmed regions are convex floating bodies of $K$, and we obtain strong limit theorems for their empirical estimators.