Combinatorics (math.CO)

Abstract: A code $C$ is a subset of the vertex set of a graph and $C$ is $s$-neighbour-transitive if its automorphism group ${\rm Aut}(C)$ acts transitively on each of the first $s+1$ parts $C_0,C_1,\ldots,C_s$ of the distance partition $\{C=C_0,C_1,\ldots,C_\rho\}$, where $\rho$ is the covering radius of $C$. While codes have traditionally been studied in the Hamming and Johnson graphs, we consider here codes in the Kneser graphs. Let $\Omega$ be the underlying set on which the Kneser graph $K(n,k)$ is defined. Our first main result says that if $C$ is a $2$-neighbour-transitive code in $K(n,k)$ such that $C$ has minimum distance at least $5$, then $n=2k+1$ (i.e., $C$ is a code in an odd graph) and $C$ lies in a particular infinite family or is one particular sporadic example. We then prove several results when $C$ is a neighbour-transitive code in the Kneser graph $K(n,k)$. First, if ${\rm Aut}(C)$ acts intransitively on $\Omega$ we characterise $C$ in terms of certain parameters. We then assume that ${\rm Aut}(C)$ acts transitively on $\Omega$, first proving that if $C$ has minimum distance at least $3$ then either $K(n,k)$ is an odd graph or ${\rm Aut}(C)$ has a $2$-homogeneous (and hence primitive) action on $\Omega$. We then assume that $C$ is a code in an odd graph and ${\rm Aut}(C)$ acts imprimitively on $\Omega$ and characterise $C$ in terms of certain parameters. We give examples in each of these cases and pose several open problems.

Abstract: Let $R$ be a commutative ring with unity. The prime ideal sum graph of the ring $R$ is the simple undirected graph whose vertex set is the set of all nonzero proper ideals of $R$ and two distinct vertices $I$, $J$ are adjacent if and only if $I + J$ is a prime ideal of $R$. In this paper, we characterize all commutative Artinian rings whose prime ideal sum graphs are line graphs. Finally, we give a description of all commutative Artinian rings whose prime ideal sum graph is the complement of a line graph.

Abstract: A $(G,[k_1,\dots,k_t],\lambda)$ {\it partitioned difference family} (PDF) is a partition $\cal B$ of an additive group $G$ into sets ({\it blocks}) of sizes $k_1$, \dots, $k_t$, such that the list of differences of ${\cal B}$ covers exactly $\lambda$ times every non-zero element of $G$. It is called {\it Hadamard} (HPDF) if the order of $G$ is $2\lambda$. The study of HPDFs is motivated by the fact that each of them gives rise, recursively, to infinitely many other PDFs. Apart from the {\it elementary} HPDFs consisting of a Hadamard difference set and its complement, only one HPDF was known. In this article we present three new examples in several groups and we start a general investigation on the possible existence of HPDFs with assigned parameters by means of simple arguments.

Abstract: We prove that the set of matchings with a fixed number of unmatched vertices is Schur-positive with respect to the set of short chords. Two proofs are presented. The first proof applies a new combinatorial criterion for Schur-positivity, while the second is bijective. The coefficients in the Schur expansion are derived, and interpreted in terms of Bessel polynomials. We present a Knuth-like equivalence relation on matchings, and show that every equivalence class corresponds to an irreducible representation. We proceed to find various refined Schur-positive sets, including the set of matchings with a prescribed crossing number and the set of matchings with a given number of pairs of intersecting chords. Finally, we characterize all the matchings $m$ such that the set of matchings avoiding $m$ is Schur-positive.

Abstract: In 1999, Pitman and Stanley introduced the polytope bearing their name along with a study of its faces, lattice points, and volume. The Pitman-Stanley polytope is well-studied due to its connections to probability, parking functions, the generalized permutahedra, and flow polytopes. Its lattice points correspond to plane partitions of skew shape with entries 0 and 1. Pitman and Stanley remarked that their polytope can be generalized so that lattice points correspond to plane partitions of skew shape with entries $0,1, \ldots , m$. Since then, this generalization has been untouched. We study this generalization and show that it can also be realized as a flow polytope of a grid graph. We give multiple characterizations of its vertices in terms of plane partitions of skew shape and integer flows. For a fixed skew shape, we show that the number of vertices of this polytope is a polynomial in $m$ whose leading term, in certain cases, counts standard Young tableaux of a skew shifted shape. Moreover, we give formulas for the number of faces, as well as generating functions for the number of vertices.

Abstract: The $(n-\ell)$-deck of an $n$-vertex graph is the multiset of (unlabeled) subgraphs obtained from it by deleting $\ell$ vertices. An $n$-vertex graph is $\ell$-reconstructible if it is determined by its $(n-\ell)$-deck, meaning that no other graph has the same deck. We prove that every tree with at least $6\ell+11$ vertices is $\ell$-reconstructible.

Abstract: The containment game is a full information game for two players, initialised with a set of occupied vertices in an infinite connected graph $G$. On the $t$-th turn, the first player, called Spreader, extends the occupied set to $g(t)$ adjacent vertices, and then the second player, called Container, removes $q$ unoccupied vertices from the graph. If the spreading process continues perpetually -- Spreader wins, and otherwise -- Container wins. For $g=\infty$ this game reduces to a solitaire game for Container, known as the Firefighter Problem. On $\mathbb{Z}^2$, for $q=1/k$ and $g\equiv 1$ it is equivalent to Conway's Angel Problem. We introduce the game, and writing $q(G,g)$ for the set of $q$ values for which Container wins against a given $g(t)$, we study the minimal asymptotics of $g(t)$ such that $q(G,g)=q(G,\infty)$, i.e. for which defeating Spreader is as hard as winning the Firefighter Problem solitaire. We show, by providing explicit winning strategies, a sub-linear upper bound $g(t)=O(t^{6/7})$ and a lower bound of $g(t)=\Omega(t^{1/2})$.