A stability version for a theorem of Erdős on nonhamiltonian graphs

Let $n,d$ be integers with $1\le d\le ?\frac{n?1}{2}?$, and set $h(n,d)?\left(\genfrac{}{}{0ex}{}{n?d}{2}\right)+d^2$ and $e(n,d)?max\{h(n,d),h(n,?\frac{n?1}{2}?)\}$. Because $h(n,d)$ is quadratic in $d$, there exists a $d_0\left(n\right)=(n∕6)+O\left(1\right)$ such that

$e(n,1)>e(n,2)>?>e(n,d_0)=e(n,d_0+1)=?=e\left(n,?\frac{n?1}{2}?\right).$

A theorem by Erd?s states that for $d\le ?\frac{n?1}{2}?$, any $n$-vertex nonhamiltonian graph $G$ with minimum degree $\delta \left(G\right)\ge d$ has at most $e(n,d)$ edges, and for $d>d_0\left(n\right)$ the unique sharpness example is simply the graph $K_n?E\left(K_{?(n+1)∕2?}\right)$. Erd?s also presented a sharpness example $H_{n,d}$ for each $1\le d\le d_0\left(n\right)$.We show that if $d<d_0\left(n\right)$ and a $2$-connected, nonhamiltonian $n$-vertex graph $G$ with $\delta \left(G\right)\ge d$ has more than $e(n,d+1)$ edges, then $G$ is a subgraph of $H_{n,d}$. Note that $e(n,d)?e(n,d+1)=n?3d?2\ge n∕2$ whenever $d<d_0\left(n\right)?1$.     

Steiner tree packing number and tree connectivity

Let $S$ be a set of at least two vertices in a graph $G$. A subtree $T$ of $G$ is a $S$-Steiner tree if $S?V\left(T\right)$. Two $S$-Steiner trees $T_1$ and $T_2$ are edge-disjoint (resp. internally vertex-disjoint) if $E\left(T_1\right)\cap E\left(T_2\right)=?$ (resp. $E\left(T_1\right)\cap E\left(T_2\right)=?$ and $V\left(T_1\right)\cap V\left(T_2\right)=S$). Let ${\lambda }_G\left(S\right)$ (resp. ${\kappa }_G\left(S\right)$) be the maximum number of edge-disjoint (resp. internally vertex-disjoint) $S$-Steiner trees in $G$, and let ${\lambda }_k\left(G\right)$ (resp. ${\kappa }_k\left(G\right)$) be the minimum ${\lambda }_G\left(S\right)$ (resp. ${\kappa }_G\left(S\right)$) for $S$ ranges over all $k$-subset of $V\left(G\right)$. Kriesell conjectured that if ${\lambda }_G\left(\{x,y\}\right)\ge 2k$ for any $x,y\in S$, then ${\lambda }_G\left(S\right)\ge k$. He proved that the conjecture holds for $\left|S\right|=3,4$. In this paper, we give a short proof of Kriesell’s Conjecture for $\left|S\right|=3,4$, and also show that ${\lambda }_k\left(G\right)\ge ?\frac{1}{k?1}?\frac{k?}{2}??$ (resp. ${\kappa }_k\left(G\right)\ge ?\frac{1}{k?1}?\frac{k?}{2}??$ ) if $\lambda \left(G\right)\ge ?$ (resp. $\kappa \left(G\right)\ge ?$) in $G$, where $k=3,4$. Moreover, we also study the relation between ${\kappa }_k\left(L\left(G\right)\right)$ and ${\lambda }_k\left(G\right)$, where $L\left(G\right)$ is the line graph of $G$.     

Singular discrete and continuous mixed boundary value problems

For each $n\in \mathbb{N}$, $n\ge 2$, we prove the existence of a solution $(u_0,\dots ,u_n)\in {\mathbb{R}}^{n+1}$ of the singular discrete problem $\frac{1}{h^2}{\Delta }^2{u}_{k?1}+f(t_k,u_k)=0\text{,}k=1,\dots ,n?1\text{,}$$\Delta u_0=0\text{,}{u}_n=0\text{,}$ where $u_k>0$ for $k=0,\dots ,n?1$. Here $T\in (0,\infty )$, $h=\frac{T}{n}$, $t_k=hk$, $f(t,x):[0,T]\times (0,\infty )\to \mathbb{R}$ is continuous and has a singularity at $x=0$. We prove that for $n\to \infty$ the sequence of solutions of the above discrete problems converges to a solution $y$ of the corresponding continuous boundary value problem $y^{″}\left(t\right)+f(t,y\left(t\right))=0\text{,}$$y^{\prime }\left(0\right)=0\text{,}y\left(T\right)=0\text{.}$     

Limit theorems for critical first-passage percolation on the triangular lattice

Consider (independent) first-passage percolation on the sites of the triangular lattice $\mathbb{T}$ embedded in $\mathbb{C}$. Denote the passage time of the site $v$ in $\mathbb{T}$ by $t\left(v\right)$, and assume that $P(t\left(v\right)=0)=P(t\left(v\right)=1)=1∕2$. Denote by $b_{0,n}$ the passage time from 0 to the halfplane $\{v\in \mathbb{T}:\text{Re}\left(v\right)\ge n\}$, and by $T(0,nu)$ the passage time from 0 to the nearest site to $nu$, where $\left|u\right|=1$. We prove that as $n\to \infty$, $b_{0,n}∕logn\to 1∕\left(2\sqrt{3}\pi \right)$ a.s., $E\left[b_{0,n}\right]∕logn\to 1∕\left(2\sqrt{3}\pi \right)$ and Var$\left[b_{0,n}\right]∕logn\to 2∕\left(3\sqrt{3}\pi \right)?1∕\left(2{\pi }^2\right)$; $T(0,nu)∕logn\to 1∕\left(\sqrt{3}\pi \right)$ in probability but not a.s., $E\left[T(0,nu)\right]∕logn\to 1∕\left(\sqrt{3}\pi \right)$ and Var$\left[T(0,nu)\right]∕logn\to 4∕\left(3\sqrt{3}\pi \right)?1∕{\pi }^2$. This answers a question of Kesten and Zhang (1997) and improves our previous work (2014). From this result, we derive an explicit form of the central limit theorem for $b_{0,n}$ and $T(0,nu)$. A key ingredient for the proof is the moment generating function of the conformal radii for conformal loop ensemble ${\mathrm{CLE}}_6$, given by Schramm et al. (2009).     

Nonexistence of some linear codes over the field of order four

We consider the problem of determining $n_4(5,d)$, the smallest possible length $n$ for which an ${[n,5,d]}_4$ code of minimum distance $d$ over the field of order 4 exists. We prove the nonexistence of ${[g_4(5,d)+1,5,d]}_4$ codes for $d=31,47,48,59,60,61,62$ and the nonexistence of a ${[g_4(5,d),5,d]}_4$ code for $d=138$ using the geometric method through projective geometries, where $g_q(k,d)={\sum }_{i=0}^{k?1}?d∕q^i?$. This yields to determine the exact values of $n_4(5,d)$ for these values of $d$. We also give the updated table for $n_4(5,d)$ for all $d$ except some known cases.     

On Birman's sequence of Hardy–Rellich-type inequalities

In 1961, Birman proved a sequence of inequalities $\{I_n\}$, for $n\in \mathbb{N}$, valid for functions in $C_0^n((0,\infty ))?L^2((0,\infty ))$. In particular, $I_1$ is the classical (integral) Hardy inequality and $I_2$ is the well-known Rellich inequality. In this paper, we give a proof of this sequence of inequalities valid on a certain Hilbert space $H_n([0,\infty ))$ of functions defined on $[0,\infty )$. Moreover, $f\in H_n([0,\infty ))$ implies $f^{\prime }\in H_{n?1}([0,\infty ))$; as a consequence of this inclusion, we see that the classical Hardy inequality implies each of the inequalities in Birman's sequence. We also show that for any finite $b>0$, these inequalities hold on the standard Sobolev space $H_0^n((0,b))$. Furthermore, in all cases, the Birman constants ${[(2n?1)!!]}^2/2^{2n}$ in these inequalities are sharp and the only function that gives equality in any of these inequalities is the trivial function in $L^2((0,\infty ))$ (resp., $L^2((0,b))$). We also show that these Birman constants are related to the norm of a generalized continuous Cesàro averaging operator whose spectral properties we determine in detail.     

The Laplacian spectral radius of trees and maximum vertex degree

Let $\Delta \left(T\right)$ and $\mu \left(T\right)$ denote the maximum degree and the Laplacian spectral radius of a tree $T$, respectively. In this paper we prove that for two trees $T_1$ and $T_2$ on $n(n\ge 21)$ vertices, if $\Delta \left(T_1\right)>\Delta \left(T_2\right)$ and $\Delta \left(T_1\right)\ge ?\frac{11n}{30}?+1$, then $\mu \left(T_1\right)>\mu \left(T_2\right)$, and the bound “$\Delta \left(T_1\right)\ge ?\frac{11n}{30}?+1$” is the best possible. We also prove that for two trees $T_1$ and $T_2$ on $2k(k\ge 4)$ vertices with perfect matchings, if $\Delta \left(T_1\right)>\Delta \left(T_2\right)$ and $\Delta \left(T_1\right)\ge ?\frac{k}{2}?+2$, then $\mu \left(T_1\right)>\mu \left(T_2\right)$.     

Constructions for optimal cyclic ternary constant-weight codes of weight four and distance six

A cyclic ${(n,d,w)}_q$ code is a $q$-ary cyclic code of length $n$, minimum Hamming distance $d$ and weight $w$. In this paper, we investigate cyclic ${(n,6,4)}_3$ codes. A new upper bound on $C{A}_3(n,6,4)$, the largest possible number of codewords in a cyclic ${(n,6,4)}_3$ code, is given. Two new constructions for optimal cyclic ${(n,6,4)}_3$ codes based on cyclic $(n,4,1)$ difference packings are presented. As a consequence, the exact value of $C{A}_3(n,6,4)$ is determined for any positive integer $n\equiv 0,6,18(mod24)$. We also obtain some other infinite classes of optimal cyclic ${(n,6,4)}_3$ codes.     

The indecomposable tournaments T with |W5(T)|=|T|−2

We consider a tournament $T=(V,A)$. For $X?V$, the subtournament of T induced by X is $T[X]=(X,A\cap (X\times X))$. An interval of T is a subset X of V such that, for $a,b\in X$ and $x\in V?X$, $(a,x)\in A$ if and only if $(b,x)\in A$. The trivial intervals of T are ?, $\{x\}(x\in V)$ and V. A tournament is indecomposable if all its intervals are trivial. For $n?2$, $W_{2n+1}$ denotes the unique indecomposable tournament defined on $\{0,\dots ,2n\}$ such that $W_{2n+1}[\{0,\dots ,2n?1\}]$ is the usual total order. Given an indecomposable tournament T, $W_5(T)$ denotes the set of $v\in V$ such that there is $W?V$ satisfying $v\in W$ and $T[W]$ is isomorphic to $W_5$. Latka [6] characterized the indecomposable tournaments T such that $W_5(T)=?$. The authors [1] proved that if $W_5(T)\ne ?$, then $|W_5(T)|?|V|?2$. In this note, we characterize the indecomposable tournaments T such that $|W_5(T)|=|V|?2$.