results for au:Yan_W in:math

- This paper investigates the task assignment problem for multiple dispersed robots constrained by limited communication range. The robots are initially randomly distributed and need to visit several target locations while minimizing the total travel time. A centralized rendezvous-based algorithm is proposed, under which all the robots first move towards a rendezvous position until communication paths are established between every pair of robots either directly or through intermediate peers, and then one robot is chosen as the leader to make a centralized task assignment for the other robots. Furthermore, we propose a decentralized algorithm based on a single-traveling-salesman tour, which does not require all the robots to be connected through communication. We investigate the variation of the quality of the assignment solutions as the level of information sharing increases and as the communication range grows, respectively. The proposed algorithms are compared with a centralized algorithm with shared global information and a decentralized greedy algorithm respectively. Monte Carlo simulation results show the satisfying performance of the proposed algorithms.
- We use Coulomb branch indices of Argyres-Douglas theories on $S^1 \times L(k,1)$ to quantize moduli spaces ${\cal M}_H$ of wild/irregular Hitchin systems. In particular, we obtain formulae for the "wild Hitchin characters" -- the graded dimensions of the Hilbert spaces from quantization -- for four infinite families of ${\cal M}_H$, giving access to many interesting geometric and topological data of these moduli spaces. We observe that the wild Hitchin characters can always be written as a sum over fixed points in ${\cal M}_H$ under the $U(1)$ Hitchin action, and a limit of them can be identified with matrix elements of the modular transform $ST^kS$ in certain two-dimensional chiral algebras. Although naturally fitting into the geometric Langlands program, the appearance of chiral algebras, which was known previously to be associated with Schur operators but not Coulomb branch operators, is somewhat surprising.
- Oct 14 2016 math.DG arXiv:1610.03912v2An isoparametric hypersurface in unit spheres has two focal submanifolds. Condition A plays a crucial role in the classification theory of isoparametric hypersurfaces in [CCJ07], [Chi16] and [Miy13]. This paper determines $C_A$, the set of points with Condition A in focal submanifolds. It turns out that the points in $C_A$ reach an upper bound of the normal scalar curvature $\rho^{\bot}$ (sharper than that in DDVV inequality [GT08], [Lu11]). We also determine the sets $C_P$ (points with parallel second fundamental form) and $C_E$ (points with Einstein condition), which achieve two lower bounds of $\rho^{\bot}$.
- In this paper, we show the equivalence between two seemingly distinct 2d TQFTs: one comes from the "Coulomb branch index" of the class S theory $T[\Sigma,G]$ on $L(k,1) \times S^1$, the other is the $^LG$ "equivariant Verlinde formula", or equivalently partition function of $^LG_{\mathbb{C}}$ complex Chern-Simons theory on $\Sigma\times S^1$. We first derive this equivalence using the M-theory geometry and show that the gauge groups appearing on the two sides are naturally $G$ and its Langlands dual $^LG$. When $G$ is not simply-connected, we provide a recipe of computing the index of $T[\Sigma,G]$ as summation over indices of $T[\Sigma,\tilde{G}]$ with non-trivial background 't Hooft fluxes, where $\tilde{G}$ is the simply-connected group with the same Lie algebra. Then we check explicitly this relation between the Coulomb index and the equivariant Verlinde formula for $G=SU(2)$ or $SO(3)$. In the end, as an application of this newly found relation, we consider the more general case where $G$ is $SU(N)$ or $PSU(N)$ and show that equivariant Verlinde algebra can be derived using field theory via (generalized) Argyres-Seiberg duality. We also attach a Mathematica notebook that can be used to compute the $SU(3)$ equivariant Verlinde coefficients.
- May 10 2016 math.AP arXiv:1605.02412v1In this paper, we investigate the Cauchy problem for the shallow water type equation \begineqnarray* u_t+\partial_x^2j+1u + \frac12\partial_x(u^2)+ \partial_x(1-\partial_x^2)^-1\left[u^2+\frac12u_x^2\right]=0 \endeqnarray* with low regularity data in the periodic settings. Himonas and Misiolek (Communications in Partial Differential Equations, 23(1998), 123-139.) have proved that the problem is locally well-posed for small initial data in H^s(\mathbfT) with s≥-\fracj2+1,j∈N^+ with the aid of the standard Fourier restriction norm method. To the best of our knowledge, there is no result of well-posedness about the problem when s<-\fracj2+1. In this paper, firstly, we prove that the bilinear estimate related to the nonlinear term of the equation in standard Bourgain space is invalid with s<-\fracj2+1. Then we prove that the Cauchy problem for the periodic shallow water-type equation is locally well-posed in H^s(\mathbfT) with -j+\frac32< s<-\fracj2+1,j\geq2 for arbitrary initial data. The novelty is that we introduce some new function spaces and give a useful relationship among new spaces.
- We study chiral algebras associated with Argyres-Douglas theories engineered from M5 brane. For the theory engineered using 6d $(2,0)$ type $J$ theory on a sphere with a single irregular singularity (without mass parameter), its chiral algebra is the minimal model of W algebra of $J$ type. For the theory engineered using an irregular singularity and a regular full singularity, its chiral algebra is the affine Kac-Moody algebra of $J$ type. We can obtain the Schur index of these theories by computing the vacua character of the corresponding chiral algebra.
- Feb 16 2016 math.AP arXiv:1602.04533v1In this paper, we investigate the Cauchy problem for the shallow water type equation \[ u_t+\partial_x^3u + \frac12\partial_x(u^2)+\partial_x (1-\partial_x^2)^-1\left[u^2+\frac12u_x^2\right]=0,x∈\mathbf T=\R/2\pi \lambda \]with low regularity data in the periodic settings and $\lambda\geq1$. We prove that the bilinear estimate in $X_{s,b}$ with $s<\frac{1}{2}$ is invalid. We also prove that the problem is locally well-posed in $H^{s}(\mathbf{T})$ with $\frac{1}{6}<s<\frac{1}{2}$ for small initial data. The result of this paper improves the result of case $j=1$ of Himonas and Misiolek (Communications in Partial Differential Equations, 23(1998), 123-139.). The new ingredients are some new function spaces and some new Strichartz estimates.
- Feb 01 2016 math.OC arXiv:1601.07972v1It is desirable but challenging to fulfill system constraints and reach optimal performance in consensus protocol design for practical multi-agent systems (MASs). This paper investigates the optimal consensus problem for general linear MASs subject to control input constraints. Two classes of MASs including subsystems with semi-stable and unstable dynamics are considered. For both classes of MASs without input constraints, the results on designing optimal consensus protocols are first developed by inverse optimality approach. Utilizing the optimal consensus protocols, the receding horizon control (RHC)-based consensus strategies are designed for these two classes of MASs with input constraints. The conditions for assigning the cost functions distributively are derived, based on which the distributed RHC-based consensus frameworks are formulated. Next, the feasibility and consensus properties of the closed-loop systems are analyzed. It is shown that 1) the optimal performance indices under the inverse optimal consensus protocols are coupled with the network topologies and the system matrices of subsystems, but they are different for MASs with semi-stable and unstable subsystems; 2) the unstable modes of subsystems impose more stringent requirements for the parameter design; 3) the designed RHC-based consensus strategies can make the control input constraints fulfilled and ensure consensus for the closed-loop systems in both cases. But for MASs with semi-stable subsystems, the \em convergent consensus can be reached. Finally, two examples are provided to verify the effectiveness of the proposed results.
- Nov 10 2015 math.AP arXiv:1511.02430v1In this paper, we investigate the Cauchy problem for the higher-order KdV-type equation \begineqnarray* u_t+(-1)^j+1\partial_x^2j+1u + \frac12\partial_x(u^2) = 0,j∈N^+,x∈\mathbfT= [0,2\pi \lambda) \endeqnarray* with low regularity data and $\lambda\geq 1$. Firstly, we show that the Cauchy problem for the periodic higher-order KdV equation is locally well-posed in $H^{s}(\mathbf{T})$ with $s\geq -j+\frac{1}{2},j\geq2.$ By using some new Strichartz estimate and some new function spaces, we also show that the Cauchy problem for the periodic higher-order KdV equation is ill-posed in $H^{s}(\mathbf{T})$ with $s<-j+\frac{1}{2},j\geq2$ in the sense that the solution map is $C^{3}.$ The result of this paper improves the result of \citeH with $j\geq2$.
- Jul 30 2015 math.CO arXiv:1507.08022v2For any graph $G$, let $t(G)$ be the number of spanning trees of $G$, $L(G)$ be the line graph of $G$ and for any non-negative integer $r$, $S_r(G)$ be the graph obtained from $G$ by replacing each edge $e$ by a path of length $r+1$ connecting the two ends of $e$. In this paper we find a combinatorial approach to obtain %an expression for $t(L(G))$ and more generally an expression for $t(L(S_r(G)))$. Thus we generalize some known results on the relation between $t(L(G))$ and $t(G)$ and prove a conjecture that $t(L(S_1(G)))=k^{m+s-n-1}(k+2)^{m-n+1}t(G)$ for any graph $G$ of order $n+s$ and size $m+s$ in which $s$ vertices are of degree $1$ and the others are of degree $k$.
- May 25 2015 math.AP arXiv:1505.05995v1In this paper, we investigate the Cauchy problem for the Ostrovsky equation \begineqnarray* \partial_x\left(u_t-\beta \partial_x^3u +\frac12\partial_x(u^2)\right) -\gamma u=0, \endeqnarray* in the Sobolev space $H^{-3/4}(\R)$, $\beta>0,\gamma >0$. From the result of \citeIM1,IM3,Tsu, we know that $s=-\frac{3}{4}$ is the critical Sobolev index for the Ostrovsky equation. By using some modified Besov spaces, we prove that the Cauchy problem for the Ostrovsky equation with positive dispersion is locally well-posed in $H^{-3/4}(\R).$ The new ingredient that we introduce in this paper is Lemmas 2.1-2.2 which are used to overcome the difficulty caused by the singularity of the phase function at the zero point.
- We study integrable models in the context of the recently discovered Gauge/YBE correspondence, where the Yang-Baxter equation is promoted to a duality between two supersymmetric gauge theories. We study flavored elliptic genus of 2d $\mathcal{N}=(2,2)$ quiver gauge theories, which theories are defined from statistical lattices regarded as quiver diagrams. Our R-matrices are written in terms of theta functions, and simplifies considerably when the gauge groups at the quiver nodes are Abelian. We also discuss the modularity properties of the R-matrix, reduction of 2d index to 1d Witten index, and string theory realizations of our theories.
- Apr 10 2015 math.AP arXiv:1504.02172v1This paper is devoted to the Cauchy problem for the stochastic generalized Benjamin-Ono equation. By using the Bourgain spaces and Fourier restriction method and the assumption that $u_{0}$ is $\mathcal{F}_{0}$-measurable, we prove that the Cauchy problem for the stochastic generalized Benjamin-Ono equation is locally well-posed for the initial data $u_{0}(x,w)\in L^{2} (\Omega; H^{s}(\R))$ with $s\geq\frac{1}{2}-\frac{\alpha}{4}$, where $0< \alpha \leq 1.$ In particular, when $u_{0}\in L^{2}(\Omega; H^{\frac{\alpha+1}{2}}(\R))\cap L^{\frac{2(2+3\alpha)}{\alpha}}(\Omega; L^{2}(\R))$, we prove that there exists a unique global solution $u\in L^{2}(\Omega; H^{\frac{\alpha+1}{2}}(\R))$ with $0< \alpha \leq 1.$
- Mar 24 2015 math.AP arXiv:1503.06265v1In this paper, we investigate the Cauchy problem for a higher order shallow water type equation \begineqnarray* u_t-u_txx+\partial_x^2j+1u-\partial_x^2j+3u+3uu_x-2u_xu_xx-uu_xxx=0, \endeqnarray* where $x\in \mathbf{T}=\mathbf{R}/2\pi$ and $j\in N^{+}.$ Firstly, we prove that the Cauchy problem for the shallow water type equation is locally well-posed in $H^{s}(\mathbf{T})$ with $s\geq -\frac{j-2}{2}$ for arbitrary initial data. By using the $I$-method, we prove that the Cauchy problem for the shallow water type equation is globally well-posed in $H^{s}(\mathbf{T})$ with $\frac{2j+1-j^{2}}{2j+1}<s\leq 1.$ Our results improve the result of A. A. Himonas, G. Misiolek (Communications in partial Differential Equations, 23(1998), 123-139;Journal of Differential Equations, 161(2000), 479-495.)
- Mar 19 2015 math.AP arXiv:1503.05419v1In this paper, we prove the local well-posedness of 3-D density-dependent liquid crystal flows with initial data in the critical Besov spaces, without assumptions of small density variation. Furthermore, if the initial density is close enough to a positive constant and the critical Besov norm of the liquid crystal orientation field and the horizontal components of the initial velocity field polynomially small compared with the critical Besov norm to the veritcal component of the initial velocity field, then the system has a unique global solution.
- Feb 18 2015 math.AP arXiv:1502.04781v3In this paper, we consider the finite time blow up of solutions for the following two kinds of nonlinear wave equations on de Sitter spacetime \begineqnarray* &&\square_g=F(u),\\ &&\square_g=F(\partial_tu,∇u). \endeqnarray* This proof is based on a new blow up criterion, which generalize the blow up criterion in Sideris \citeSider. Furthermore, we give the lifespan estimate of solutions for the problems.
- This paper studies the large time existence for the motion of closed hypersurfaces in a radially symmetric potential. In physical, this surface can be considered as an electrically charged membrane with a constant charge per area in a radially symmetric potential. The evolution of such surface has been investigated by Schnürer and Smoczyk (Evolution of hypersurfaces in central force fields, J. Reine Angew. Math. 550 (2002), 77-95). To study its motion, we introduce a quasi-linear degenerate hyperbolic equation which describes the motion of the surfaces extrinsically. Our main results show that the large time existence of such Cauchy problem and the stability with respect to small initial data. When the radially symmetric potential function $v\equiv1$, the local existence and stability results have been obtained by Notz (Closed Hypersurfaces driven by mean curvature and inner pressure, Comm. Pure Appl. Math. 66(5) (2013), 790-819). The proof is based on a new Nash-Moser iteration scheme.
- Dec 01 2014 math.CO arXiv:1411.7458v1The matching energy is defined as the sum of the absolute values of the zeros of the matching polynomial of a graph, which is proposed first by Gutman and Wagner [The matching energy of a graph, Discrete Appl. Math. 160 (2012) 2177--2187]. And they gave some properties and asymptotic results of the matching energy. In this paper, we characterize the trees with $n$ vertices whose complements have the maximal, second-maximal and minimal matching energy. Further, we determine the trees with a perfect matching whose complements have the second-maximal matching energy. In particular, show that the trees with edge-independence number number $p$ whose complements have the minimum matching energy for $p=1,2,\ldots, \lfloor\frac{n}{2}\rfloor$.
- Nov 05 2014 math.AP arXiv:1411.0890v1In this paper, we investigate the Cauchy problem for the Ostrovsky equation \begineqnarray* \partial_x\left(u_t-\beta \partial_x^3u +\frac12\partial_x(u^2)\right) -\gamma u=0, \endeqnarray* in the Sobolev space $H^{-3/4}(\R)$. Here $\beta>0(<0)$ corresponds to the positive (negative) dispersion of the media, respectively. P. Isaza and J. Mejı́a (J. Diff. Eqns. 230(2006), 601-681; Nonli. Anal. 70(2009), 2306-2316), K. Tsugawa (J. Diff. Eqns. 247(2009), 3163-3180) proved that the problem is locally well-posed in $H^s(\R)$ when $s>-3/4$ and ill-posed when $s<-3/4$. By using some modified Bourgain spaces, we prove that the problem is locally well-posed in $H^{-3/4}(\R)$ with $\beta <0$ and $\gamma>0.$ The new ingredient that we introduce in this paper is Lemmas 2.1-2.6.
- Jun 25 2014 math.OC arXiv:1406.6167v1This paper investigates the consensus problem of general linear multi-agent systems under the framework of optimization. A novel distributed receding horizon control (RHC) strategy for consensus is proposed. We show that the consensus protocol generated by the unconstrained distributed RHC can be expressed in an explicit form. Based on the resulting consensus protocol the necessary and sufficient conditions for ensuring consensus are developed. Furthermore, we specify more detailed consensus conditions for multi-agent system with general and one-dimensional linear dynamics depending on the difference Riccati equations (DREs), respectively. Finally, two case studies verify the proposed scheme and the corresponding theoretical results.
- The focal sets of isoparametric hypersurfaces in spheres with g = 4 are all Willmore submanifolds, being minimal but mostly non-Einstein ([TY1], [QTY]). Inspired by A.Gray's view, the present paper shows that, these focal sets are all A- manifolds but rarely Ricci parallel, except possibly for the only unclassi?ed case. As a byproduct, it gives in?nitely many simply-connected examples to the problem 16.56 (i) of Besse concerning generalizations of the Einstein condition.
- Jun 11 2013 math.DG arXiv:1306.1996v2This paper mainly aims to establish the well-posedness on time interval $[0,\varepsilon^{-\frac{1}{2}}T]$ of the classical initial problem for the bosonic membrane in the light cone gauge. Here $\varepsilon$ is the small parameter measures the nonlinear effects. In geometric, the bosonic membrane are timelike submanifolds with vanishing mean curvature. Since the initial Riemannian metric may be degenerate or non-degenerate, the corresponding equation can be reduce to a quasi-linear degenerate or non-degenerate hyperbolic system of second order with an area preserving constraint via a Hamiltonian reduction. Our proof is based on a new Nash-Moser iteration scheme.
- In this paper, we consider the motion of timelike minimal surface in the Minkowski space $\textbf{R}^{1+n}$. Those surfaces are known as a membranes or relativistic strings, and described by a system with $n$ nonlinear wave equations of Born-Infeld type. We show that the timelike minimal surface can takes a time quasi-periodic motion in $\textbf{R}^{1+n}$.
- This paper is devoted to the study of a class of singular perturbation elliptic type problems on compact Lie groups or homogeneous spaces $\mathcal{M}$. By constructing a suitable Nash-Moser-type iteration scheme on compact Lie groups and homogeneous spaces, we overcome the clusters of "small divisor" problem, then the existence of solutions for nonlinear elliptic equations with a singular perturbation is established. Especially, if $\mathcal{M}$ is the standard torus $\textbf{T}^n$ or the spheres $\textbf{S}^n$, our result shows that there is a local uniqueness of spatially periodic solutions for nonlinear elliptic equations with a singular perturbation.
- This paper is devoted to the study of the dynamical behavior of the critically dissipative quasi-geostrophic equation in $\textbf{T}^2$. We prove that this system possesses time-dependent periodic solutions, bifurcating from a smooth steady solution, i.e. a Hopf-Bifurcation theorem.
- Apr 16 2012 math.DG arXiv:1204.2917v2This paper is a continuation of a paper with the same title of the last two authors. In the first part of the present paper, we give a unified geometric proof that both focal submanifolds of every isoparametric hypersurface in spheres with four distinct principal curvatures are Willmore. In the second part, we completely determine which focal submanifolds are Einstein except one case.
- Mar 13 2012 math.AP arXiv:1203.2405v3This paper is devoted to the study of the weak-strong uniqueness property for the full compressible magnetohydrodynamics flows. The governing equations for magnetohydrodynamic flows are expressed by the full Navier-Stokes system for compressible fluids enhanced by forces due to the presence of the magnetic field as well as the gravity and with an additional equation which describes the evolution of the magnetic field. Using relative entropy inequality, we prove that a weak solution coincides with the strong solution, emanating from the same initial data, as long as the latter exists.
- Mar 12 2012 math.DG arXiv:1203.2089v2Jakobson and Nadirashvili \citeJN constructed a sequence of eigenfunctions on $T^2$ with a bounded number of critical points, answering in the negative the question raised by Yau \citeYau1 which asks that whether the number of the critical points of eigenfunctions for the Laplacian increases with the corresponding eigenvalues. The present paper finds three interesting eigenfunctions on the minimal isoparametric hypersurface $M^n$ in $S^{n+1}(1)$. The corresponding eigenvalues are $n$, $2n$ and $3n$, while their critical sets consist of $8$ points, a submanifold(infinite many points) and $8$ points, respectively. On one of its focal submanifolds, a similar phenomenon occurs.
- Jan 04 2012 math.DG arXiv:1201.0666v3A well known conjecture of Yau states that the first eigenvalue of every closed minimal hypersurface $M^n$ in the unit sphere $S^{n+1}(1)$ is just its dimension $n$. The present paper shows that Yau conjecture is true for minimal isoparametric hypersurfaces. Moreover, the more fascinating result of this paper is that the first eigenvalues of the focal submanifolds are equal to their dimensions in the non-stable range.
- In this paper we consider the equations of the unsteady viscous, incompressible, and heat conducting magnetohydrodynamic flows in a bounded three-dimensional domain with Lipschitz boundary. By an approximation scheme and a weak convergence method, the existence of a weak solution to the three-dimensional density dependent generalized incompressible magnetohydrodynamic equations with large data is obtained.
- We study the N=2 four-dimensional superconformal index in various interesting limits, such that only states annihilated by more than one supercharge contribute. Extrapolating from the SU(2) generalized quivers, which have a Lagrangian description, we conjecture explicit formulae for all A-type quivers of class S, which in general do not have one. We test our proposals against several expected dualities. The index can always be interpreted as a correlator in a two-dimensional topological theory, which we identify in each limit as a certain deformation of two-dimensional Yang-Mills theory. The structure constants of the topological algebra are diagonal in the basis of Macdonald polynomials of the holonomies.
- Oct 18 2011 math.DG arXiv:1110.3557v2An isometric immersion $x:M^n\rightarrow S^{n+p}$ is called Willmore if it is an extremal submanifold of the Willmore functional: $W(x)=\int_{M^n} (S-nH^2)^{\frac{n}{2}}dv$, where $S$ is the norm square of the second fundamental form and $H$ is the mean curvature. Examples of Willmore submanifolds in the unit sphere are scarce in the literature. The present paper gives a series of new examples of Willmore submanifolds in the unit sphere via isoparametric functions of FKM-type.
- Jul 27 2011 math.DG arXiv:1107.5234v2Motivated by the celebrated Schoen-Yau-Gromov-Lawson surgery theory on metrics of positive scalar curvature, we construct a double manifold associated with a minimal isoparametric hypersurface in the unit sphere. The resulting double manifold carries a metric of positive scalar curvature and an isoparametric foliation as well. To investigate the topology of the double manifolds, we use K-theory and the representation of the Clifford algebra for the FKM-type, and determine completely the isotropy subgroups of singular orbits for homogeneous case.
- The number of independent sets is equivalent to the partition function of the hard-core lattice gas model with nearest-neighbor exclusion and unit activity. We study the number of independent sets $m_{d,b}(n)$ on the generalized Sierpinski gasket $SG_{d,b}(n)$ at stage $n$ with dimension $d$ equal to two, three and four for $b=2$, and layer $b$ equal to three for $d=2$. The upper and lower bounds for the asymptotic growth constant, defined as $z_{SG_{d,b}}=\lim_{v \to \infty} \ln m_{d,b}(n)/v$ where $v$ is the number of vertices, on these Sierpinski gaskets are derived in terms of the results at a certain stage. The numerical values of these $z_{SG_{d,b}}$ are evaluated with more than a hundred significant figures accurate. We also conjecture the upper and lower bounds for the asymptotic growth constant $z_{SG_{d,2}}$ with general $d$.
- Feb 08 2011 math.DG arXiv:1102.1126v2This paper introduces the notion of $k$-isoparametric hypersurface in an $(n+1)$-dimensional Riemannian manifold for $k=0,1,...,n$. Many fundamental and interesting results (towards the classification of homogeneous hypersurfaces among other things) are given in complex projective spaces, complex hyperbolic spaces, and even in locally rank one symmetric spaces.
- Jan 20 2011 math.AP arXiv:1101.3685v1In this paper, we study the global subsonic irrotational flows in a multi-dimensional ($n\geq 2$) infinitely long nozzle with variable cross sections. The flow is described by the inviscid potential equation, which is a second order quasilinear elliptic equation when the flow is subsonic. First, we prove the existence of the global uniformly subsonic flow in a general infinitely long nozzle for arbitrary dimension for sufficiently small incoming mass flux and obtain the uniqueness of the global uniformly subsonic flow. Furthermore, we show that there exists a critical value of the incoming mass flux such that a global uniformly subsonic flow exists uniquely, provided that the incoming mass flux is less than the critical value. This gives a positive answer to the problem of Bers on global subsonic irrotational flows in infinitely long nozzles for arbitrary dimension. Finally, under suitable asymptotic assumptions of the nozzle, we obtain the asymptotic behavior of the subsonic flow in far fields by a blow-up argument. The main ingredients of our analysis are methods of calculus of variations, the Moser iteration techniques for the potential equation and a blow-up argument for infinitely long nozzles.
- Let $G$ be a connected graph with vertex set $V(G)=\{v_1,v_2,...,v_{\nu}\}$, which may have multiple edges but have no loops, and $2\leq d_G(v_i)\leq 3$ for $i=1,2,...,\nu$, where $d_G(v)$ denotes the degree of vertex $v$ of $G$. We show that if $G$ has an even number of edges, then the number of perfect matchings of the line graph of $G$ equals $2^{n/2+1}$, where $n$ is the number of 3-degree vertices of $G$. As a corollary, we prove that the number of perfect matchings of a connected cubic line graph with $n$ vertices equals $2^{n/6+1}$ if $n>4$, which implies the conjecture by Lovász and Plummer holds for the connected cubic line graphs. As applications, we enumerate perfect matchings of the Kagomé lattices, $3.12.12$ lattices, and Sierpinski gasket with dimension two in the context of statistical physics.
- Oct 07 2008 math.CO arXiv:0810.0801v2The energy of a simple graph $G$ arising in chemical physics, denoted by $\mathcal E(G)$, is defined as the sum of the absolute values of eigenvalues of $G$. We consider the asymptotic energy per vertex (say asymptotic energy) for lattice systems. In general for a type of lattice in statistical physics, to compute the asymptotic energy with toroidal, cylindrical, Mobius-band, Klein-bottle, and free boundary conditions are different tasks with different hardness. In this paper, we show that if $\{G_n\}$ is a sequence of finite simple graphs with bounded average degree and $\{G_n'\}$ a sequence of spanning subgraphs of $\{G_n\}$ such that almost all vertices of $G_n$ and $G_n'$ have the same degrees, then $G_n$ and $G_n'$ have the same asymptotic energy. Thus, for each type of lattices with toroidal, cylindrical, Mobius-band, Klein-bottle, and free boundary conditions, we have the same asymptotic energy. As applications, we obtain the asymptotic formulae of energies per vertex of the triangular, $3^3.4^2$, and hexagonal lattices with toroidal, cylindrical, Mobius-band, Klein-bottle, and free boundary conditions simultaneously.
- By using combinatorics, we give a new proof for the recurrence relations of the characteristic polynomial coefficients, and then we obtain an explicit expression for the generic term of the coefficient sequence, which yields the trace formulae of the Cayley-Hamilton's theorem with all coefficients explicitly given, and which implies a byproduct, a complete expression for the determinant of any finite-dimensional matrix in terms of the traces of its successive powers. And we discuss some of their applications to chiral perturbation theory and general relativity.
- Nov 07 2006 math.CO arXiv:math/0611132v2The enumeration of perfect matchings of graphs is equivalent to the dimer problem which has applications in statistical physics. A graph $G$ is said to be $n$-rotation symmetric if the cyclic group of order $n$ is a subgroup of the automorphism group of $G$. Jockusch (Perfect matchings and perfect squares, J. Combin. Theory Ser. A, 67(1994), 100-115) and Kuperberg (An exploration of the permanent-determinant method, Electron. J. Combin., 5(1998), #46) proved independently that if $G$ is a plane bipartite graph of order $N$ with $2n$-rotation symmetry, then the number of perfect matchings of $G$ can be expressed as the product of $n$ determinants of order $N/2n$. In this paper we give this result a new presentation. We use this result to compute the entropy of a bulk plane bipartite lattice with $2n$-notation symmetry. We obtain explicit expressions for the numbers of perfect matchings and entropies for two types of cylinders. Using the results on the entropy of the torus obtained by Kenyon, Okounkov, and Sheffield (Dimers and amoebae, Ann. Math. 163(2006), 1019--1056) and by Salinas and Nagle (Theory of the phase transition in the layered hydrogen-bonded $SnCl^2\cdot 2H_2O$ crystal, Phys. Rev. B, 9(1974), 4920--4931), we show that each of the cylinders considered and its corresponding torus have the same entropy. Finally, we pose some problems.
- Sep 19 2006 math.CO arXiv:math/0609475v1Let $T$ be a weighted tree. The weight of a subtree $T_1$ of $T$ is defined as the product of weights of vertices and edges of $T_1$. We obtain a linear-time algorithm to count the sum of weights of subtrees of $T$. As applications, we characterize the tree with the diameter at least $d$, which has the maximum number of subtrees, and we characterize the tree with the maximum degree at least $\Delta$, which has the minimum number of subtrees.
- Feb 09 2006 math.CO arXiv:math/0602159v2In this paper we prove that two quantities relating to the length of permutations defined on trees are independent of the structures of trees. We also find that these results are closely related to the results obtained by Graham and Pollak (Bell System Tech. J. 50(1971) 2495--2519) and by Bapat, Kirkland, and Neumann (Linear Alg. Appl. 401(2005) 193--209).
- Nov 15 2005 math.CO arXiv:math/0511315v1We present some Pfaffian identities, which are completely different from the Plücker relations. As consequences we obtain a quadratic identity for the number of perfect matchings of plane graphs, which has a simpler form than the formula by Yan et al (Graphical condensation of plane graphs: a combinatorial approach, Theoret. Comput. Sci., to appear), and we also obtain some new determinant identities.
- Nov 15 2005 math.CO arXiv:math/0511316v1Let $G$ be a graph and let Pm$(G)$ denote the number of perfect matchings of $G$. We denote the path with $m$ vertices by $P_m$ and the Cartesian product of graphs $G$ and $H$ by $G\times H$. In this paper, as the continuance of our paper [19], we enumerate perfect matchings in a type of Cartesian products of graphs by the Pfaffian method, which was discovered by Kasteleyn. Here are some of our results: 1. Let $T$ be a tree and let $C_n$ denote the cycle with $n$ vertices. Then Pm$(C_4\times T)=\prod (2+\alpha^2)$, where the product ranges over all eigenvalues $\alpha$ of $T$. Moreover, we prove that Pm$(C_4\times T)$ is always a square or double a square. 2. Let $T$ be a tree. Then Pm$(P_4\times T)=\prod (1+3\alpha^2+\alpha^4)$, where the product ranges over all non-negative eigenvalues $\alpha$ of $T$. 3. Let $T$ be a tree with a perfect matching. Then Pm$(P_3\times T)=\prod (2+\alpha^2),$ where the product ranges over all positive eigenvalues $\alpha$ of $T$. Moreover, we prove that Pm$(C_4\times T)=[{Pm}(P_3\times T)]^2$.
- Sep 16 2005 math.CO arXiv:math/0509337v2The method of graphical vertex-condensation for enumerating perfect matchings of plane bipartite graph was found by Propp (Theoret. Comput. Sci. 303(2003), 267-301), and was generalized by Kuo (Theoret. Comput. Sci. 319 (2004), 29-57) and Yan and Zhang (J. Combin. Theory Ser. A, 110(2005), 113-125). In this paper, by a purely combinatorial method some explicit identities on graphical vertex-condensation for enumerating perfect matchings of plane graphs (which do not need to be bipartite) are obtained. As applications of our results, some results on graphical edge-condensation for enumerating perfect matchings are proved, and we count the sum of weights of perfect matchings of weighted Aztec diamond.