Variational formulation of time-fractional parabolic equations

We consider initial/boundary value problems for parabolic PDE ${?}_t^{\alpha }u?\Delta u=f$ with fractional Caputo derivative ${?}_t^{\alpha }$ of order $1∕2<\alpha <1$ as time derivative and the usual Laplacian $?\Delta$ as space derivative (also called fractional diffusion equations in the literature). We prove well-posedness of corresponding variational formulations based entirely on fractional Sobolev–Bochner spaces, and extend existing results for possible choices of the initial value for $u$ at $t=0$.     

A compact ADI method and its extrapolation for time fractional sub-diffusion equations with nonhomogeneous Neumann boundary conditions

A compact alternating direction implicit (ADI) finite difference method is proposed for two-dimensional time fractional sub-diffusion equations with nonhomogeneous Neumann boundary conditions. The unconditional stability and convergence of the method is proved. The error estimates in the weighted $L^2$- and $L^{\infty }$-norms are obtained. The proposed method has the fourth-order spatial accuracy and the temporal accuracy of order $min\{2?\alpha ,1+\alpha \}$, where $\alpha \in (0,1)$ is the order of the fractional derivative. In order to further improve the temporal accuracy, two Richardson extrapolation algorithms are presented. Numerical results demonstrate the accuracy of the compact ADI method and the high efficiency of the extrapolation algorithms.     

Relations between matrix sets generated from linear matrix expressions and their applications

Let $A+BXC$ and $A+BX+YC$ be two linear matrix expressions, and denote by $\{A+BXC\}$ and $\{A+BX+YC\}$ the collections of the two matrix expressions when $X$ and $Y$ run over the corresponding matrix spaces. In this paper, we study relationships between the two matrix sets $\{A_1+B_1{X}_1{C}_1\}$ and $\{A_2+B_2{X}_2{C}_2\}$, as well as the two sets $\{A_1+B_1{X}_1+Y_1{C}_1\}$ and $\{A_2+B_2{X}_2+Y_2{C}_2\}$, by using some rank formulas for matrices. In particular, we give necessary and sufficient conditions for the two matrix set inclusions $\{A_1+B_1{X}_1{C}_1\}?\{A_2+B_2{X}_2{C}_2\}$ and $\{A_1+B_1{X}_1+Y_1{C}_1\}?\{A_2+B_2{X}_2+Y_2{C}_2\}$ to hold. We also use the results obtained to characterize relations of solutions of some linear matrix equations.     

Finite time blow-up for a class of parabolic or pseudo-parabolic equations

In this paper, we study the initial boundary value problem for a class of parabolic or pseudo-parabolic equations:

$u_t?a\Delta u_t?\Delta u+bu=k\left(t\right)|u{|}^{p?2}u,(x,t)\in \Omega \times (0,T),$

where $a\ge 0$, $b>?{?}_1$ with ${?}_1$ being the principal eigenvalue for $?\Delta$ on $H_0^1\left(\Omega \right)$ and $k\left(t\right)>0$. By using the potential well method, Levine’s concavity method and some differential inequality techniques, we obtain the finite time blow-up results provided that the initial energy satisfies three conditions: (i) $J(u_0;0)<0$; (ii) $J(u_0;0)\le d\left(\infty \right)$, where $d\left(\infty \right)$ is a nonnegative constant; (iii) $0<J(u_0;0)\le C\rho \left(0\right)$, where $\rho \left(0\right)$ involves the $L^2$-norm or $H_0^1$-norm of the initial data. We also establish the lower and upper bounds for the blow-up time. In particular, we obtain the existence of certain solutions blowing up in finite time with initial data at the Nehari manifold or at arbitrary energy level.     

Longest paths and cycles in faulty star graphs

In this paper, we investigate the star graph $S_n$ with faulty vertices and/or edges from the graph theoretic point of view. We show that between every pair of vertices with different colors in a bicoloring of $S_n$, $n⩾4$, there is a fault-free path of length at least $n!-2f_v-1$, and there is a path of length at least $n!-2f_v-2$ joining a pair of vertices with the same color, when the number of faulty elements is $n-3$ or less. Here, $f_v$ is the number of faulty vertices. $S_n$, $n⩾4$, with at most $n-2$ faulty elements has a fault-free cycle of length at least $n!-2f_v$ unless the number of faulty elements are $n-2$ and all the faulty elements are edges incident to a common vertex. It is also shown that $S_n$, $n⩾4$, is strongly hamiltonian-laceable if the number of faulty elements is $n-3$ or less and the number of faulty vertices is one or less.     

State complexity of power

The number of states in a deterministic finite automaton (DFA) recognizing the language $L^k$, where $L$ is regular language recognized by an $n$-state DFA, and $k?2$ is a constant, is shown to be at most $n{2}^{(k?1)n}$ and at least $(n?k)2^{(k?1)(n?k)}$ in the worst case, for every $n>k$ and for every alphabet of at least six letters. Thus, the state complexity of $L^k$ is $\Theta \left(n{2}^{(k?1)n}\right)$. In the case $k=3$ the corresponding state complexity function for $L^3$ is determined as $\frac{6n?3}{8}{4}^n?(n?1)2^n?n$ with the lower bound witnessed by automata over a four-letter alphabet. The nondeterministic state complexity of $L^k$ is demonstrated to be $nk$. This bound is shown to be tight over a two-letter alphabet.     

Nonexistence of global solutions for a class of nonlocal in time and space nonlinear evolution equations

In this paper, we study the nonlocal nonlinear evolution equation

${}^C{D}_{0|t}^{\alpha }u(t,x)?(J1\left|u\right|?\left|u\right|)(t,x){+}^C{D}_{0|t}^{\beta }u(t,x)={\left|u(t,x)\right|}^p,t>0,x\in {\mathbb{R}}^d,$

where $1<\alpha <2$, $0<\beta <1$, $p>1$, $J:{\mathbb{R}}^d\to {\mathbb{R}}_{+}$, $1$ is the convolution product in ${\mathbb{R}}^d$, and ${}^C{D}_{0|t}^q$, $q\in \{\alpha ,\beta \}$, is the Caputo left-sided fractional derivative of order $q$ with respect to the time $t$. We prove that the problem admits no global weak solution other than the trivial one with suitable initial data when $1<p<1+\frac{2\beta }{d\beta +2(1?\beta )}$. Next, we deal with the system

where $1<\alpha <2$, $0<\beta <1$, $p>1$, and $q>1$. We prove that the system admitsnon global weak solution other than the trivial one with suitable initial data when $1<pq<1+\frac{2\beta }{d\beta +2(1?\beta )}max\{p+1,q+1\}$. Our approach is based on the test function method.     

On average and highest number of flips in pancake sorting

We are given a stack of pancakes of different sizes and the only allowed operation is to take several pancakes from the top and flip them. The unburnt version requires the pancakes to be sorted by their sizes at the end, while in the burnt version they additionally need to be oriented burnt-side down. We are interested in the largest value of the number of flips needed to sort a stack of $n$ pancakes, both in the unburnt version ($f\left(n\right)$) and in the burnt version ($g\left(n\right)$).We present exact values of $f\left(n\right)$ up to $n=19$ and of $g\left(n\right)$ up to $n=17$ and disprove a conjecture of Cohen and Blum by showing that the burnt stack $?I_{15}$ is not the hardest to sort for $n=15$.We also show that sorting a random stack of $n$ unburnt pancakes can be done with at most $17n/12+O\left(1\right)$ flips on average. The average number of flips of the optimal algorithm for sorting stacks of $n$ burnt pancakes is shown to be between $n+\Omega (n/logn)$ and $7n/4+O\left(1\right)$ and we conjecture that it is $n+\Theta (n/logn)$.Finally we show that sorting the stack $?I_n$ needs at least $?(3n+3)/2?$ flips, which slightly increases the lower bound on $g\left(n\right)$. This bound together with the upper bound for sorting $?I_n$ found by Heydari and Sudborough in 1997 [10] gives the exact number of flips to sort it for $n\equiv 3(mod4)$ and $n\ge 15$.