Combinatorics (math.CO)

Abstract: Let $G=(V, E)$ be a graph where $V$ and $E$ are the vertex and edge sets, respectively. For two disjoint subsets $A$ and $B$ of $V$, we say $A$ \emph{dominates} $B$ if every vertex of $B$ is adjacent to at least one vertex of $A$. A vertex partition $\pi = \{V_1, V_2, \ldots, V_k\}$ of $G$ is called a \emph{transitive partition} of size $k$ if $V_i$ dominates $V_j$ for all $1\leq i<j\leq k$. In this article, we initiate the study of a generalization of transitive partition, namely \emph{$d_2$-transitive partition}. For two disjoint subsets $A$ and $B$ of $V$, we say $A$ \emph{$d_2$-dominates} $B$ if, for every vertex of $B$, there exists a vertex in $A$, such that the distance between them is at most two. A vertex partition $\pi = \{V_1, V_2, \ldots, V_k\}$ of $G$ is called a \emph{$d_2$-transitive partition} of size $k$ if $V_i$ $d_2$-dominates $V_j$ for all $1\leq i<j\leq k$. The maximum integer $k$ for which the above partition exists is called \emph{$d_2$-transitivity} of $G$, and it is denoted by $Tr_{d_2}(G)$. The \textsc{Maximum $d_2$-Transitivity Problem} is to find a $d_2$-transitive partition of a given graph with the maximum number of parts. We show that this problem can be solved in linear time for the complement of bipartite graphs and bipartite chain graphs. On the negative side, we prove that the decision version of the \textsc{Maximum $d_2$-Transitivity Problem} is NP-complete for split graphs, bipartite graphs, and star-convex bipartite graphs.

Abstract: It is known that the complete graph $K_n$ contains a pancyclic subgraph with $n+(1+o(1))\cdot \log _2 n$ edges, and that there is no pancyclic graph on $n$ vertices with fewer than $n+\log _2 (n-1) -1$ edges. We show that, with high probability, $G(n,p)$ contains a pancyclic subgraph with $n+(1+o(1))\log_2 n$ edges for $p \ge p^*$, where $p^*=(1+o(1))\ln n/n$, right above the threshold for pancyclicity.

Abstract: Near maximum distance separable (NMDS) codes are important in finite geometry and coding theory. Self-dual codes are closely related to combinatorics, lattice theory, and have important application in cryptography. In this paper, we construct a class of $q$-ary linear codes and prove that they are either MDS or NMDS which depends on certain zero-sum condition. In the NMDS case, we provide an effective approach to construct NMDS self-dual codes which largely extend known parameters of such codes. In particular, we proved that for square $q$, almost $q/8$ NMDS self-dual $q$-ary codes can be constructed.

Abstract: Given a graph $G$, when is it possible to reconstruct with high probability a uniformly random colouring of its vertices in $r$ colours from its $k$-deck, i.e. a set of its induced (coloured) subgraphs of size $k$? In this paper, we reconstruct random colourings of lattices and random graphs. Recently, Narayanan and Yap proved that, for $d=2$, with high probability a random colouring of vertices of a $d$-dimensional $n$-lattice ($n\times n$ grid) is reconstructibe from its deck of all $k$-subgrids ($k\times k$ grids) if $k\geq\sqrt{2\log_2 n}+\frac{3}{4}$ and is not reconstructible if $k<\sqrt{2\log_2 n}-\frac{1}{4}$. We prove that the same "two-point concentration" result for the minimum size of subgrids that determine the entire colouring holds true in any dimension $d\geq 2$. We also prove that with high probability a uniformly random $r$-colouring of the vertices of the random graph $G(n,1/2)$ is reconstructible from its full $k$-deck if $k\geq 2\log_2 n+8$ and is not reconstructible if $k\leq\sqrt{2\log_2 n}$. We further show that the colour reconstruction algorithm for random graphs can be modified and used for graph reconstruction: we prove that with high probability $G(n,1/2)$ is reconstructible from its full $k$-deck if $k\geq 2\log_2 n+11$ (while it is not reconstructible with high probability if $k\leq 2\sqrt{\log_2 n}$). This significantly improves the best known upper bound for the minimum size of subgraphs in a deck that can be used to reconstruct the random graph with high probability.

Abstract: Given a graph $G$, the number of its vertices is represented by $n(G)$, while the number of its edges is denoted as $m(G)$. An independent set in a graph is a set of vertices where no two vertices are adjacent to each other and the size of the maximum independent set is denoted by $\alpha(G)$. A matching in a graph refers to a set of edges where no two edges share a common vertex and the maximum matching size is denoted by $\mu(G)$. If $\alpha(G) + \mu(G) = n(G)$, then the graph $G$ is called a K\"{o}nig-Egerv\'{a}ry graph. Considering a graph $G$ with a degree sequence $d_1 \leq d_2 \leq \cdots \leq d_n$, the annihilation number $a(G)$ is defined as the largest integer $k$ such that the sum of the first $k$ degrees in the sequence is less than or equal to $m(G)$ (Pepper, 2004). It is a known fact that $\alpha(G)$ is less than or equal to $a(G)$ for any graph $G$. Our goal is to estimate the difference between these two parameters. Specifically, we prove a series of inequalities, including $a(G) - \alpha(G) \leq \frac{\mu(G) - 1}{2}$ for trees, $a(G) - \alpha(G) \leq 2 + \mu(G) - 2\sqrt{1 + \mu(G)}$ for bipartite graphs and $a(G) - \alpha(G) \leq \mu(G) - 2$ for K\"{o}nig-Egerv\'{a}ry graphs. Furthermore, we demonstrate that these inequalities serve as tight upper bounds for the difference between the annihilation and independence numbers, regardless of the assigned value for $\mu(G)$.

Abstract: We consider structural equation models (SEMs), in which every variable is a function of a subset of the other variables and a stochastic error. Each such SEM is naturally associated with a directed graph describing the relationships between variables. When the errors are homoscedastic, recent work has proposed methods for inferring the graph from observational data under the assumption that the graph is acyclic (i.e., the SEM is recursive). In this work, we study the setting of homoscedastic errors but allow the graph to be cyclic (i.e., the SEM to be non-recursive). Using an algebraic approach that compares matroids derived from the parameterizations of the models, we derive sufficient conditions for when two simple directed graphs generate different distributions generically. Based on these conditions, we exhibit subclasses of graphs that allow for directed cycles, yet are generically identifiable. We also conjecture a strengthening of our graphical criterion which can be used to distinguish many more non-complete graphs.

Abstract: The square coloring of a graph $G$ is a stronger version of proper vertex coloring, requiring additionally that any two distinct vertices with a common neighbor need to be colored differently. In this paper we prove that every planar graph with maximum degree at most $5$ admits a square coloring using at most $17$ colors, which improves the upper bound $18$ recently presented by Hou, Jin, Miao, and Zhao [Graphs and Combinatorics, 2023].