Combinatorics (math.CO)

Abstract: I show that we can assume graphs that do not have the edge-Erd\H{o}s-P\'{o}sa property to be connected. Then I strengthen this result to $2$-connectivity under the additional assumptions of a minor-closed property and a generic counterexample.

Abstract: For a finite abelian group $A$, define $f(A)$ to be the minimum integer such that for every complete digraph $\Gamma$ on $f$ vertices and every map $w:E(\Gamma) \rightarrow A$, there exists a directed cycle $C$ in $\Gamma$ such that $\sum_{e \in E(C)}w(e) = 0$. The study of $f(A)$ was initiated by Alon and Krivelevich (2021). In this article, we prove that $f(\mathbb{Z}_p^k) = O(pk (\log k)^2)$, where $p$ is prime, with an improved bound of $O(k \log k)$ when $p = 2$. These bounds are tight up to a factor which is polylogarithmic in $k$.

Abstract: In a recent article by Chapuy and Perarnau, it was shown that a uniformly chosen automaton on $n$ states with a $2$-letter alphabet has a synchronizing word of length $O(\sqrt{n}\log n)$ with high probability. In this note, we give a new simplified proof of a slightly weaker version of this statement. Our proof is based on two properties of random automata. First, by repeating a fixed character from the alphabet sufficiently many times in a row, the number of possible states reduces to, in expectation, $O(\sqrt{n})$. Second, with high probability, each pair of states can be synchronized by a word of length $O(\log n)$.

Abstract: We show that subcubic graphs of treewidth at least $2500$ do not have the edge-Erd\H{o}s-P\'{o}sa property.

Abstract: Every polyhedron can be decomposed into a Minkowski sum (or vector sum) of a bounded polyhedron and a polyhedral cone. This paper establishes similar statements for some classes of discrete sets in discrete convex analysis, such as integrally convex sets, L-natural-convex sets, and M-natural-convex sets.

Abstract: Do\v{s}li\'{c} et al. defined the Mostar index of a graph $G$ as $Mo(G)=\sum\limits_{uv\in E(G)}|n_G(u,v)-n_G(v,u)|$, where, for an edge $uv$ of $G$, the term $n_G(u,v)$ denotes the number of vertices of $G$ that have a smaller distance in $G$ to $u$ than to $v$. For a graph $G$ of order $n$ and maximum degree at most $\Delta$, we show $Mo(G)\leq \frac{\Delta}{2}n^2-(1-o(1))c_{\Delta}n\log(\log(n)),$ where $c_{\Delta}>0$ only depends on $\Delta$ and the $o(1)$ term only depends on $n$. Furthermore, for integers $n_0$ and $\Delta$ at least $3$, we show the existence of a $\Delta$-regular graph of order $n$ at least $n_0$ with $Mo(G)\geq \frac{\Delta}{2}n^2-c'_{\Delta}n\log(n),$ where $c'_{\Delta}>0$ only depends on $\Delta$.

Abstract: We classify the countable ultrahomogeneous 2-vertex-colored graphs in which the color classes are imprimitive, i.e., up to complementation they form disjoint unions of cliques. This generalizes work by Jenkinson, Lockett and Truss as well as Rose on ultrahomogeneous $n$-graphs. As the key aspect in such a classification, we identify a concept called piecewise ultrahomogeneity. We prove that there are two specific graphs whose occurrence essentially dictates whether a graph is piecewise ultrahomogeneous, and we exploit this fact to prove the classification.

Abstract: How many edges in an $n$-vertex graph will force the existence of a cycle with as many chords as it has vertices? Almost 30 years ago, Chen, Erd\H{o}s and Staton considered this question and showed that any $n$-vertex graph with $2n^{3/2}$ edges contains such a cycle. We significantly improve this old bound by showing that $\Omega(n\log^8n)$ edges are enough to guarantee the existence of such a cycle. Our proof exploits a delicate interplay between certain properties of random walks in almost regular expanders. We argue that while the probability that a random walk of certain length in an almost regular expander is self-avoiding is very small, one can still guarantee that it spans many edges (and that it can be closed into a cycle) with large enough probability to ensure that these two events happen simultaneously.

Abstract: We prove a weak version of the cross--product conjecture: ${F}(k+1,\ell) {F}(k,\ell+1) \geq (\frac12+\varepsilon) {F}(k,\ell) {F}(k+1,\ell+1)$, where ${F}(k,\ell)$ is the number of linear extensions for which the values at fixed elements $x,y,z$ are $k$ and $\ell$ apart, respectively, and where $\varepsilon>0$ depends on the poset. We also prove the converse inequality and disprove the {generalized cross--product conjecture}. The proofs use geometric inequalities for mixed volumes and combinatorics of words.

Abstract: A \textit{signed graph} $G_\phi$ consists of a graph $G$ along with a function $\phi$ that assigns a positive or negative weight to each edge. The reduced signed Laplacian matrix $L_{G_\phi}$ gives rise to a natural notion of chip-firing on $G_\phi$, as well as a critical group ${\mathcal K}(G_\phi)$. Here a negative edge designates an adversarial relationship, so that firing a vertex incident to such an edge leads to a loss of chips at both endpoints. We study chip-firing on signed graphs, employing the theory of chip-firing on invertible matrices introduced by Guzm\'an and Klivans. %Here valid chip configurations are given by the lattice points of a certain cone determined by $G_\phi$ and the underlying graph $G$. This gives rise to notions of \textit{critical} as well as \textit{$z$-superstable} configurations, both of which are counted by the determinant of $L_{G_\phi}$. We establish general results regarding these configurations, focusing on efficient methods of verifying the underlying properties. We then study the critical group of signed graphs in the context of vertex switching and Smith normal forms. We use this to compute the critical groups for various classes of signed graphs including signed cycles, wheels, complete graphs, and fans. In the process we generalize a number of results from the literature.