In this paper, we provide bounds for the genus of the pancake graph $\mathbb{P}_n$, burnt pancake graph $\mathbb{BP}_n$, and undirected generalized pancake graph $\mathbb{P}_m(n)$. Our upper bound for $\mathbb{P}_n$ is sharper than the previously-known bound, and the other bounds presented are the first of their kind. Our proofs are constructive and rely on finding an appropriate rotation system (also referred to in the literature as Edmonds' permutation technique) where certain cycles in the graphs we consider become boundaries of regions of a 2-cell embedding. A key ingredient in the proof of our bounds for the genus $\mathbb{P}_n$ and $\mathbb{BP}_n$ is a labeling algorithm of their vertices that allows us to implement rotation systems to bound the number of regions of a 2-cell embedding of said graphs.
相關內容
The paper aims to study the performance of the amplitude-based model \newline $\widehat{\mathbf x} \in {\rm argmin}_{{\mathbf x}\in \mathbb{C}^d}\sum_{j=1}^m\left(|\langle {\mathbf a}_j,{\mathbf x}\rangle|-b_j\right)^2$, where $b_j:=|\langle {\mathbf a}_j,{\mathbf x}_0\rangle|+\eta_j$ and ${\mathbf x}_0\in \mathbb{C}^d$ is a target signal. The model is raised in phase retrieval as well as in absolute value rectification neural networks. Many efficient algorithms have been developed to solve it in the past decades. {However, there are very few results available regarding the estimation performance in the complex case under noisy conditions.} In this paper, {we present a theoretical guarantee on the amplitude-based model for the noisy complex phase retrieval problem}. Specifically, we show that $\min_{\theta\in[0,2\pi)}\|\widehat{\mathbf x}-\exp(\mathrm{i}\theta)\cdot{\mathbf x}_0\|_2 \lesssim \frac{\|{\mathbf \eta}\|_2}{\sqrt{m}}$ holds with high probability provided the measurement vectors ${\mathbf a}_j\in \mathbb{C}^d,$ $j=1,\ldots,m,$ are {i.i.d.} complex sub-Gaussian random vectors and $m\gtrsim d$. Here ${\mathbf \eta}=(\eta_1,\ldots,\eta_m)\in \mathbb{R}^m$ is the noise vector without any assumption on the distribution. Furthermore, we prove that the reconstruction error is sharp. For the case where the target signal ${\mathbf x}_0\in \mathbb{C}^{d}$ is sparse, we establish a similar result for the nonlinear constrained $\ell_1$ minimization model. { To accomplish this, we leverage a strong version of restricted isometry property for an operator on the space of simultaneous low-rank and sparse matrices.}
Given a surface $\Sigma$ equipped with a set $P$ of marked points, we consider the triangulations of $\Sigma$ with vertex set $P$. The flip-graph of $\Sigma$ whose vertices are these triangulations, and whose edges correspond to flipping arcs appears in the study of moduli spaces and mapping class groups. We consider the number of geodesics in the flip-graph of $\Sigma$ between two triangulations as a function of their distance. We show that this number grows exponentially provided the surface has enough topology, and that in the remaining cases the growth is polynomial.
In this work, we propose a simple yet generic preconditioned Krylov subspace method for a large class of nonsymmetric block Toeplitz all-at-once systems arising from discretizing evolutionary partial differential equations. Namely, our main result is to propose two novel symmetric positive definite preconditioners, which can be efficiently diagonalized by the discrete sine transform matrix. More specifically, our approach is to first permute the original linear system to obtain a symmetric one, and subsequently develop desired preconditioners based on the spectral symbol of the modified matrix. Then, we show that the eigenvalues of the preconditioned matrix sequences are clustered around $\pm 1$, which entails rapid convergence when the minimal residual method is devised. Alternatively, when the conjugate gradient method on the normal equations is used, we show that our preconditioner is effective in the sense that the eigenvalues of the preconditioned matrix sequence are clustered around unity. An extension of our proposed preconditioned method is given for high-order backward difference time discretization schemes, which can be applied on a wide range of time-dependent equations. Numerical examples are given, also in the variable-coefficient setting, to demonstrate the effectiveness of our proposed preconditioners, which consistently outperforms an existing block circulant preconditioner discussed in the relevant literature.
By combining a logarithm transformation with a corrected Milstein-type method, the present article proposes an explicit, unconditional boundary and dynamics preserving scheme for the stochastic susceptible-infected-susceptible (SIS) epidemic model that takes value in (0,N). The scheme applied to the model is first proved to have a strong convergence rate of order one. Further, the dynamic behaviors are analyzed for the numerical approximations and it is shown that the scheme can unconditionally preserve both the domain and the dynamics of the model. More precisely, the proposed scheme gives numerical approximations living in the domain (0,N) and reproducing the extinction and persistence properties of the original model for any time discretization step-size h > 0, without any additional requirements on the model parameters. Numerical experiments are presented to verify our theoretical results.
In this work, we first develop a general mesoscopic multiple-relaxation-time lattice Boltzmann (MRT-LB) model for the two-dimensional diffusion equation with the constant diffusion coefficient and source term, where the D2Q5 (five discrete velocities in two-dimensional space) lattice structure is considered. Then we exactly derive the equivalent macroscopic finite-difference scheme of the MRT-LB model. Additionally, we also propose a proper MRT-LB model for the diffusion equation with a linear source term, and obtain an equivalent macroscopic six-level finite-difference scheme. After that, we conduct the accuracy and stability analysis of the finite-difference scheme and the mesoscopic MRT-LB model. It is found that at the diffusive scaling, both of them can achieve a fourth-order accuracy in space based on the Taylor expansion. The stability analysis also shows that they are both unconditionally stable. Finally, some numerical experiments are conducted, and the numerical results are also consistent with our theoretical analysis.
In this paper we propose a modification to the invariant polytope algorithm (ipa) using ideas of the finite expressible tree algorithm (feta) by M\"oller and Reif. We show that our new feta-flavoured-ipa applies to a wider range of matrix families.
This is an expository paper. A $1$-cycle in a graph is a set $C$ of edges such that every vertex is contained in an even number of edges from $C$. E.g., a cycle in the sense of graph theory is a $1$-cycle, but not vice versa. It is easy to check that the sum (modulo $2$) of $1$-cycles is a $1$-cycle. In this text we study the following problems: to find $\bullet$ the number of all 1-cycles in a given graph; $\bullet$ a small number of 1-cycles in a given graph such that any 1-cycle is the sum of some of them. We also consider generalizations (of these problems) to graphs with symmetry, and to $2$-cycles in $2$-dimensional hypergraphs.
We propose a deep learning based method for simulating the large bending deformation of bilayer plates. Inspired by the greedy algorithm, we propose a pre-training method on a series of nested domains, which can accelerate the convergence of training and find the absolute minimizer more effectively. The proposed method exhibits the capability to converge to an absolute minimizer, overcoming the limitation of gradient flow methods getting trapped in local minimizer basins. We showcase better performance for the relative energy errors and relative $L^2$-errors of the minimizer through several numerical experiments. Furthermore, our method successfully maintains the $L^2$-norm of the isometric constraint, leading to improved solution accuracy.
Large datasets are often affected by cell-wise outliers in the form of missing or erroneous data. However, discarding any samples containing outliers may result in a dataset that is too small to accurately estimate the covariance matrix. Moreover, most robust procedures designed to address this problem are not effective on high-dimensional data as they rely crucially on invertibility of the covariance operator. In this paper, we propose an unbiased estimator for the covariance in the presence of missing values that does not require any imputation step and still achieves minimax statistical accuracy with the operator norm. We also advocate for its use in combination with cell-wise outlier detection methods to tackle cell-wise contamination in a high-dimensional and low-rank setting, where state-of-the-art methods may suffer from numerical instability and long computation times. To complement our theoretical findings, we conducted an experimental study which demonstrates the superiority of our approach over the state of the art both in low and high dimension settings.
In this paper, we propose a parameter identification methodology of the SIRD model, an extension of the classical SIR model, that considers the deceased as a separate category. In addition, our model includes one parameter which is the ratio between the real total number of infected and the number of infected that were documented in the official statistics. Due to many factors, like governmental decisions, several variants circulating, opening and closing of schools, the typical assumption that the parameters of the model stay constant for long periods of time is not realistic. Thus our objective is to create a method which works for short periods of time. In this scope, we approach the estimation relying on the previous 7 days of data and then use the identified parameters to make predictions. To perform the estimation of the parameters we propose the average of an ensemble of neural networks. Each neural network is constructed based on a database built by solving the SIRD for 7 days, with random parameters. In this way, the networks learn the parameters from the solution of the SIRD model. Lastly we use the ensemble to get estimates of the parameters from the real data of Covid19 in Romania and then we illustrate the predictions for different periods of time, from 10 up to 45 days, for the number of deaths. The main goal was to apply this approach on the analysis of COVID-19 evolution in Romania, but this was also exemplified on other countries like Hungary, Czech Republic and Poland with similar results. The results are backed by a theorem which guarantees that we can recover the parameters of the model from the reported data. We believe this methodology can be used as a general tool for dealing with short term predictions of infectious diseases or in other compartmental models.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191