Combinatorics (math.CO)

Abstract: The first non-obvious case of Hadwiger's Conjecture states that every graph $G$ with chromatic number at least 4 has a $K_4$ minor. We give a new proof that derives the $K_4$ minor from a proper 3-coloring of a subgraph of $G$.

Abstract: This paper introduces the notion of a Galois point for a finite graph, using the theory of linear systems of divisors for graphs discovered by Baker and Norine. We present a new characterization of complete graphs in terms of Galois points.

Abstract: Bulgarian Solitaire is an interesting self-map on the set of integer partitions of a fixed number $n$. As a finite dynamical system, its long-term behavior is well-understood, having recurrent orbits parametrized by necklaces of beads with two colors black $B$ and white $W$. However, the behavior of the transient elements within each orbit is much less understood. Recent work of Pham considered the orbits corresponding to a family of necklaces $P^\ell$ that are concatenations of $\ell$ copies of a fixed primitive necklace $P$. She proved striking limiting behavior as $\ell$ goes to infinity: the level statistic for the orbit, counting how many steps it takes a partition to reach the recurrent cycle, has a limiting distribution, whose generating function $H_p(x)$ is rational. Pham also conjectured that $H_P(x), H_{P^*}(x)$ share the same denominator whenever $P^*$ is obtained from $P$ by reading it backwards and swapping $B$ for $W$. Here we introduce a new representation of Bulgarian Solitaire that is convenient for the study of these generating functions. We then use it to prove two instances of Pham's conjecture, showing that $$H_{BWBWB \cdots WB}(x)=H_{WBWBW \cdots BW}(x)$$ and that $H_{BWWW\cdots W}(x),H_{WBBB\cdots B}(x)$ share the same denominator.

Abstract: Let $G$ and $H$ be two vertex disjoint graphs. The {\em union} $G\cup H$ is the graph with $V(G\cup H)=V(G)\cup V(H)$ and $E(G\cup H)=E(G)\cup E(H)$. We use $P_k$ to denote a {\em path} on $k$ vertices, use {\em house} to denote the complement of $P_5$. In this paper, we show that $\chi(G)\le2\omega(G)$ if $G$ is ($P_3\cup P_2$, house)-free. Moreover, this bound is optimal when $\omega(G)\ge2$.

Abstract: Following up on our previous work, we study single-element extensions of transversal valuated matroids. We show that tropical presentations of valuated matroids with a minimal set of finite entries enjoy counterparts of the properties proved by Bonin and de Mier of minimal non-valuated transversal presentations.

Abstract: Let $P_{10}$ be a path on $10$ vertices. A graph is said to be $P_{10}$-free if it does not contain $P_{10}$ as an induced subgraph. The well-known Erd\H{o}s-Gy\'{a}rf\'{a}s Conjecture states that every graph with minimum degree at least three has a cycle whose length is a power of $2$. In this paper, we show that every $P_{10}$-free graph with minimum degree at least three contains a cycle of length $4$ or $8$. This implies that the conjecture is true for $P_{10}$-free graphs.

Abstract: This paper exploits adjacencies between the orbits of an ordered set P and a consequence of the classification of finite simple groups to, in many cases, exponentially bound the number of automorphisms. Results clearly identify the structures which currently prevent the proof of such an exponential bound, or which indeed inflate the number of automorphisms beyond such a bound. This is a first step towards a possible resolution of the Automorphism Conjecture for ordered sets.