Combinatorics (math.CO)

Abstract: Cover-Incomparability graphs (C-I graphs) are an interesting class of graphs from posets. A C-I graph is a graph from a poset $P=(V,\le)$ with vertex set $V$, and the edge-set is the union of edge sets of the cover graph and the incomparability graph of the poset. The recognition of the C-I graphs is known to be NP-complete (Maxov\'{a} et al., Order 26(3), 229--236(2009)). In this paper, we prove that chordal graphs having at most two independent simplicial vertices are exactly the chordal graphs which are also C-I graphs. A similar result is obtained for cographs as well. Using the structural results of these graphs, we derive linear time recognition algorithms for chordal graphs and cographs, which are C-I graphs.

Abstract: Penrose tilings are the most famous aperiodic tilings, and they have been studied extensively. In particular, patterns composed with hexagons ($H$), boats ($B$) and stars ($S$) were soon exhibited and many physicists published on what they later called $HBS$ tilings, but no article or book combines all we know about them. This work is done here, before introducing new decorations and properties including explicit substitutions. For the latter, the star comes in three versions so we have 5 prototiles in what we call the Star tileset. Yet this set yields exactly the strict $HBS$ tilings formed using 3 tiles decorated with either the usual decorations (arrows) or Ammann bar markings for instance. Another new tileset called Gemstones is also presented, derived from the Star tileset.

Abstract: Given a graph $G$ and assuming that some vertices of $G$ are infected, the $r$-neighbor bootstrap percolation rule makes an uninfected vertex $v$ infected if $v$ has at least $r$ infected neighbors. The $r$-percolation number, $m(G, r)$, of $G$ is the minimum cardinality of a set of initially infected vertices in $G$ such that after continuously performing the $r$-neighbor bootstrap percolation rule each vertex of $G$ eventually becomes infected. In this paper, we consider the $3$-bootstrap percolation number of grids with fixed widths. If $G$ is the cartesian product $P_3 \square P_m$ of two paths of orders~$3$ and $m$, we prove that $m(G,3)=\frac{3}{2}(m+1)-1$, when $m$ is odd, and $m(G,3)=\frac{3}{2}m +1$, when $m$ is even. Moreover if $G$ is the cartesian product $P_5 \square P_m$, we prove that $m(G,3)=2m+2$, when $m$ is odd, and $m(G,3)=2m+3$, when $m$ is even. If $G$ is the cartesian product $P_4 \square P_m$, we prove that $m(G,3)$ takes on one of two possible values, namely $m(G,3) = \lfloor \frac{5(m+1)}{3} \rfloor + 1$ or $m(G,3) = \lfloor \frac{5(m+1)}{3} \rfloor + 2$.

Abstract: A Known Alder-type partition inequality of level $a$, which involves the second Rogers-Ramanujan identity when the level $a$ is 2, states that the number of partitions of $n$ into parts differing by at least $d$ with the smallest part being at least $a$ is greater than or equal to that of partitions of $n$ into parts congruent to $\pm a \pmod{d+3}$, excluding the part $d+3-a$. In this paper, we prove levels 2 and 3 Alder-type partition inequalities for all but a finite number of $d$, without requiring the exclusion of the part $d+3-a$ in the latter partition.

Abstract: We study a recursively defined two-parameter family of graphs which generalize Fibonacci cubes and Pell graphs and determine their basic structural and enumerative properties. In particular, we show that all of them are induced subgraphs of hypercubes and present their canonical decompositions. Further, we compute their metric invariants and establish some Hamiltonicity properties. We show that the new family inherits many useful properties of Fibonacci cubes and hence could be interesting for potential applications. We also compute the degree distribution, opening thus the way for computing many degree-based topological invariants. Several possible directions of further research are discussed in the concluding section.

Abstract: A simple graph on $n$ vertices may contain a lot of maximum cliques. But how many can it potentially contain? We will show that the maximum number of maximum cliques is taken over so-called cliqueful graphs, more specifically, later we will show that it is taken over saturated composite cliqueful graphs, if $n \ge 15$. Using this we will show that the graph that contains $3^{\lfloor n/3 \rfloor}c$ maxcliques has the most number of maxcliques on $n$ vertices, where $c\in\{1,\frac{4}{3},2\}$, depending on $n \text{ mod } 3$.

Abstract: We introduce higher-dimensional cubical sliding puzzles that are inspired by the classical 15 Puzzle from the 1880s. In our puzzles, on a $d$-dimensional cube, a labeled token can be slid from one vertex to another if it is topologically free to move on lower-dimensional faces. We analyze the solvability of these puzzles by studying how the puzzle graph changes with the number of labeled tokens vs empty vertices. We give characterizations of the different regimes ranging from being completely stuck (and thus all puzzles unsolvable) to having only one giant component where almost all puzzles can be solved. For the Cube, the Tesseract, and the Penteract ($5$-dimensional cube) we have implemented an algorithm to completely analyze their solvability and we provide specific puzzles for which we know the minimum number of moves needed to solve them.

Abstract: Let $r > 0$ be an integer, let $\mathbb{F}_q$ be a finite field of $q$ elements, and let $\mathcal{A}$ be a nonempty proper subset of $\mathbb{F}_q$. Moreover, let $\mathbf{M}$ be a random $m \times n$ rank-$r$ matrix over $\mathbb{F}_q$ taken with uniform distribution. We prove, in a precise sense, that, as $m, n \to +\infty$ and $r,q,\mathcal{A}$ are fixed, the number of entries of $\mathbf{M}$ that belong to $\mathcal{A}$ approaches a normal distribution.

Abstract: The \textit{(weak) chromatic number} of a hypergraph $H$, denoted by $\chi(H)$, is the smallest number of colors required to color the vertices of $H$ so that no hyperedge of $H$ is monochromatic. For every $2\le k\le d+1$, denote by $\chi_L(k,d)$ (resp. $\chi_{PL}(k,d)$) the supremum $\sup_H \chi(H)$ where $H$ runs over all finite $k$-uniform hypergraphs such that $H$ forms the collection of maximal faces of a simplicial complex that is linearly (resp. PL) embeddable in $\mathbb{R}^d$. Following the program by Heise, Panagiotou, Pikhurko and Taraz, we improve their results as follows: For $d \geq 3$, we show that A. $\chi_L(k,d)=\infty$ for all $2\le k\le d$, B. $\chi_{PL}(d+1,d)=\infty$ and C. $\chi_L(d+1,d)\ge 3$ for all odd $d\ge 3$. As an application, we extend the results by Lutz and M\o ller on the weak chromatic number of the $s$-dimensional faces in the triangulations of a fixed triangulable $d$-manifold $M$: D. $\chi_s(M)=\infty$ for $1\leq s \leq d$.

Abstract: It is known that the generating function associated with the enumeration of non-backtracking walks on finite graphs is a rational matrix-valued function of the parameter; such function is also closely related to graph-theoretical results such as Ihara's theorem and the zeta function on graphs. In [P. Grindrod, D. J. Higham, V. Noferini, The deformed graph Laplacian and its application to network centrality analysis, SIAM J. Matrix Anal. Appl. 39(1), 310--341, 2018], the radius of convergence of the generating function was studied for simple (i.e., undirected, unweighted and with no loops) graphs, and shown to depend on the number of cycles in the graph. In this paper, we use technologies from the theory of polynomial and rational matrices to greatly extend these results by studying the radius of convergence of the corresponding generating function for general, possibly directed and/or weighted, graphs. We give an analogous characterization of the radius of convergence for directed unweighted graphs, showing that it depends on the number of cycles in the undirectization of the graph. For weighted graphs, we provide for the first time an exact formula for the radius of convergence, improving a previous result that exhibited a lower bound. Finally, we consider also backtracking-downweighted walks on unweighted digraphs, and we prove a version of Ihara's theorem in that case.

Abstract: What is the minimum proportion of edges which must be added to or removed from a graph of density $p$ to eliminate all induced cycles of length $h$? The maximum of this quantity over all graphs of density $p$ is measured by the edit distance function, $\text{ed}_{\text{Forb}(C_h)}(p)$, a function which provides a natural metric between graphs and hereditary properties. Martin determined $\text{ed}_{\text{Forb}(C_h)}(p)$ for all $p \in [0,1]$ when $h \in \{3, \ldots, 9\}$ and determined $\text{ed}_{\text{Forb}(C_{10})}(p)$ for $p \in [1/7, 1]$. Peck determined $\text{ed}_{\text{Forb}(C_h)}(p)$ for all $p \in [0,1]$ for odd cycles, and for $p \in [ 1/\lceil h/3 \rceil, 1]$ for even cycles. In this paper, we fully determine the edit distance function for $C_{10}$ and $C_{12}$. Furthermore, we improve on the result of Peck for even cycles, by determining $\text{ed}_{\text{Forb}(C_h)}(p)$ for all $p \in [p_0, 1/\lceil h/3 \rceil ]$, where $p_0 \leq c/h^2$ for a constant $c$. More generally, if $C_h^t$ is the $t$-th power of the cycle $C_h$, we determine $\text{ed}_{\text{Forb}(C_h^t)}(p)$ for all $p \geq p_0$ in the case when $(t+1) \mid h$, thus improving on earlier work of Berikkyzy, Martin and Peck.

Abstract: Using the framework of pastures and foundations of matroids developed by Baker-Lorscheid, we give algorithms to: (i) compute the foundation of a matroid, and (ii) compute all morphisms between two pastures. Together, these provide an efficient method of solving many questions of interest in matroid representations, including orientability, non-representability, and computing all representations of a matroid over a finite field.