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).     

A new approach to the chromatic number of the square of Kneser graph K(2k+1,k)

The vertices of Kneser graph $K(n,k)$ are the subsets of $\{1,2,\dots ,n\}$ of cardinality $k$, two vertices are adjacent if and only if they are disjoint. The square $G^2$ of a graph $G$ is defined on the vertex set of $G$ with two vertices adjacent if their distance in $G$ is at most 2. Z. Füredi, in 2002, proposed the problem of determining the chromatic number of the square of the Kneser graph. The first non-trivial problem arises when $n=2k+1$. It is believed that $\chi \left(K^2(2k+1,k)\right)=2k+c$ where $c$ is a constant, and yet the problem remains open. The best known upper bounds are by Kim and Park: $8k∕3+20∕3$ for 1$k\ge 3$ (Kim and Park, 2014) and $32k∕15+32$ for $k\ge 7$ (Kim and Park, 2016). In this paper, we develop a new approach to this coloring problem by employing graph homomorphisms, cartesian products of graphs, and linear congruences integrated with combinatorial arguments. These lead to $\chi \left(K^2(2k+1,k)\right)\le 5k∕2+c$, where $c$ is a constant in $\{5∕2,9∕2,5,6\}$, depending on $k\ge 2$.     

Latent voter model on locally tree-like random graphs

In the latent voter model, individuals who have just changed their choice have a latent period, which is exponential with rate $\lambda$, during which they will not change their opinion. We study this model on random graphs generated by a configuration model with degrees $3\le d\left(x\right)\le M$. We show that if the number of vertices $n\to \infty$ and $logn?{\lambda }_n?n$ then there is a quasi-stationary state in which each opinion has probability $\approx 1∕2$ and persists in this state for a time that is $\ge n^m$ for any $m<\infty$.     

Self-complementary magic squares of doubly even orders

A magic square $M$ in which the entries consist of consecutive integers from $1,2,\dots ,n^2$ is said to be self-complementary of order$n$ if the resulting square obtained from $M$ by replacing each entry $i$ by $n^2+1?i$ is equivalent to $M$ (under rotation or reflection). We present a new construction for self-complementary magic squares of order $n$ for each $n\ge 4$, where $n$ is a multiple of $4$.     

A note on two geometric paths with few crossings for points labeled by integers in the plane

Let $S$ be a set of $n$ points in the plane in general position such that the integers $1,2,\dots ,n$ are assigned to the points bijectively. Set $h$ be an integer with $1\le h<n(n+1)∕2$. In this paper we consider the problem of finding two vertex-disjoint simple geometric paths consisting of all points of $S$ such that the sum of labels of the points in one path is equal to $h$ and the paths have as few crossings as possible. We prove that there exists such a pair of paths with at most two crossings between them.     

Number of Crossing-Free Geometric Graphs vs. Triangulations

We show that there is a constant $\alpha >0$ such that, for any set P of n⩾ 5 points in general position in the plane, a crossing-free geometric graph on P that is chosen uniformly at random contains, in expectation, at least $(\frac{1}{2}+\alpha )M$ edges, where M denotes the number of edges in any triangulation of P. From this we derive (to our knowledge) the first non-trivial upper bound of the form $c^n\cdot \mathsf{tr}(P)$ on the number of crossing-free geometric graphs on P; that is, at most a fixed exponential in n times the number of triangulations of P. (The trivial upper bound of $2^M\cdot \mathsf{tr}(P)$, or $c=2^{M/n}$, follows by taking subsets of edges of each triangulation.) If the convex hull of P is triangular, then $M=3n-6$, and we obtain $c<7.98$.Upper bounds for the number of crossing-free geometric graphs on planar point sets have so far applied the trivial $8^n$ factor to the bound for triangulations; we slightly decrease this bound to $O({343.11}^n)$.     

A panconnectivity theorem for bipartite graphs

Let $G$ be a simple $m\times n$ bipartite graph with $m\ge n$. We prove that if the minimum degree of $G$ satisfies $\delta \left(G\right)\ge m∕2+1$, then $G$ is bipanconnected: for every pair of vertices $x,y$, and for every appropriate integer $2\le ?\le 2n$, there is an $x,y$-path of length $?$ in $G$.     

Lower bounds on Davenport–Schinzel sequences via rectangular Zarankiewicz matrices

An order-$s$Davenport–Schinzel sequence over an $n$-letter alphabet is one avoiding immediate repetitions and alternating subsequences with length $s+2$. The main problem is to determine the maximum length of such a sequence, as a function of $n$ and $s$. When $s$ is fixed this problem has been settled (see Agarwal, Sharir, and Shor, 1989, Nivasch, 2010 and Pettie, 2015) but when $s$ is a function of $n$, very little is known about the extremal function $\lambda (s,n)$ of such sequences.In this paper we give a new recursive construction of Davenport–Schinzel sequences that is based on dense 0–1matrices avoiding large all-1 submatrices (aka Zarankiewicz’s Problem ). In particular, we give a simple construction of $n^{2∕t}\times n$ matrices containing $n^{1+1∕t}$ 1s that avoid $t\times 2$ all-1 submatrices. (This result seems to be absent from the literature on Zarankiewicz’s problem, but it may be considered folklore among experts in this area [Z. Füredi, personal communication, 2017].)Our lower bounds on $\lambda (s,n)$ exhibit three qualitatively different behaviors depending on the size of $s$ relative to $n$. When $s\le loglogn$ we show that $\lambda (s,n)∕n\ge 2^s$ grows exponentially with $s$. When $s=n^{o\left(1\right)}$ we show $\lambda (s,n)∕n\ge {\left(\frac{s}{2log{log}_{s}n}\right)}^{log{log}_{s}n}$ grows faster than any polynomial in $s$. Finally, when $s=\Omega (n^{1∕t}(t?1)!)$, $\lambda (s,n)=\Omega (n^{2}s∕(t?1)!)$ matches the trivial upper bound $O\left(n^{2}s\right)$ asymptotically, whenever $t$ is constant.     

On packing of rectangles in a rectangle

It is known that ${\sum }_{i=1}^{\infty }1∕\left(i(i+1)\right)=1$. In 1968, Meir and Moser (1968) asked for finding the smallest $?$ such that all the rectangles of sizes $1∕i\times 1∕(i+1)$, $i\in \{1,2,\dots \}$, can be packed into a square or a rectangle of area $1+?$. First we show that in Paulhus (1997), the key lemma, as a statement, in the proof of the smallest published upper bound of the minimum area is false, then we prove a different new upper bound. We show that $?\le 1.26?10^{?9}$ if the rectangles are packed into a square and $?\le 6.878?10^{?10}$ if the rectangles are packed into a rectangle.     

A characterization of a class of hyperplanes of DW(2n−1,F)

A hyperplane of the symplectic dual polar space $DW(2n?1,\mathbb{F})$, $n\ge 2$, is said to be of subspace-type if it consists of all maximal singular subspaces of $W(2n?1,\mathbb{F})$ meeting a given $(n?1)$-dimensional subspace of $\text{PG}(2n?1,\mathbb{F})$. We show that a hyperplane of $DW(2n?1,\mathbb{F})$ is of subspace-type if and only if every hex $F$ of $DW(2n?1,\mathbb{F})$ intersects it in either $F$, a singular hyperplane of $F$ or the extension of a full subgrid of a quad. In the case $\mathbb{F}$ is a perfect field of characteristic 2, a stronger result can be proved, namely a hyperplane $H$ of $DW(2n?1,\mathbb{F})$ is of subspace-type or arises from the spin-embedding of $DW(2n?1,\mathbb{F})?DQ(2n,\mathbb{F})$ if and only if every hex $F$ intersects it in either $F$, a singular hyperplane of $F$, a hexagonal hyperplane of $F$ or the extension of a full subgrid of a quad.