Combinatorics (math.CO)

Abstract: In this paper, we study some properties of persistent pairs in a discrete Morse function on a simplicial complex. As a simple corollary we improve discrete Morse inequalities. By using the properties, we explore the correlation between the number of strongly connected critical simplices between two distinct discrete Morse functions and the Betti number of a simple graph. This result gives an answer to the problem recently posed by King et al.

Abstract: Given a planar graph family $\mathcal{F}$, let ${\rm ex}_{\mathcal{P}}(n,\mathcal{F})$ and ${\rm spex}_{\mathcal{P}}(n,\mathcal{F})$ be the maximum size and maximum spectral radius over all $n$-vertex $\mathcal{F}$-free planar graphs, respectively. Let $tC_k$ be the disjoint union of $t$ copies of $k$-cycles, and $t\mathcal{C}$ be the family of $t$ vertex-disjoint cycles without length restriction. Tait and Tobin [Three conjectures in extremal spectral graph theory, J. Combin. Theory Ser. B 126 (2017) 137--161] determined that $K_2+P_{n-2}$ is the extremal spectral graph among all planar graphs with sufficiently large order $n$, which implies the extreme graphs of $spex_{\mathcal{P}}(n,tC_{\ell})$ and $spex_{\mathcal{P}}(n,t\mathcal{C})$ for $t\geq 3$ are $K_2+P_{n-2}$. In this paper, we first determine $spex_{\mathcal{P}}(n,tC_{\ell})$ and $spex_{\mathcal{P}}(n,t\mathcal{C})$ and characterize the unique extremal graph for $1\leq t\leq 2$, $\ell\geq 3$ and sufficiently large $n$. Secondly, we obtain the exact values of ${\rm ex}_{\mathcal{P}}(n,2C_4)$ and ${\rm ex}_{\mathcal{P}}(n,2\mathcal{C})$, which answers a conjecture of Li [Planar Tur\'an number of disjoint union of $C_3$ and $C_4$, arxiv:2212.12751v1 (2022)]. These present a new exploration of approaches and tools to investigate extremal problems of planar graphs.

Abstract: Two graphs are homomorphism indistinguishable over a graph class $\mathcal{F}$, denoted by $G \equiv_{\mathcal{F}} H$, if $\operatorname{hom}(F,G) = \operatorname{hom}(F,H)$ for all $F \in \mathcal{F}$ where $\operatorname{hom}(F,G)$ denotes the number of homomorphisms from $F$ to $G$. A classical result of Lov\'{a}sz shows that isomorphism between graphs is equivalent to homomorphism indistinguishability over the class of all graphs. More recently, there has been a series of works giving natural algebraic and/or logical characterizations for homomorphism indistinguishability over certain restricted graph classes. A class of graphs $\mathcal{F}$ is homomorphism-distinguishing closed if, for every $F \notin \mathcal{F}$, there are graphs $G$ and $H$ such that $G \equiv_{\mathcal{F}} H$ and $\operatorname{hom}(F,G) \neq \operatorname{hom}(F,H)$. Roberson conjectured that every class closed under taking minors and disjoint unions is homomorphism-distinguishing closed which implies that every such class defines a distinct equivalence relation between graphs. In this note, we confirm this conjecture for the classes $\mathcal{T}_k$, $k \geq 1$, containing all graphs of tree-width at most $k$.

Abstract: We consider twisted permutation codes, a class of frequency permutation arrays obtained from finite groups with multiple permutation representations of the same degree, introduced by Gillespie, Praeger and Spiga (and later studied by Akbari, Gillespie and Praeger), and develop a decoding algorithm for such codes based on earlier work of the first author for permutation group codes. In particular, we show how to implement this algorithm for an infinite family of groups considered by Akbari, Gillespie and Praeger.

Abstract: We discuss the problem of existence of latin squares without a substructure consisting of six elements $(r_1,c_2,l_3)$, $(r_2,c_3,l_1)$, $(r_3,c_1,l_2)$, $(r_2,c_1,l_3)$, $(r_3,c_2,l_1)$, $(r_1,c_3,l_2)$. Equivalently, the corresponding latin square graph does not have an induced subgraph isomorphic to $K_{3,3}$. The exhaustive search [Brouwer, Wanless. Universally noncommutative loops. 2011] says that there are no such latin squares of order from $3$ to $11$, and there are only two $K_{3,3}$-free latin squares of order $8$, up to equivalence. We repeat the search, establishing also the number of latin $m$-by-$n$ rectangles for each $m$ and $n$ less or equal to $11$. As a switched combination of two orthogonal latin squares of order $8$, we construct a $K_{3,3}$-free (universally noncommutative) latin square of order $16$. Keywords: latin square; transversal; trade; pattern avoiding; eigenfunction; universally noncommutative loops.

Abstract: The search for a highly discriminating and easily computable invariant to distinguish graphs remains a challenging research topic. Here we focus on cospectral graphs whose complements are also cospectral (generalized cospectral), and on coinvariant graphs (same Smith normal form) whose complements are also coinvariant (generalized coinvariant). We show a new characterization of generalized cospectral graphs in terms of codeterminantal graphs. We also establish the Smith normal form of some graph classes for certain associated matrices, and as an application, we prove that the Smith normal form can be used to uniquely determine star graphs. Finally, for graphs up to 10 vertices, we present enumeration results on the number of generalized cospectral graphs and generalized coinvariant graphs with respect to several associated matrices.