Combinatorics (math.CO)

Abstract: Given a graph $G$ and assuming that some vertices of $G$ are infected, the $r$-neighbor bootstrap percolation rule makes an uninfected vertex $v$ infected if $v$ has at least $r$ infected neighbors. The $r$-percolation number, $m(G,r)$, of $G$ is the minimum cardinality of a set of initially infected vertices in $G$ such that after continuously performing the $r$-neighbor bootstrap percolation rule each vertex of $G$ eventually becomes infected. In this paper, we consider percolation numbers of strong products of graphs. If $G$ is the strong product $G_1\boxtimes \cdots \boxtimes G_k$ of $k$ connected graphs, we prove that $m(G,r)=r$ as soon as $r\le 2^{k-1}$ and $|V(G)|\ge r$. As a dichotomy, we present a family of strong products of $k$ connected graphs with the $(2^{k-1}+1)$-percolation number arbitrarily large. We refine these results for strong products of graphs in which at least two factors have at least three vertices. In addition, when all factors $G_i$ have at least three vertices we prove that $m(G_1 \boxtimes \dots \boxtimes G_k,r)\leq 3^{k-1} -k$ for all $r\leq 2^k-1$, and we again get a dichotomy, since there exist families of strong products of $k$ graphs such that their $2^{k}$-percolation numbers are arbitrarily large. While $m(G\boxtimes H,3)=3$ if both $G$ and $H$ have at least three vertices, we also characterize the strong prisms $G\boxtimes K_2$ for which this equality holds. Some of the results naturally extend to infinite graphs, and we briefly consider percolation numbers of strong products of two-way infinite paths.

Abstract: Based on a construction iterating the line graph operator twice, the cycle double cover conjecture is proven in a constructive way using a perspective inspired by statistical mechanics and spin systems. In the resulting graph, deletion of specific subgraphs gives a union of cycles which via projection to the underlying graph results in a double cycle cover.

Abstract: We define an abelian group homomorphism $\mathscr{F}$, which we call the Frobenius transform, from the ring of symmetric functions to the ring of the symmetric power series. The matrix entries of $\mathscr{F}$ in the Schur basis are the restriction coefficients $r_\lambda^\mu = \dim \operatorname{Hom}_{\mathfrak{S}_n}(V_\mu, \mathbb{S}^\lambda \mathbb{C}^n)$, which are known to be nonnegative integers but have no known combinatorial interpretation. The Frobenius transform satisfies the identity $\mathscr{F}\{fg\} = \mathscr{F}\{f\} \ast \mathscr{F}\{g\}$, where $\ast$ is the Kronecker product. We prove for all symmetric functions $f$ that $\mathscr{F}\{f\} = \mathscr{F}_{\mathrm{Sur}}\{f\} \cdot (1 + h_1 + h_2 + \cdots)$, where $\mathscr{F}_{\mathrm{Sur}}\{f\}$ is a symmetric function with the same degree and leading term as $f$. Then, we compute the matrix entries of $\mathscr{F}_{\mathrm{Sur}}\{f\}$ and $\mathscr{F}^{-1}_{\mathrm{Sur}}\{f\}$ in the complete homogeneous, elementary, and power sum symmetric function bases, giving combinatorial interpretations of the coefficients where possible. In particular, the matrix entries of $\mathscr{F}^{-1}_{\mathrm{Sur}}\{f\}$ in the elementary basis count words with a constraint on their Lyndon factorization. As an example application of our main results, we prove that $r_\lambda^\mu = 0$ if the Young diagram of $\mu$ contains a square of side length greater than $2^{\lambda_1 - 1}$, and this inequality is tight.

Abstract: Given a digraph $D=(V,A)$ on $n$ vertices and a vertex $v\in V$, the cycle-degree of $v$ is the minimum size of a set $S \subseteq V(D) \setminus \{v\}$ intersecting every directed cycle of $D$ containing $v$. From this definition of cycle-degree, we define the $c$-degeneracy (or cycle-degeneracy) of $D$, which we denote by $\delta^*_c(D)$. It appears to be a nice generalisation of the undirected degeneracy. In this work, using this new definition of cycle-degeneracy, we extend several evidences for Cereceda's conjecture to digraphs. The $k$-dicolouring graph of $D$, denoted by $\mathcal{D}_k(D)$, is the undirected graph whose vertices are the $k$-dicolourings of $D$ and in which two $k$-dicolourings are adjacent if they differ on the colour of exactly one vertex. We show that $\mathcal{D}_k(D)$ has diameter at most $O_{\delta^*_c(D)}(n^{\delta^*_c(D) + 1})$ (respectively $O(n^2)$ and $(\delta^*_c(D)+1)$) when $k$ is at least $\delta^*_c(D)+2$ (respectively $\frac{3}{2}(\delta^*_c(D)+1)$ and $2(\delta^*_c(D)+1)$). This improves known results on digraph redicolouring (Bousquet et al.). Next, we extend a result due to Feghali to digraphs, showing that $\mathcal{D}_{d+1}(D)$ has diameter at most $O_{d,\epsilon}(n(\log n)^{d-1})$ when $D$ has maximum average cycle-degree at most $d-\epsilon$. We then show that two proofs of Bonamy and Bousquet for undirected graphs can be extended to digraphs. The first one uses the digrundy number of a digraph and the second one uses the $\mathscr{D}$-width. Finally, we give a general theorem which makes a connection between the recolourability of a digraph $D$ and the recolourability of its underlying graph $UG(D)$. This result directly extends a number of results on planar graph recolouring to planar digraph redicolouring.

Abstract: A proof of the first Rogers-Ramanujan identity is given using admissible neighborly partitions. This completes a program initiated by Mohsen and Mourtada. The admissible neighborly partitions involve an unusual mod 3 condition on the parts.

Abstract: For $A\subseteq \mathbb{R}$, let $A+A=\{a+b: a,b\in A\}$ and $AA=\{ab: a,b\in A\}$. For $k\in \mathbb{N}$, let $SP(k)$ denote the minimum value of $\max\{|A+A|, |AA|\}$ over all $A\subseteq \mathbb{N}$ with $|A|=k$. Here we establish $SP(k)=3k-3$ for $2\leq k \leq 7$, the $k=7$ case achieved for example by $\{1,2,3,4,6,8,12\}$, while $SP(k)=3k-2$ for $k=8,9$, the $k=9$ case achieved for example by $\{1,2,3,4,6,8,9,12,16\}$. For $4\leq k \leq 7$, we provide two proofs using different applications of Freiman's $3k-4$ theorem; one of the proofs includes extensive case analysis on the product sets of $k$-element subsets of $(2k-3)$-term arithmetic progressions. For $k=8,9$, we apply Freiman's $3k-3$ theorem for product sets, and investigate the sumset of the union of two geometric progressions with the same common ratio $r>1$, with separate treatments of the overlapping cases $r\neq 2$ and $r\geq 2$.

Abstract: The planar Tur\'an number, $ex_\mathcal{P}(n,H)$, is the maximum number of edges in an $n$-vertex planar graph which does not contain $H$ as a subgraph. The topic of extremal planar graphs was initiated by Dowden (2016). He obtained sharp upper bound for both $ex_\mathcal{P}(n,C_4)$ and $ex_\mathcal{P}(n,C_5)$. Later on, D. Ghosh et al. obtained sharp upper bound of $ex_\mathcal{P}(n,C_6)$ and proposed a conjecture on $ex_\mathcal{P}(n,C_k)$ for $k\geq 7$. In this paper, we give a sharp upper bound $ex_\mathcal{P}(n,C_7)\leq {18\over 7}n-{48\over 7}$, which satisfies the conjecture of D. Ghosh et al. It turns out that this upper bound is also sharp for $ex_\mathcal{P}(n,\{K_4,C_7\})$, the maximum number of edges in an $n$-vertex planar graph which does not contain $K_4$ or $C_7$ as a subgraph.

Abstract: Ruzsa asked whether there exist Fourier-uniform subsets of $\mathbb Z/N\mathbb Z$ with density $\alpha$ and 4-term arithmetic progression (4-APs) density at most $\alpha^C$, for arbitrarily large $C$. Gowers constructed Fourier uniform sets with density $\alpha$ and 4-AP density at most $\alpha^{4+c}$ for some small constant $c>0$. We show that an affirmative answer to Ruzsa's question would follow from the existence of an $N^{o(1)}$-coloring of $[N]$ without symmetrically colored 4-APs. For a broad and natural class of constructions of Fourier-uniform subsets of $\mathbb Z/N\mathbb Z$, we show that Ruzsa's question is equivalent to our arithmetic Ramsey question. We prove analogous results for all even-length APs. For each odd $k\geq 5$, we show that there exist $U^{k-2}$-uniform subsets of $\mathbb Z/N\mathbb Z$ with density $\alpha$ and $k$-AP density at most $\alpha^{c_k \log(1/\alpha)}$. We also prove generalizations to arbitrary one-dimensional patterns.