The expansion of a chord diagram and the Tutte polynomial

A chord diagram is a set of chords of a circle such that no pair of chords has a common endvertex. A chord diagram $E$ is called nonintersecting if $E$ contains no crossing. For a chord diagram $E$ having a crossing $S=\{x_1{x}_3,x_2{x}_4\}$, the expansion of $E$ with respect to $S$ is to replace $E$ with $E_1=(E?S)\cup \{x_2{x}_3,x_4{x}_1\}$ or $E_2=(E?S)\cup \{x_1{x}_2,x_3{x}_4\}$. For a chord diagram $E$, let $f\left(E\right)$ be the chord expansion number of $E$, which is defined as the cardinality of the multiset of all nonintersecting chord diagrams generated from $E$ with a finite sequence of expansions.In this paper, it is shown that the chord expansion number $f\left(E\right)$ equals the value of the Tutte polynomial at the point $(2,?1)$ for the interlace graph $G_E$ corresponding to $E$. The chord expansion number of a complete multipartite chord diagram is also studied. An extended abstract of the paper was published (Nakamigawa and Sakuma, 2017) [13].     

All double generalized Petersen graphs are Hamiltonian

The double generalized Petersen graph $DP(n,t)$, $n\ge 3$ and $t\in {\mathbb{Z}}_n?\left\{0\right\}$, $2\le 2t<n$, has vertex-set $\{x_i,y_i,u_i,v_i\mid i\in {\mathbb{Z}}_n\}$, edge-set $\{\{x_i,x_{i+1}\},\{y_i,y_{i+1}\},\{u_i,v_{i+t}\},\{v_i,u_{i+t}\},\{x_i,u_i\},\{y_i,v_i\}\mid i\in {\mathbb{Z}}_n\}$. These graphs were first defined by Zhou and Feng as examples of vertex-transitive non-Cayley graphs. Then, Kutnar and Petecki considered the structural properties, Hamiltonicity properties, vertex-coloring and edge-coloring of $DP(n,t)$, and conjectured that all $DP(n,t)$ are Hamiltonian. In this paper, we prove this conjecture.     

Minimal solutions of the isometry equation

For a finite vector space $W$ over ${\mathbb{F}}_q$, there are described all the pairs of multisets $\{V_1,\dots ,V_{q+1}\}$ and $\{U_1,\dots ,U_{q+1}\}$ of subspaces in $W$ such that for all $w\in W$ the equality $\left|\{i\mid w\in V_i\}\right|=\left|\{i\mid w\in U_i\}\right|$ holds.     

A new forbidden pair for 6-contractible edges

An edge of a $k$-connected graph is said to be $k$-contractible if the contraction of the edge results in a $k$-connected graph. If every $k$-connected graph with no $k$-contractible edge has either $H_1$ or $H_2$ as a subgraph, then an unordered pair of graphs $\{H_1,H_2\}$ is said to be a forbidden pair for $k$-contractible edges. We prove that $\{K_1+3K_2,K_1+(P_3\cup K_2)\}$ is a forbidden pair for 6-contractible edges, which is an extension of a previous result due to Ando and Kawarabayashi.     

A sufficient condition for DP-4-colorability

DP-coloring of a simple graph is a generalization of list coloring, and also a generalization of signed coloring of signed graphs. It is known that for each $k\in \{3,4,5,6\}$, every planar graph without $C_k$ is 4-choosable. Furthermore, Jin et al. (2016) showed that for each $k\in \{3,4,5,6\}$, every signed planar graph without $C_k$ is signed 4-choosable. In this paper, we show that for each $k\in \{3,4,5,6\}$, every planar graph without $C_k$ is 4-DP-colorable, which is an extension of the above results.     

A note on conservative galaxies,Skolem systems,cyclic cycle decompositions,and Heffter arrays

The conservative number of a graph $G$ is the minimum positive integer $M$, such that $G$ admits an orientation and a labeling of its edges by distinct integers in $\{1,2,\dots ,M\}$, such that at each vertex of degree at least three, the sum of the labels on the in-coming edges is equal to the sum of the labels on the out-going edges. A graph is conservative if $M=\left|E\left(G\right)\right|$. It is worth noting that determining whether certain biregular graphs are conservative is equivalent to find integer Heffter arrays.In this work we show that the conservative number of a galaxy (a disjoint union of stars) of size $M$ is $M$ for $M\equiv 0$, $3(mod4)$, and $M+1$ otherwise. Consequently, given positive integers $m_1$, $m_2$, …, $m_n$ with $m_i\ge 3$ for $1\le i\le n$, we construct a cyclic $(m_1,m_2,\dots ,m_n)$-cycle system of infinitely many circulant graphs, generalizing a result of Bryant, Gavlas and Ling (2003). In particular, it allows us to construct a cyclic $(m_1,m_2,\dots ,m_n)$-cycle system of the complete graph $K_{2M+1}$, where $M={\sum }_{i=1}^n{m}_i$. Also, we prove necessary and sufficient conditions for the existence of a cyclic $(m_1,m_2,\dots ,m_n)$-cycle system of $K_{2M+2}?F$, where $F$ is a 1-factor. Furthermore, we give a sufficient condition for a subset of ${\mathbb{Z}}_v?\left\{0\right\}$ to be sequenceable.     

On parabolic Kazhdan–Lusztig R-polynomials for the symmetric group

Parabolic R-polynomials were introduced by Deodhar as parabolic analogues of ordinary R-polynomials defined by Kazhdan and Lusztig. In this paper, we are concerned with the computation of parabolic R-polynomials for the symmetric group. Let $S_n$ be the symmetric group on $\{1,2,\dots ,n\}$, and let $S=\{s_i|1\le i\le n?1\}$ be the generating set of $S_n$, where for $1\le i\le n?1$, $s_i$ is the adjacent transposition. For a subset $J?S$, let ${(S_n)}_J$ be the parabolic subgroup generated by J, and let ${(S_n)}^J$ be the set of minimal coset representatives for $S_n/{(S_n)}_J$. For $u\le v\in {(S_n)}^J$ in the Bruhat order and $x\in \{q,?1\}$, let $R_{u,v}^{J,x}(q)$ denote the parabolic R-polynomial indexed by u and v. Brenti found a formula for $R_{u,v}^{J,x}(q)$ when $J=S?\{s_i\}$, and obtained an expression for $R_{u,v}^{J,x}(q)$ when $J=S?\{s_{i?1},s_i\}$. In this paper, we provide a formula for $R_{u,v}^{J,x}(q)$, where $J=S?\{s_{i?2},s_{i?1},s_i\}$ and i appears after $i?1$ in v. It should be noted that the condition that i appears after $i?1$ in v is equivalent to that v is a permutation in ${(S_n)}^{S?\{s_{i?2},s_i\}}$. We also pose a conjecture for $R_{u,v}^{J,x}(q)$, where $J=S?\{s_k,s_{k+1},\dots ,s_i\}$ with $1\le k\le i\le n?1$ and v is a permutation in ${(S_n)}^{S?\{s_k,s_i\}}$.     

Small-time expansions for state-dependent local jump–diffusion models with infinite jump activity

In this article, we consider a Markov process ${\left\{X_t\right\}}_{t?0}$, which solves a stochastic differential equation driven by a Brownian motion and an independent pure jump component exhibiting both state-dependent jump intensity and infinite jump activity. A second order expansion is derived for the tail probability $\mathbb{P}[X_t?x+y]$ in small time $t$, where $x$ is the initial value of the process and $y>0$. As an application of this expansion and a suitable change of the underlying probability measure, a second order expansion, near expiration, for out-of-the-money European call option prices is obtained when the underlying stock price is modeled as the exponential of the jump–diffusion process ${\left\{X_t\right\}}_{t?0}$ under the risk-neutral probability measure.     

Partitions of natural numbers with the same weighted representation functions

TextFor any given two positive integers $k_1$ and $k_2$, and any set A of nonnegative integers, let $r_{k_1,k_2}(A,n)$ denote the number of solutions of the equation $n=k_1{a}_1+k_2{a}_2$ with $a_1,a_2\in A$. In this paper, we determine all pairs $k_1,k_2$ of positive integers for which there exists a set $A?\mathbb{N}$ such that $r_{k_1,k_2}(A,n)=r_{k_1,k_2}(\mathbb{N}?A,n)$ for all $n?n_0$. We also pose several problems for further research.VideoFor a video summary of this paper, please click here or visit http://www.youtube.com/watch?v=EnezEsJl0OY.