Abstract: We consider a non-monotone activation process $(X_t)_{t\in\{ 0,1,2,\ldots\}}$on a graph $G$, where $X_0\subseteq V(G)$, $X_t=\{ u\in V(G): N_G(u)\capX_{t-1} \geq \tau(u)\}$ for every positive integer $t$, and $\tau:V(G)\to\mathbb{Z}$ is a threshold function. The set $X_0$ is a so-called non-monotonetarget set for $(G,\tau)$ if there is some $t_0$ such that $X_t=V(G)$ for every$t\geq t_0$. Ben-Zwi, Hermelin, Lokshtanov, and Newman [Discrete Optimization 8(2011) 87-96] asked whether a target set of minimum order can be determinedefficiently if $G$ is a tree. We answer their question in the affirmative forthreshold functions $\tau$ satisfying $\tau(u)\in \{ 0,1,d_G(u)\}$ for everyvertex~$u$. For such restricted threshold functions, we give a characterizationof target sets that allows to show that the minimum target set problem remainsNP-hard for planar graphs of maximum degree $3$ but is efficiently solvable forgraphs of bounded treewidth. PubDate: Fri, 13 May 2022 14:38:55 +020
Abstract: Layered treewidth and row treewidth are recently introduced graph parametersthat have been key ingredients in the solution of several well-known openproblems. It follows from the definitions that the layered treewidth of a graphis at most its row treewidth plus 1. Moreover, a minor-closed class has boundedlayered treewidth if and only if it has bounded row treewidth. However, it hasbeen open whether row treewidth is bounded by a function of layered treewidth.This paper answers this question in the negative. In particular, for everyinteger $k$ we describe a graph with layered treewidth 1 and row treewidth $k$.We also prove an analogous result for layered pathwidth and row pathwidth. PubDate: Fri, 13 May 2022 14:35:08 +020
Abstract: We study the neighborhood polynomial and the complexity of its computationfor chordal graphs. The neighborhood polynomial of a graph is the generatingfunction of subsets of its vertices that have a common neighbor. We introduce aparameter for chordal graphs called anchor width and an algorithm to computethe neighborhood polynomial which runs in polynomial time if the anchor widthis polynomially bounded. The anchor width is the maximal number of differentsub-cliques of a clique which appear as a common neighborhood. Furthermore westudy the anchor width for chordal graphs and some subclasses such as chordalcomparability graphs and chordal graphs with bounded leafage. the leafage of achordal graphs is the minimum number of leaves in the host tree of a subtreerepresentation. We show that the anchor width of a chordal graph is at most$n^{\ell}$ where $\ell$ denotes the leafage. This shows that for somesubclasses computing the neighborhood polynomial is possible in polynomial timewhile it is NP-hard for general chordal graphs. PubDate: Fri, 06 May 2022 15:09:43 +020
Abstract: Given a graph and an integer $k$, it is an NP-complete problem to decidewhether there is a dominating set of size at most $k$. In this paper we studythis problem for the Kn\"odel Graph on $n$ vertices using elementary numbertheory techniques. In particular, we show an explicit upper bound for thedomination number of the Kn\"odel Graph on $n$ vertices any time that we canfind a prime number $p$ dividing $n$ for which $2$ is a primitive root. PubDate: Fri, 06 May 2022 15:06:07 +020
Abstract: Let $P$ be a set of $n\geq 3$ points in general position in the plane. Theedge disjointness graph $D(P)$ of $P$ is the graph whose vertices are all theclosed straight line segments with endpoints in $P$, two of which are adjacentin $D(P)$ if and only if they are disjoint. We show that the connectivity of$D(P)$ is at least$\binom{\lfloor\frac{n-2}{2}\rfloor}{2}+\binom{\lceil\frac{n-2}{2}\rceil}{2}$,and that this bound is tight for each $n\geq 3$. PubDate: Fri, 06 May 2022 15:01:53 +020
Abstract: The finite models of a universal sentence $\Phi$ in a finite relationalsignature are the age of a structure if and only if $\Phi$ has the jointembedding property. We prove that the computational problem whether a givenuniversal sentence $\Phi$ has the joint embedding property is undecidable, evenif $\Phi$ is additionally Horn and the signature of $\Phi$ only containsrelation symbols of arity at most two. PubDate: Fri, 06 May 2022 14:58:29 +020
Abstract: We consider the Erd\H{o}s-P\'osa property for immersions and topologicalminors in tournaments. We prove that for every simple digraph $H$, $k\in\mathbb{N}$, and tournament $T$, the following statements hold: (i) If in $T$ one cannot find $k$ arc-disjoint immersion copies of $H$, thenthere exists a set of $\mathcal{O}_H(k^3)$ arcs that intersects all immersioncopies of $H$ in $T$. (ii) If in $T$ one cannot find $k$ vertex-disjoint topological minor copiesof $H$, then there exists a set of $\mathcal{O}_H(k\log k)$ vertices thatintersects all topological minor copies of $H$ in $T$. This improves the results of Raymond [DMTCS '18], who proved similarstatements under the assumption that $H$ is strongly connected. PubDate: Tue, 05 Apr 2022 18:05:27 +020
Abstract: An equitable partition into branchings in a digraph is a partition of the arcset into branchings such that the sizes of any two branchings differ at most byone. For a digraph whose arc set can be partitioned into $k$ branchings, therealways exists an equitable partition into $k$ branchings. In this paper, wepresent two extensions of equitable partitions into branchings in digraphs:those into matching forests in mixed graphs; and into $b$-branchings indigraphs. For matching forests, Kir\'{a}ly and Yokoi (2022) considered atricriteria equitability based on the sizes of the matching forest, and thematching and branching therein. In contrast to this, we introduce asingle-criterion equitability based on the number of covered vertices, which isplausible in the light of the delta-matroid structure of matching forests.While the existence of this equitable partition can be derived from a lemma inKir\'{a}ly and Yokoi, we present its direct and simpler proof. For$b$-branchings, we define an equitability notion based on the size of the$b$-branching and the indegrees of all vertices, and prove that an equitablepartition always exists. We then derive the integer decomposition property ofthe associated polytopes. PubDate: Thu, 31 Mar 2022 16:27:13 +020
Abstract: A bramble in an undirected graph $G$ is a family of connected subgraphs of$G$ such that for every two subgraphs $H_1$ and $H_2$ in the bramble either$V(H_1) \cap V(H_2) \neq \emptyset$ or there is an edge of $G$ with oneendpoint in $V(H_1)$ and the second endpoint in $V(H_2)$. The order of thebramble is the minimum size of a vertex set that intersects all elements of abramble. Brambles are objects dual to treewidth: As shown by Seymour and Thomas, themaximum order of a bramble in an undirected graph $G$ equals one plus thetreewidth of $G$. However, as shown by Grohe and Marx, brambles of high ordermay necessarily be of exponential size: In a constant-degree $n$-vertexexpander a bramble of order $\Omega(n^{1/2+\delta})$ requires size exponentialin $\Omega(n^{2\delta})$ for any fixed $\delta \in (0,\frac{1}{2}]$. On theother hand, the combination of results of Grohe and Marx and Chekuri andChuzhoy shows that a graph of treewidth $k$ admits a bramble of order$\widetilde{\Omega}(k^{1/2})$ and size $\widetilde{\mathcal{O}}(k^{3/2})$.($\widetilde{\Omega}$ and $\widetilde{\mathcal{O}}$ hide polylogarithmicfactors and divisors, respectively.) In this note, we first sharpen the second bound by proving that every graph$G$ of treewidth at least $k$ contains a bramble of order$\widetilde{\Omega}(k^{1/2})$ and congestion $2$, i.e., every vertex of $G$ iscontained in at most two elements of the bramble (thus the bramble is of sizelinear in its order). Second, we provide a tight upper bound for the lowerbound of Grohe and Marx: For every $\delta \in (0,\frac{1}{2}]$, every graph$G$ of treewidth at least $k$ contains a bramble of order$\widetilde{\Omega}(k^{1/2+\delta})$ and size$2^{\widetilde{\mathcal{O}}(k^{2\delta})}$. PubDate: Thu, 31 Mar 2022 16:15:06 +020
Abstract: The determining number of a graph $G = (V,E)$ is the minimum cardinality of aset $S\subseteq V$ such that pointwise stabilizer of $S$ under the action of$Aut(G)$ is trivial. In this paper, we provide some improved upper and lowerbounds on the determining number of Kneser graphs. Moreover, we provide theexact value of the determining number for some subfamilies of Kneser graphs. PubDate: Wed, 30 Mar 2022 11:24:23 +020
Abstract: Let $k$ and $n$ be integers such that $1\leq k \leq n-1$, and let $G$ be asimple graph of order $n$. The $k$-token graph $F_k(G)$ of $G$ is the graphwhose vertices are the $k$-subsets of $V(G)$, where two vertices are adjacentin $F_k(G)$ whenever their symmetric difference is an edge of $G$. In thispaper we show that if $G$ is a tree, then the connectivity of $F_k(G)$ is equalto the minimum degree of $F_k(G)$. PubDate: Wed, 30 Mar 2022 11:20:29 +020
Abstract: This note defines a notion of multiplicity for nodes in a rooted tree andpresents an asymptotic calculation of the maximum multiplicity over all leavesin a Bienaym\'e-Galton-Watson tree with critical offspring distribution $\xi$,conditioned on the tree being of size $n$. In particular, we show that if $S_n$is the maximum multiplicity in a conditional Bienaym\'e-Galton-Watson tree,then $S_n = \Omega(\log n)$ asymptotically in probability and under the furtherassumption that ${\bf E}\{2^\xi\} < \infty$, we have $S_n = O(\log n)$asymptotically in probability as well. Explicit formulas are given for theconstants in both bounds. We conclude by discussing links with an alternatedefinition of multiplicity that arises in the root-estimation problem. PubDate: Wed, 30 Mar 2022 11:17:27 +020
Abstract: Motivated by the study of pattern avoidance in the context of permutationsand ordered partitions, we consider the enumeration of weak-ordering chainsobtained as leaves of certain restricted rooted trees. A tree of order $n$ isgenerated by inserting a new variable into each node at every step. A nodebecomes a leaf either after $n$ steps or when a certain stopping condition ismet. In this paper we focus on conditions of size 2 ($x=y$, $x PubDate: Mon, 21 Mar 2022 15:59:04 +010
Abstract: We assign a relational structure to any finite algebra in a canonical way,using solution sets of equations, and we prove that this relational structureis polymorphism-homogeneous if and only if the algebra itself ispolymorphism-homogeneous. We show that polymorphism-homogeneity is alsoequivalent to the property that algebraic sets (i.e., solution sets of systemsof equations) are exactly those sets of tuples that are closed under thecentralizer clone of the algebra. Furthermore, we prove that the aforementionedproperties hold if and only if the algebra is injective in the category of itsfinite subpowers. We also consider two additional conditions: a strongervariant for polymorphism-homogeneity and for injectivity, and we describeexplicitly the finite semilattices, lattices, Abelian groups and monounaryalgebras satisfying any one of these three conditions. PubDate: Mon, 21 Mar 2022 15:54:14 +010
Abstract: Initiated by Davis, Nelson, Petersen and Tenner (2018), the enumerative studyof pinnacle sets of permutations has attracted a fair amount of attentionrecently. In this article, we provide a recurrence that can be used to computeefficiently the number $ \mathfrak{S}_n(P) $ of permutations of size $n$ with agiven pinnacle set $P$, with arithmetic complexity $O(k^4 + k\log n)$ for $P$of size $k$. A symbolic expression can also be computed in this way forpinnacle sets of fixed size. A weighted sum $q_n(P)$ of $ \mathfrak{S}_n(P) $proposed in Davis, Nelson, Petersen and Tenner (2018) seems to have a simpleform, and a conjectural form is given recently by Flaque, Novelli and Thibon(2021+). We settle the problem by providing and proving an alternative form of$q_n(P)$, which has a strong combinatorial flavor. We also study admissibleorderings of a given pinnacle set, first considered by Rusu (2020) andcharacterized by Rusu and Tenner (2021), and we give an efficient algorithm fortheir counting. PubDate: Fri, 11 Mar 2022 14:00:56 +010
Abstract: The age $\mathcal{A}(G)$ of a graph $G$ (undirected and without loops) is thecollection of finite induced subgraphs of $G$, considered up to isomorphy andordered by embeddability. It is well-quasi-ordered (wqo) for this order if itcontains no infinite antichain. A graph is \emph{path-minimal} if it containsfinite induced paths of unbounded length and every induced subgraph $G'$ withthis property embeds $G$. We construct $2^{\aleph_0}$ path-minimal graphs whoseages are pairwise incomparable with set inclusion and which are wqo. Ourconstruction is based on uniformly recurrent sequences and lexicographical sumsof labelled graphs. PubDate: Tue, 08 Mar 2022 17:07:01 +010
Abstract: Let $G=(V(G),E(G))$ be a finite simple undirected graph with vertex set$V(G)$, edge set $E(G)$ and vertex subset $S\subseteq V(G)$. $S$ is termed\emph{open-dominating} if every vertex of $G$ has at least one neighbor in $S$,and \emph{open-independent, open-locating-dominating} (an $OLD_{oind}$-set forshort) if no two vertices in $G$ have the same set of neighbors in $S$, andeach vertex in $S$ is open-dominated exactly once by $S$. The problem ofdeciding whether or not $G$ has an $OLD_{oind}$-set has important applicationsthat have been reported elsewhere. As the problem is known to be$\mathcal{NP}$-complete, it appears to be notoriously difficult as we show thatits complexity remains the same even for just planar bipartite graphs ofmaximum degree five and girth six, and also for planar subcubic graphs of girthnine. Also, we present characterizations of both $P_4$-tidy graphs and thecomplementary prisms of cographs that have an $OLD_{oind}$-set. PubDate: Mon, 07 Feb 2022 11:59:48 +010
Abstract: Let asc and desc denote respectively the statistics recording the number of ascents or descents in a sequence having non-negative integer entries. In a recent paper by Andrews and Chern, it was shown that the distribution of asc on the inversion sequence avoidance class $I_n(\geq,\neq,>)$ is the same as that of $n-1-\text{asc}$ on the class $I_n(>,\neq,\geq)$, which confirmed an earlier conjecture of Lin. In this paper, we consider some further enumerative aspects related to this equivalence and, as a consequence, provide an alternative proof of the conjecture. In particular, we find recurrence relations for the joint distribution on $I_n(\geq,\neq,>)$ of asc and desc along with two other parameters, and do the same for $n-1-\text{asc}$ and desc on $I_n(>,\neq,\geq)$. By employing a functional equation approach together with the kernel method, we are able to compute explicitly the generating function for both of the aforementioned joint distributions, which extends (and provides a new proof of) the recent result $ I_n(\geq,\neq,>) = I_n(>,\neq,\geq) $. In both cases, an algorithm is formulated for computing the generating function of the asc distribution on members of each respective class having a fixed number of descents. PubDate: Mon, 07 Feb 2022 11:56:51 +010
Abstract: Hamiltonian cycles in graphs were first studied in the 1850s. Since then, animpressive amount of research has been dedicated to identifying classes ofgraphs that allow Hamiltonian cycles, and to related questions. Thecorresponding decision problem, that asks whether a given graph is Hamiltonian(i.\,e.\ admits a Hamiltonian cycle), is one of Karp's famous NP-completeproblems. In this paper we study graphs of bounded degree that are \emph{far}from being Hamiltonian, where a graph $G$ on $n$ vertices is \emph{far} frombeing Hamiltonian, if modifying a constant fraction of $n$ edges is necessaryto make $G$ Hamiltonian. We give an explicit deterministic construction of aclass of graphs of bounded degree that are locally Hamiltonian, but (globally)far from being Hamiltonian. Here, \emph{locally Hamiltonian} means that everysubgraph induced by the neighbourhood of a small vertex set appears in someHamiltonian graph. More precisely, we obtain graphs which differ in $\Theta(n)$edges from any Hamiltonian graph, but non-Hamiltonicity cannot be detected inthe neighbourhood of $o(n)$ vertices. Our class of graphs yields a class ofhard instances for one-sided error property testers with linear querycomplexity. It is known that any property tester (even with two-sided error)requires a linear number of queries to test Hamiltonicity (Yoshida, Ito, 2010).This is proved via a randomised construction of hard instances. In contrast,our construction is deterministic. So far only very few deterministicconstructions of hard instances for property testing are known. We believe thatour construction may lead to future insights in graph theory and towards acharacterisation of the properties that are testable in the bounded-degreemodel. PubDate: Mon, 31 Jan 2022 09:47:41 +010
Abstract: This paper studies three classes of cellular automata from a computational point of view: freezing cellular automata where the state of a cell can only decrease according to some order on states, cellular automata where each cell only makes a bounded number of state changes in any orbit, and finally cellular automata where each orbit converges to some fixed point. Many examples studied in the literature fit into these definitions, in particular the works on cristal growth started by S. Ulam in the 60s. The central question addressed here is how the computational power and computational hardness of basic properties is affected by the constraints of convergence, bounded number of change, or local decreasing of states in each cell. By studying various benchmark problems (short-term prediction, long term reachability, limits) and considering various complexity measures and scales (LOGSPACE vs. PTIME, communication complexity, Turing computability and arithmetical hierarchy) we give a rich and nuanced answer: the overall computational complexity of such cellular automata depends on the class considered (among the three above), the dimension, and the precise problem studied. In particular, we show that all settings can achieve universality in the sense of Blondel-Delvenne-K\r{u}rka, although short term predictability varies from NLOGSPACE to P-complete. Besides, the computability of limit configurations starting from computable initial configurations separates bounded-change from convergent cellular automata in dimension~1, but also dimension~1 versus higher dimensions for freezing cellular automata. Another surprising dimension-sensitive result obtained is that nilpotency becomes decidable in dimension~ 1 for all the three classes, while it stays undecidable even for freezing cellular automata in higher dimension. PubDate: Mon, 31 Jan 2022 09:44:09 +010
Abstract: The majorization relation orders the degree sequences of simple graphs intoposets called dominance orders. As shown by Ruch and Gutman (1979) and Merris(2002), the degree sequences of threshold and split graphs form upward-closedsets within the dominance orders they belong to, i.e., any degree sequencemajorizing a split or threshold sequence must itself be split or threshold,respectively. Motivated by the fact that threshold graphs and split graphs havecharacterizations in terms of forbidden induced subgraphs, we define a class$\mathcal{F}$ of graphs to be dominance monotone if whenever no realization of$e$ contains an element $\mathcal{F}$ as an induced subgraph, and $d$ majorizes$e$, then no realization of $d$ induces an element of $\mathcal{F}$. We presentconditions necessary for a set of graphs to be dominance monotone, and weidentify the dominance monotone sets of order at most 3. PubDate: Thu, 20 Jan 2022 17:56:54 +010
Abstract: Let $D$ be a strong balanced digraph on $2a$ vertices. Adamus et al. haveproved that $D$ is hamiltonian if $d(u)+d(v)\ge 3a$ whenever $uv\notin A(D)$and $vu\notin A(D)$. The lower bound $3a$ is tight. In this paper, we shallshow that the extremal digraph on this condition is two classes of digraphsthat can be clearly characterized. Moreover, we also show that if$d(u)+d(v)\geq 3a-1$ whenever $uv\notin A(D)$ and $vu\notin A(D)$, then $D$ istraceable. The lower bound $3a-1$ is tight. PubDate: Thu, 20 Jan 2022 17:52:09 +010
Abstract: In Defective Coloring we are given a graph $G$ and two integers $\chi_d$,$\Delta^*$ and are asked if we can $\chi_d$-color $G$ so that the maximumdegree induced by any color class is at most $\Delta^*$. We show that thisnatural generalization of Coloring is much harder on several basic graphclasses. In particular, we show that it is NP-hard on split graphs, even whenone of the two parameters $\chi_d$, $\Delta^*$ is set to the smallest possiblefixed value that does not trivialize the problem ($\chi_d = 2$ or $\Delta^* =1$). Together with a simple treewidth-based DP algorithm this completelydetermines the complexity of the problem also on chordal graphs. We thenconsider the case of cographs and show that, somewhat surprisingly, DefectiveColoring turns out to be one of the few natural problems which are NP-hard onthis class. We complement this negative result by showing that DefectiveColoring is in P for cographs if either $\chi_d$ or $\Delta^*$ is fixed; thatit is in P for trivially perfect graphs; and that it admits a sub-exponentialtime algorithm for cographs when both $\chi_d$ and $\Delta^*$ are unbounded. PubDate: Thu, 20 Jan 2022 17:47:09 +010
Abstract: A paired dominating set $P$ is a dominating set with the additional propertythat $P$ has a perfect matching. While the maximum cardainality of a minimaldominating set in a graph $G$ is called the upper domination number of $G$,denoted by $\Gamma(G)$, the maximum cardinality of a minimal paired dominatingset in $G$ is called the upper paired domination number of $G$, denoted by$\Gamma_{pr}(G)$. By Henning and Pradhan (2019), we know that$\Gamma_{pr}(G)\leq 2\Gamma(G)$ for any graph $G$ without isolated vertices. Wefocus on the graphs satisfying the equality $\Gamma_{pr}(G)= 2\Gamma(G)$. Wegive characterizations for two special graph classes: bipartite and unicyclicgraphs with $\Gamma_{pr}(G)= 2\Gamma(G)$ by using the results of Ulatowski(2015). Besides, we study the graphs with $\Gamma_{pr}(G)= 2\Gamma(G)$ and arestricted girth. In this context, we provide two characterizations: one forgraphs with $\Gamma_{pr}(G)= 2\Gamma(G)$ and girth at least 6 and the other for$C_3$-free cactus graphs with $\Gamma_{pr}(G)= 2\Gamma(G)$. We also pose thecharacterization of the general case of $C_3$-free graphs with $\Gamma_{pr}(G)=2\Gamma(G)$ as an open question. PubDate: Thu, 16 Dec 2021 14:15:54 +010
Abstract: Let $H=(V,F)$ be a simple hypergraph without loops. $H$ is called linear if$ f\cap g \le 1$ for any $f,g\in F$ with $f\not=g$. The $2$-section of $H$,denoted by $[H]_2$, is a graph with $V([H]_2)=V$ and for any $ u,v\inV([H]_2)$, $uv\in E([H]_2)$ if and only if there is $ f\in F$ such that $u,v\inf$. The treewidth of a graph is an important invariant in structural andalgorithmic graph theory. In this paper, we consider the treewidth of the$2$-section of a linear hypergraph. We will use the minimum degree, maximumdegree, anti-rank and average rank of a linear hypergraph to determine theupper and lower bounds of the treewidth of its $2$-section. Since for any graph$G$, there is a linear hypergraph $H$ such that $[H]_2\cong G$, we provide amethod to estimate the bound of treewidth of graph by the parameters of thehypergraph. PubDate: Thu, 09 Dec 2021 16:59:54 +010
Abstract: Fici, Restivo, Silva, and Zamboni define a $k$-antipower to be a wordcomposed of $k$ pairwise distinct, concatenated words of equal length. Bergerand Defant conjecture that for any sufficiently well-behaved aperiodic morphicword $w$, there exists a constant $c$ such that for any $k$ and any index $i$,a $k$-antipower with block length at most $ck$ starts at the $i$th position of$w$. They prove their conjecture in the case of binary words, and we extendtheir result to alphabets of arbitrary finite size and characterize those wordsfor which the result does not hold. We also prove their conjecture in thespecific case of the Fibonacci word. PubDate: Thu, 09 Dec 2021 16:53:04 +010
Abstract: A graph $G$ is $k$-$weighted-list-antimagic$ if for any vertex weighting$\omega\colon V(G)\to\mathbb{R}$ and any list assignment $L\colonE(G)\to2^{\mathbb{R}}$ with $ L(e) \geq E(G) +k$ there exists an edge labeling$f$ such that $f(e)\in L(e)$ for all $e\in E(G)$, labels of edges are pairwisedistinct, and the sum of the labels on edges incident to a vertex plus theweight of that vertex is distinct from the sum at every other vertex. In thispaper we prove that every graph on $n$ vertices having no $K_1$ or $K_2$component is $\lfloor{\frac{4n}{3}}\rfloor$-weighted-list-antimagic. An oriented graph $G$ is $k$-$oriented-antimagic$ if there exists aninjective edge labeling from $E(G)$ into $\{1,\dotsc, E(G) +k\}$ such that thesum of the labels on edges incident to and oriented toward a vertex minus thesum of the labels on edges incident to and oriented away from that vertex isdistinct from the difference of sums at every other vertex. We prove that everygraph on $n$ vertices with no $K_1$ component admits an orientation that is$\lfloor{\frac{2n}{3}}\rfloor$-oriented-antimagic. PubDate: Thu, 02 Dec 2021 16:23:48 +010
Abstract: We are given $n$ balls and an unknown coloring of them with two colors. Ourgoal is to find a ball that belongs to the larger color class, or show that thecolor classes have the same size. We can ask sets of $k$ balls as queries, andthe problem has different variants, according to what the answers to thequeries can be. These questions has attracted several researchers, but thefocus of most research was the adaptive version, where queries are decidedsequentially, after learning the answer to the previous query. Here we studythe non-adaptive version, where all the queries have to be asked at the sametime. PubDate: Fri, 26 Nov 2021 11:00:41 +010
Abstract: Boolean nested canalizing functions (NCFs) have important applications inmolecular regulatory networks, engineering and computer science. In this paper,we study their certificate complexity. For both Boolean values $b\in\{0,1\}$,we obtain a formula for $b$-certificate complexity and consequently, we developa direct proof of the certificate complexity formula of an NCF. Symmetry isanother interesting property of Boolean functions and we significantly simplifythe proofs of some recent theorems about partial symmetry of NCFs. We alsodescribe the algebraic normal form of $s$-symmetric NCFs. We obtain the generalformula of the cardinality of the set of $n$-variable $s$-symmetric BooleanNCFs for $s=1,\dots,n$. In particular, we enumerate the strongly asymmetricBoolean NCFs. PubDate: Fri, 26 Nov 2021 10:50:34 +010
Abstract: When can we compute the diameter of a graph in quasi linear time' We addressthis question for the class of {\em split graphs}, that we observe to be thehardest instances for deciding whether the diameter is at most two. We stressthat although the diameter of a non-complete split graph can only be either $2$or $3$, under the Strong Exponential-Time Hypothesis (SETH) we cannot computethe diameter of an $n$-vertex $m$-edge split graph in less than quadratic time-- in the size $n+m$ of the input. Therefore it is worth to study thecomplexity of diameter computation on {\em subclasses} of split graphs, inorder to better understand the complexity border. Specifically, we consider thesplit graphs with bounded {\em clique-interval number} and their complements,with the former being a natural variation of the concept of interval number forsplit graphs that we introduce in this paper. We first discuss the relationsbetween the clique-interval number and other graph invariants such as theclassic interval number of graphs, the treewidth, the {\em VC-dimension} andthe {\em stabbing number} of a related hypergraph. Then, in part based on theseabove relations, we almost completely settle the complexity of diametercomputation on these subclasses of split graphs: - For the $k$-clique-intervalsplit graphs, we can compute their diameter in truly subquadratic time if$k={\cal O}(1)$, and even in quasi linear time if $k=o(\log{n})$ and inaddition a corresponding ordering of the vertices in the clique is given.However, under SETH this cannot be done in truly subquadratic time for any $k =\omega(\log{n})$. - For the {\em complements} of $k$-clique-interval splitgraphs, we can compute their diameter in truly subquadratic time if $k={\calO}(1)$, and even in time ${\cal O}(km)$ if a corresponding ordering of thevertices in the stable set is given. Again this latter result is optimal underSETH up to polylogarithmic factors. Our findings raise the question whether a$k$-clique interval ordering can always be computed in quasi linear time. Weprove that it is the case for $k=1$ and for some subclasses such asbounded-treewidth split graphs, threshold graphs and comparability splitgraphs. Finally, we prove that some important subclasses of split graphs --including the ones mentioned above -- have a bounded clique-interval number. PubDate: Mon, 15 Nov 2021 11:16:07 +010
Abstract: In this paper, we prove a collection of results on graphical indices. Wedetermine the extremal graphs attaining the maximal generalized Wiener index(e.g. the hyper-Wiener index) among all graphs with given matching number orindependence number. This generalizes some work of Dankelmann, as well as somework of Chung. We also show alternative proofs for two recents results onmaximizing the Wiener index and external Wiener index by deriving it fromearlier results. We end with proving two conjectures. We prove that the maximumfor the difference of the Wiener index and the eccentricity is attained by thepath if the order $n$ is at least $9$ and that the maximum weighted Szegedindex of graphs of given order is attained by the balanced complete bipartitegraphs. PubDate: Mon, 15 Nov 2021 11:10:33 +010
Abstract: In this article we present theoretical and computational results on theexistence of polyhedral embeddings of graphs. The emphasis is on cubic graphs.We also describe an efficient algorithm to compute all polyhedral embeddings ofa given cubic graph and constructions for cubic graphs with some specialproperties of their polyhedral embeddings. Some key results are that even cubicgraphs with a polyhedral embedding on the torus can also have polyhedralembeddings in arbitrarily high genus, in fact in a genus {\em close} to thetheoretical maximum for that number of vertices, and that there is no bound onthe number of genera in which a cubic graph can have a polyhedral embedding.While these results suggest a large variety of polyhedral embeddings,computations for up to 28 vertices suggest that by far most of the cubic graphsdo not have a polyhedral embedding in any genus and that the ratio of thesegraphs is increasing with the number of vertices. PubDate: Fri, 05 Nov 2021 16:40:54 +010
Abstract: A function on an algebra is congruence preserving if, for any congruence, itmaps pairs of congruent elements onto pairs of congruent elements. We show thaton the algebra of binary trees whose leaves are labeled by letters of analphabet containing at least three letters, a function is congruence preservingif and only if it is polynomial. PubDate: Thu, 04 Nov 2021 09:44:33 +010
Abstract: A distributed graph algorithm is basically an algorithm where every node of agraph can look at its neighborhood at some distance in the graph and chose itsoutput. As distributed environment are subject to faults, an important issue isto be able to check that the output is correct, or in general that the networkis in proper configuration with respect to some predicate. One would like thischecking to be very local, to avoid using too much resources. Unfortunatelymost predicates cannot be checked this way, and that is where certificationcomes into play. Local certification (also known as proof-labeling schemes,locally checkable proofs or distributed verification) consists in assigninglabels to the nodes, that certify that the configuration is correct. There areseveral point of view on this topic: it can be seen as a part ofself-stabilizing algorithms, as labeling problem, or as a non-deterministicdistributed decision. This paper is an introduction to the domain of local certification, giving anoverview of the history, the techniques and the current research directions. PubDate: Wed, 15 Sep 2021 14:18:21 +020
Abstract: As a step towards resolving a question of Ru\v{s}kuc on the decidability ofjoint embedding for hereditary classes of permutations, which may be viewed asstructures in a language of 2 linear orders, we show the corresponding problemis undecidable for hereditary classes of structures in a language of 3 linearorders. PubDate: Tue, 14 Sep 2021 10:40:59 +020
Abstract: In the $d$-dimensional hypercube bin packing problem, a given list of$d$-dimensional hypercubes must be packed into the smallest number of hypercubebins. Epstein and van Stee [SIAM J. Comput. 35 (2005)] showed that theasymptotic performance ratio $\rho$ of the online bounded space variant is$\Omega(\log d)$ and $O(d/\log d)$, and conjectured that it is $\Theta(\logd)$. We show that $\rho$ is in fact $\Theta(d/\log d)$, using probabilisticarguments. PubDate: Tue, 14 Sep 2021 10:37:20 +020
Abstract: A subset $A \subset \mathbb R^2$ is said to avoid distance $1$ if: $\forallx,y \in A, \left\ x-y \right\ _2 \neq 1.$ In this paper we study the number$m_1(\mathbb R^2)$ which is the supremum of the upper densities of measurablesets avoiding distance 1 in the Euclidean plane. Intuitively, $m_1(\mathbbR^2)$ represents the highest proportion of the plane that can be filled by aset avoiding distance 1. This parameter is related to the fractional chromaticnumber $\chi_f(\mathbb R^2)$ of the plane. We establish that $m_1(\mathbb R^2) \leq 0.25647$ and $\chi_f(\mathbb R^2)\geq 3.8991$. PubDate: Tue, 31 Aug 2021 18:35:13 +020
Abstract: Defant, Engen, and Miller defined a permutation to be uniquely sorted if ithas exactly one preimage under West's stack-sorting map. We enumerate classesof uniquely sorted permutations that avoid a pattern of length three and apattern of length four by establishing bijections between these classes andvarious lattice paths. This allows us to prove nine conjectures of Defant. PubDate: Tue, 31 Aug 2021 09:30:13 +020
Abstract: We show that, with the exception of the words $a^2ba^2$ and $b^2ab^2$, all(finite or infinite) binary patterns in the Prouhet-Thue-Morse sequence canactually be found in that sequence as segments (up to exchange of letters inthe infinite case). This result was previously attributed to unpublished workby D. Guaiana and may also be derived from publications of A. Shur onlyavailable in Russian. We also identify the (finitely many) finite binarypatterns that appear non trivially, in the sense that they are obtained byapplying an endomorphism that does not map the set of all segments of thesequence into itself. PubDate: Mon, 30 Aug 2021 14:58:00 +020
Abstract: An outer-1-planar graph is a graph admitting a drawing in the plane so thatall vertices appear in the outer region of the drawing and every edge crossesat most one other edge. This paper establishes the local structure ofouter-1-planar graphs by proving that each outer-1-planar graph contains one ofthe seventeen fixed configurations, and the list of those configurations isminimal in the sense that for each fixed configuration there existouter-1-planar graphs containing this configuration that do not contain any ofanother sixteen configurations. There are two interesting applications of thisstructural theorem. First of all, we conclude that every (resp. maximal)outer-1-planar graph of minimum degree at least 2 has an edge with the sum ofthe degrees of its two end-vertices being at most 9 (resp. 7), and this upperbound is sharp. On the other hand, we show that the list 3-dynamic chromaticnumber of every outer-1-planar graph is at most 6, and this upper bound is bestpossible. PubDate: Fri, 27 Aug 2021 08:57:03 +020
Abstract: The Hausdorff distance is a relatively new measure of similarity of graphs.The notion of the Hausdorff distance considers a special kind of a commonsubgraph of the compared graphs and depends on the structural propertiesoutside of the common subgraph. There was no known efficient algorithm for theproblem of determining the Hausdorff distance between two trees, and in thispaper we present a polynomial-time algorithm for it. The algorithm is recursiveand it utilizes the divide and conquer technique. As a subtask it also uses theprocedure that is based on the well known graph algorithm of finding themaximum bipartite matching. PubDate: Thu, 19 Aug 2021 17:29:10 +020
Abstract: A family S of convex sets in the plane defines a hypergraph H = (S, E) asfollows. Every subfamily S' of S defines a hyperedge of H if and only if thereexists a halfspace h that fully contains S' , and no other set of S is fullycontained in h. In this case, we say that h realizes S'. We say a set S isshattered, if all its subsets are realized. The VC-dimension of a hypergraph His the size of the largest shattered set. We show that the VC-dimension forpairwise disjoint convex sets in the plane is bounded by 3, and this is tight.In contrast, we show the VC-dimension of convex sets in the plane (notnecessarily disjoint) is unbounded. We provide a quadratic lower bound in thenumber of pairs of intersecting sets in a shattered family of convex sets inthe plane. We also show that the VC-dimension is unbounded for pairwisedisjoint convex sets in R^d , for d> 2. We focus on, possibly intersecting,segments in the plane and determine that the VC-dimension is always at most 5.And this is tight, as we construct a set of five segments that can beshattered. We give two exemplary applications. One for a geometric set coverproblem and one for a range-query data structure problem, to motivate ourfindings. PubDate: Thu, 19 Aug 2021 17:24:12 +020
Abstract: Two permutation classes, the X-class and subpermutations of the increasingoscillation are shown to exhibit an exponential Wilf-collapse. This means thatthe number of distinct enumerations of principal subclasses of each of theseclasses grows much more slowly than the class itself whereas a priori, basedonly on symmetries of the class, there is no reason to expect this. Theunderlying cause of the collapse in both cases is the ability to apply someform of local symmetry which, combined with a greedy algorithm for detectingpatterns in these classes, yields a Wilf-collapse. PubDate: Thu, 19 Aug 2021 17:18:29 +020
Abstract: The dynamics of certain combinatorial actions and their liftings to actionsat the piecewise-linear and birational level have been studied lately with aneye towards questions of periodicity, orbit structure, and invariants. One keyproperty enjoyed by the rowmotion operator on certain finite partially-orderedsets is homomesy, where the average value of a statistic is the same for allorbits. To prove refined versions of homomesy in the product of two chainposets, J. Propp and the second author used an equivariant bijection discovered(less formally) by R. Stanley and H. Thomas. We explore the lifting of this "Stanley--Thomas word" to thepiecewise-linear, birational, and noncommutative realms. Although the map is nolonger a bijection, so cannot be used to prove periodicity directly, it stillgives enough information to prove the homomesy at the piecewise-linear andbirational levels (a result previously shown by D. Grinberg, S. Hopkins, and S.Okada). Even at the noncommutative level, the Stanley--Thomas word of a posetlabeling rotates cyclically with the lifting of antichain rowmotion. Along theway we give some formulas for noncommutative antichain rowmotion that we hopewill be first steps towards proving the conjectured periodicity at this level. PubDate: Wed, 18 Aug 2021 09:18:26 +020
Abstract: In this paper, we enumerate Dumont permutations of the fourth kind avoidingor containing certain permutations of length 4. We also conjecture aWilf-equivalence of two 4-letter patterns on Dumont permutations of the firstkind. PubDate: Tue, 06 Jul 2021 14:35:41 +020
Abstract: A dominating set $D$ of a graph $G$ without isolated vertices is calledsemipaired dominating set if $D$ can be partitioned into $2$-element subsetssuch that the vertices in each set are at distance at most $2$. The semipaireddomination number, denoted by $\gamma_{pr2}(G)$ is the minimum cardinality of asemipaired dominating set of $G$. Given a graph $G$ with no isolated vertices,the \textsc{Minimum Semipaired Domination} problem is to find a semipaireddominating set of $G$ of cardinality $\gamma_{pr2}(G)$. The decision version ofthe \textsc{Minimum Semipaired Domination} problem is already known to beNP-complete for chordal graphs, an important graph class. In this paper, weshow that the decision version of the \textsc{Minimum Semipaired Domination}problem remains NP-complete for split graphs, a subclass of chordal graphs. Onthe positive side, we propose a linear-time algorithm to compute a minimumcardinality semipaired dominating set of block graphs. In addition, we provethat the \textsc{Minimum Semipaired Domination} problem is APX-complete forgraphs with maximum degree $3$. PubDate: Tue, 06 Jul 2021 14:30:51 +020
Abstract: A skew shape is the difference of two top-left justified Ferrers shapessharing the same top-left corner. We study integer fillings of skew shapes. Asour first main result, we show that for a specific hereditary class of skewshapes, which we call D-free shapes, the fillings that avoid a north-east chainof size $k$ are in bijection with fillings that avoid a south-east chain of thesame size. Since Ferrers shapes are a subclass of D-free shapes, this resultcan be seen as a generalization of previous analogous results for Ferrersshapes. As our second main result, we construct a bijection between 01-fillings of anarbitrary skew shape that avoid a south-east chain of size 2, and the01-fillings of the same shape that simultaneously avoid a north-east chain ofsize 2 and a particular non-square subfilling. This generalizes a previousresult for transversal fillings. PubDate: Fri, 18 Jun 2021 14:31:44 +020
Abstract: We consider weighted tree automata (wta) over strong bimonoids and theirinitial algebra semantics and their run semantics. There are wta for whichthese semantics are different; however, for bottom-up deterministic wta and forwta over semirings, the difference vanishes. A wta is crisp-deterministic if itis bottom-up deterministic and each transition is weighted by one of the unitelements of the strong bimonoid. We prove that the class of weighted treelanguages recognized by crisp-deterministic wta is the same as the class ofrecognizable step mappings. Moreover, we investigate the following twocrisp-determinization problems: for a given wta ${\cal A}$, (a) does thereexist a crisp-deterministic wta which computes the initial algebra semantics of${\cal A}$ and (b) does there exist a crisp-deterministic wta which computesthe run semantics of ${\cal A}$' We show that the finiteness of the Nerodealgebra ${\cal N}({\cal A})$ of ${\cal A}$ implies a positive answer for (a),and that the finite order property of ${\cal A}$ implies a positive answer for(b). We show a sufficient condition which guarantees the finiteness of ${\calN}({\cal A})$ and a sufficient condition which guarantees the finite orderproperty of ${\cal A}$. Also, we provide an algorithm for the construction ofthe crisp-deterministic wta according to (a) if ${\cal N}({\cal A})$ is finite,and similarly for (b) if ${\cal A}$ has finite order property. We prove that itis undecidable whether an arbitrary wta ${\cal A}$ is crisp-determinizable. Wealso prove that both, the finiteness of ${\cal N}({\cal A})$ and the finiteorder property of ${\cal A}$ are undecidable. PubDate: Tue, 15 Jun 2021 09:40:34 +020
Abstract: Edmonds, Lov\'asz, and Pulleyblank showed that if a matching covered graphhas a nontrivial tight cut, then it also has a nontrivial ELP-cut. Carvalho etal. gave a stronger conjecture: if a matching covered graph has a nontrivialtight cut $C$, then it also has a nontrivial ELP-cut that does not cross $C$.Chen, et al gave a proof of the conjecture. This note is inspired by the paperof Carvalho et al. We give a simplified proof of the conjecture, and prove thefollowing result which is slightly stronger than the conjecture: if anontrivial tight cut $C$ of a matching covered graph $G$ is not an ELP-cut,then there is a sequence $G_1=G, G_2,\ldots,G_r, r\geq2$ of matching coveredgraphs, such that for $i=1, 2,\ldots, r-1$, $G_i$ has an ELP-cut $C_i$, and$G_{i+1}$ is a $C_i$-contraction of $G_i$, and $C$ is a $2$-separation cut of$G_r$. PubDate: Mon, 14 Jun 2021 11:51:56 +020
Abstract: We introduce and study the Bicolored $P_3$ Deletion problem defined asfollows. The input is a graph $G=(V,E)$ where the edge set $E$ is partitionedinto a set $E_r$ of red edges and a set $E_b$ of blue edges. The question iswhether we can delete at most $k$ edges such that $G$ does not contain abicolored $P_3$ as an induced subgraph. Here, a bicolored $P_3$ is a path onthree vertices with one blue and one red edge. We show that Bicolored $P_3$Deletion is NP-hard and cannot be solved in $2^{o( V + E )}$ time onbounded-degree graphs if the ETH is true. Then, we show that Bicolored $P_3$Deletion is polynomial-time solvable when $G$ does not contain a bicolored$K_3$, that is, a triangle with edges of both colors. Moreover, we provide apolynomial-time algorithm for the case that $G$ contains no blue $P_3$, red$P_3$, blue $K_3$, and red $K_3$. Finally, we show that Bicolored $P_3$Deletion can be solved in $ O(1.84^k\cdot V \cdot E )$ time and that itadmits a kernel with $ O(k\Delta\min(k,\Delta))$ vertices, where $\Delta$ isthe maximum degree of $G$. PubDate: Tue, 08 Jun 2021 10:23:01 +020
Abstract: Fix a finite undirected graph $\Gamma$ and a vertex $v$ of $\Gamma$. Let $E$be the set of edges of $\Gamma$. We call a subset $F$ of $E$ pandemic if eachedge of $\Gamma$ has at least one endpoint that can be connected to $v$ by an$F$-path (i.e., a path using edges from $F$ only). In 1984, Elser showed thatthe sum of $\left(-1\right)^{\left F\right }$ over all pandemic subsets $F$ of$E$ is $0$ if $E\neq \varnothing$. We give a simple proof of this result via asign-reversing involution, and discuss variants, generalizations andrefinements, revealing connections to abstract convexity (the notion of anantimatroid) and discrete Morse theory. PubDate: Thu, 03 Jun 2021 11:41:13 +020
Abstract: Binary relations derived from labeled rooted trees play an import role inmathematical biology as formal models of evolutionary relationships. The(symmetrized) Fitch relation formalizes xenology as the pairs of genesseparated by at least one horizontal transfer event. As a naturalgeneralization, we consider symmetrized Fitch maps, that is, symmetric maps$\varepsilon$ that assign a subset of colors to each pair of vertices in $X$and that can be explained by a tree $T$ with edges that are labeled withsubsets of colors in the sense that the color $m$ appears in $\varepsilon(x,y)$if and only if $m$ appears in a label along the unique path between $x$ and $y$in $T$. We first give an alternative characterization of the monochromatic caseand then give a characterization of symmetrized Fitch maps in terms ofcompatibility of a certain set of quartets. We show that recognition ofsymmetrized Fitch maps is NP-complete. In the restricted case where$ \varepsilon(x,y) \leq 1$ the problem becomes polynomial, since such mapscoincide with class of monochromatic Fitch maps whose graph-representationsform precisely the class of complete multi-partite graphs. PubDate: Thu, 03 Jun 2021 11:37:26 +020
Abstract: Let $G$ be a connected graph of order $n$.The Wiener index $W(G)$ of $G$ isthe sum of the distances between all unordered pairs of vertices of $G$. Inthis paper we show that the well-known upper bound $\big(\frac{n}{\delta+1}+2\big) {n \choose 2}$ on the Wiener index of a graph oforder $n$ and minimum degree $\delta$ [M. Kouider, P. Winkler, Mean distanceand minimum degree. J. Graph Theory 25 no. 1 (1997)] can be improvedsignificantly if the graph contains also a vertex of large degree.Specifically, we give the asymptotically sharp bound $W(G) \leq{n-\Delta+\delta \choose 2} \frac{n+2\Delta}{\delta+1}+ 2n(n-1)$ on the Wienerindex of a graph $G$ of order $n$, minimum degree $\delta$ and maximum degree$\Delta$. We prove a similar result for triangle-free graphs, and we determinea bound on the Wiener index of $C_4$-free graphs of given order, minimum andmaximum degree and show that it is, in some sense, best possible. PubDate: Thu, 03 Jun 2021 11:31:33 +020
Abstract: This paper introduces a notion of equivalence for higher-dimensionalautomata, called weak equivalence. Weak equivalence focuses mainly on atraditional trace language and a new homology language, which captures theoverall independence structure of an HDA. It is shown that weak equivalence iscompatible with both the tensor product and the coproduct of HDAs and that,under certain conditions, HDAs may be reduced to weakly equivalent smaller onesby merging and collapsing cubes. PubDate: Tue, 18 May 2021 11:47:50 +020
Abstract: Flip-sort is a natural sorting procedure which raises fascinatingcombinatorial questions. It finds its roots in the seminal work of Knuth onstack-based sorting algorithms and leads to many links with permutationpatterns. We present several structural, enumerative, and algorithmic resultson permutations that need few (resp. many) iterations of this procedure to besorted. In particular, we give the shape of the permutations after oneiteration, and characterize several families of permutations related to thebest and worst cases of flip-sort. En passant, we also give some links betweenpop-stack sorting, automata, and lattice paths, and introduce several tacticsof bijective proofs which have their own interest. PubDate: Fri, 30 Apr 2021 10:26:14 +020
Abstract: A mixed dominating set is a collection of vertices and edges that dominatesall vertices and edges of a graph. We study the complexity of exact andparameterized algorithms for \textsc{Mixed Dominating Set}, resolving some openquestions. In particular, we settle the problem's complexity parameterized bytreewidth and pathwidth by giving an algorithm running in time $O^*(5^{tw})$(improving the current best $O^*(6^{tw})$), as well as a lower bound showingthat our algorithm cannot be improved under the Strong Exponential TimeHypothesis (SETH), even if parameterized by pathwidth (improving a lower boundof $O^*((2 - \varepsilon)^{pw})$). Furthermore, by using a simple but so faroverlooked observation on the structure of minimal solutions, we obtainbranching algorithms which improve both the best known FPT algorithm for thisproblem, from $O^*(4.172^k)$ to $O^*(3.510^k)$, and the best knownexponential-time exact algorithm, from $O^*(2^n)$ and exponential space, to$O^*(1.912^n)$ and polynomial space. PubDate: Fri, 30 Apr 2021 10:23:11 +020
Abstract: Let $\lambda$ be a partition with no more than $n$ parts. Let $\beta$ be aweakly increasing $n$-tuple with entries from $\{ 1, ... , n \}$. The flaggedSchur function in the variables $x_1, ... , x_n$ that is indexed by $\lambda$and $\beta$ has been defined to be the sum of the content weight monomials forthe semistandard Young tableaux of shape $\lambda$ whose values are row-wisebounded by the entries of $\beta$. Gessel and Viennot gave a determinantexpression for the flagged Schur function indexed by $\lambda$ and $\beta$;this could be done since the pair $(\lambda, \beta)$ satisfied their"nonpermutable" condition for the sequence of terminals of an $n$-tuple oflattice paths that they used to model the tableaux. We generalize flagged Schurfunctions by dropping the requirement that $\beta$ be weakly increasing. Thenfor each $\lambda$ we give a condition on the entries of $\beta$ for the pair$(\lambda, \beta)$ to be nonpermutable that is both necessary and sufficient.When the parts of $\lambda$ are not distinct there will be multiple row bound$n$-tuples $\beta$ that will produce the same set of tableaux. We accordinglygroup the bounding $\beta$ into equivalence classes and identify the mostefficient $\beta$ in each class for the determinant computation. We recentlyshowed that many other sets of objects that are indexed by $n$ and $\lambda$are enumerated by the number of these efficient $n$-tuples. We called thesecounts "parabolic Catalan numbers". It is noted that the $GL(n)$ Demazurecharacters (key polynomials) indexed by 312-avoiding permutations can also beexpressed with these determinants. PubDate: Fri, 23 Apr 2021 11:42:21 +020
Abstract: Catalan words are particular growth-restricted words counted by the eponymousinteger sequence. In this article we consider Catalan words avoiding a pair ofpatterns of length 3, pursuing the recent initiating work of the first and lastauthors and of S. Kirgizov where (among other things) the enumeration ofCatalan words avoiding a patterns of length 3 is completed. More precisely, weexplore systematically the structural properties of the sets of words underconsideration and give enumerating results by means of recursive decomposition,constructive bijections or bivariate generating functions with respect to thelength and descent number. Some of the obtained enumerating sequences areknown, and thus the corresponding results establish new combinatorialinterpretations for them. PubDate: Fri, 16 Apr 2021 09:43:30 +020
Abstract: We give three applications of a recently-proven "Decomposition Lemma," whichallows one to count preimages of certain sets of permutations under West'sstack-sorting map $s$. We first enumerate the permutation class$s^{-1}(\text{Av}(231,321))=\text{Av}(2341,3241,45231)$, finding a new exampleof an unbalanced Wilf equivalence. This result is equivalent to the enumerationof permutations sortable by ${\bf B}\circ s$, where ${\bf B}$ is the bubblesort map. We then prove that the sets $s^{-1}(\text{Av}(231,312))$,$s^{-1}(\text{Av}(132,231))=\text{Av}(2341,1342,\underline{32}41,\underline{31}42)$,and $s^{-1}(\text{Av}(132,312))=\text{Av}(1342,3142,3412,34\underline{21})$ arecounted by the so-called "Boolean-Catalan numbers," settling a conjecture ofthe current author and another conjecture of Hossain. This completes theenumerations of all sets of the form$s^{-1}(\text{Av}(\tau^{(1)},\ldots,\tau^{(r)}))$ for$\{\tau^{(1)},\ldots,\tau^{(r)}\}\subseteq S_3$ with the exception of the set$\{321\}$. We also find an explicit formula for$ s^{-1}(\text{Av}_{n,k}(231,312,321)) $, where $\text{Av}_{n,k}(231,312,321)$is the set of permutations in $\text{Av}_n(231,312,321)$ with $k$ descents.This allows us to prove a conjectured identity involving Catalan numbers andorder ideals in Young's lattice. PubDate: Fri, 09 Apr 2021 17:03:26 +020
Abstract: In this paper, we study the staircase encoding of permutations, which maps apermutation to a staircase grid with cells filled with permutations. Weconsider many cases, where restricted to a permutation class, the staircaseencoding becomes a bijection to its image. We describe the image of thoserestrictions using independent sets of graphs weighted with permutations. Wederive the generating function for the independent sets and then for theirweighted counterparts. The bijections we establish provide the enumeration ofpermutation classes. We use our results to uncover some unbalancedWilf-equivalences of permutation classes and outline how to do random samplingin the permutation classes. In particular, we cover the classes$\mathrm{Av}(2314,3124)$, $\mathrm{Av}(2413,3142)$, $\mathrm{Av}(2413,3124)$,$\mathrm{Av}(2413,2134)$ and $\mathrm{Av}(2314,2143)$, as well as manysubclasses. PubDate: Mon, 29 Mar 2021 11:02:41 +020
Abstract: We introduce a new boundedness condition for affine permutations, motivatedby the fruitful concept of periodic boundary conditions in statistical physics.We study pattern avoidance in bounded affine permutations. In particular, weshow that if $\tau$ is one of the finite increasing oscillations, then every$\tau$-avoiding affine permutation satisfies the boundedness condition. We alsoexplore the enumeration of pattern-avoiding affine permutations that can bedecomposed into blocks, using analytic methods to relate their exact andasymptotic enumeration to that of the underlying ordinary permutations.Finally, we perform exact and asymptotic enumeration of the set of all boundedaffine permutations of size $n$. A companion paper will focus on avoidance ofmonotone decreasing patterns in bounded affine permutations. PubDate: Mon, 29 Mar 2021 10:57:54 +020
Abstract: We consider non-trivial homomorphisms to reflexive oriented graphs in whichsome pair of adjacent vertices have the same image. Using a notion of convexityfor oriented graphs, we study those oriented graphs that do not admit suchhomomorphisms. We fully classify those oriented graphs with tree-width $2$ thatdo not admit such homomorphisms and show that it is NP-complete to decide if agraph admits an orientation that does not admit such homomorphisms. We proveanalogous results for $2$-edge-coloured graphs. We apply our results onoriented graphs to provide a new tool in the study of chromatic number oforientations of planar graphs -- a long-standing open problem. PubDate: Mon, 29 Mar 2021 10:53:54 +020
Abstract: The forbidden number $\mathrm{forb}(m,F)$, which denotes the maximum numberof unique columns in an $m$-rowed $(0,1)$-matrix with no submatrix that is arow and column permutation of $F$, has been widely studied in extremal settheory. Recently, this function was extended to $r$-matrices, whose entries liein $\{0,1,\dots,r-1\}$. The combinatorics of the generalized forbidden numberis less well-studied. In this paper, we provide exact bounds for many$(0,1)$-matrices $F$, including all $2$-rowed matrices when $r> 3$. We alsoprove a stability result for the $2\times 2$ identity matrix. Along the way, weexpose some interesting qualitative differences between the cases $r=2$, $r =3$, and $r> 3$. PubDate: Tue, 23 Mar 2021 10:42:29 +010
Abstract: Let $G$ be a a connected graph. The Wiener index of a connected graph is thesum of the distances between all unordered pairs of vertices. We provideasymptotic formulae for the maximum Wiener index of simple triangulations andquadrangulations with given connectivity, as the order increases, and makeconjectures for the extremal triangulations and quadrangulations based oncomputational evidence. If $\overline{\sigma}(v)$ denotes the arithmetic meanof the distances from $v$ to all other vertices of $G$, then the remoteness of$G$ is defined as the largest value of $\overline{\sigma}(v)$ over all vertices$v$ of $G$. We give sharp upper bounds on the remoteness of simpletriangulations and quadrangulations of given order and connectivity. PubDate: Mon, 08 Mar 2021 09:48:59 +010
Abstract: Recently, Yamazaki et al. provided an algorithm that enumerates allnon-isomorphic interval graphs on $n$ vertices with an $O(n^4)$ time delay. Inthis paper, we improve their algorithm and achieve $O(n^3 \log n)$ time delay.We also extend the catalog of these graphs providing a list of allnon-isomorphic interval graphs for all $n$ up to $15$. PubDate: Mon, 08 Mar 2021 09:45:41 +010
Abstract: Recently, Fici, Restivo, Silva, and Zamboni introduced the notion of a$k$-anti-power, which is defined as a word of the form $w^{(1)} w^{(2)} \cdotsw^{(k)}$, where $w^{(1)}, w^{(2)}, \ldots, w^{(k)}$ are distinct words of thesame length. For an infinite word $w$ and a positive integer $k$, define$AP_j(w,k)$ to be the set of all integers $m$ such that $w_{j+1} w_{j+2} \cdotsw_{j+km}$ is a $k$-anti-power, where $w_i$ denotes the $i$-th letter of $w$.Define also $\mathcal{F}_j(k) = (2 \mathbb{Z}^+ - 1) \cap AP_j(\mathbf{t},k)$,where $\mathbf{t}$ denotes the Thue-Morse word. For all $k \in \mathbb{Z}^+$,$\gamma_j(k) = \min (AP_j(\mathbf{t},k))$ is a well-defined positive integer,and for $k \in \mathbb{Z}^+$ sufficiently large, $\Gamma_j(k) = \sup ((2\mathbb{Z}^+ -1) \setminus \mathcal{F}_j(k))$ is a well-defined odd positiveinteger. In his 2018 paper, Defant shows that $\gamma_0(k)$ and $\Gamma_0(k)$grow linearly in $k$. We generalize Defant's methods to prove that$\gamma_j(k)$ and $\Gamma_j(k)$ grow linearly in $k$ for any nonnegativeinteger $j$. In particular, we show that $\displaystyle 1/10 \leq \liminf_{k\rightarrow \infty} (\gamma_j(k)/k) \leq 9/10$ and $\displaystyle 1/5 \leq\limsup_{k \rightarrow \infty} (\gamma_j(k)/k) \leq 3/2$. Additionally, we showthat $\displaystyle \liminf_{k \rightarrow \infty} (\Gamma_j(k)/k) = 3/2$ and$\displaystyle \limsup_{k \rightarrow \infty} (\Gamma_j(k)/k) = 3$. PubDate: Thu, 25 Feb 2021 10:28:02 +010
Abstract: In a recent work, Bensmail, Blanc, Cohen, Havet and Rocha, motivated by applications for TDMA scheduling problems, have introduced the notion of BMRN*-colouring of digraphs, which is a type of arc-colouring with particular colouring constraints. In particular, they gave a special focus to planar digraphs. They notably proved that every planar digraph can be 8-BMRN*-coloured, while there exist planar digraphs for which 7 colours are needed in a BMRN*-colouring. They also proved that the problem of deciding whether a planar digraph can be 3-BMRN*-coloured is NP-hard. In this work, we pursue these investigations on planar digraphs, in particular by answering some of the questions left open by the authors in that seminal work. We exhibit planar digraphs needing 8 colours to be BMRN*-coloured, thus showing that the upper bound of Bensmail, Blanc, Cohen, Havet and Rocha cannot be decreased in general. We also generalize their complexity result by showing that the problem of deciding whether a planar digraph can be k-BMRN*-coloured is NP-hard for every k ∈ {3,...,6}. Finally, we investigate the connection between the girth of a planar digraphs and the least number of colours in its BMRN*-colourings. PubDate: Thu, 25 Feb 2021 10:24:16 +010
Abstract: In this paper we present an average-case analysis of closed lambda terms with restricted values of De Bruijn indices in the model where each occurrence of a variable contributes one to the size. Given a fixed integer k, a lambda term in which all De Bruijn indices are bounded by k has the following shape: It starts with k De Bruijn levels, forming the so-called hat of the term, to which some number of k-colored Motzkin trees are attached. By means of analytic combinatorics, we show that the size of this hat is constant on average and that the average number of De Bruijn levels of k-colored Motzkin trees of size n is asymptotically Θ(√ n). Combining these two facts, we conclude that the maximal non-empty De Bruijn level in a lambda term with restrictions on De Bruijn indices and of size n is, on average, also of order √ n. On this basis, we provide the average unary profile of such lambda terms. PubDate: Fri, 12 Feb 2021 10:04:37 +010
Abstract: A sequence of geometric random variables of length $n$ is a sequence of $n$independent and identically distributed geometric random variables ($\Gamma_1,\Gamma_2, \dots, \Gamma_n$) where $\mathbb{P}(\Gamma_j=i)=pq^{i-1}$ for$1~\leq~j~\leq~n$ with $p+q=1.$ We study the number of distinct adjacent twoletter patterns in such sequences. Initially we directly count the number ofdistinct pairs in words of short length. Because of the rapid growth of thenumber of word patterns we change our approach to this problem by obtaining anexpression for the expected number of distinct pairs in words of length $n$. Wealso obtain the asymptotics for the expected number as $n \to \infty$. PubDate: Thu, 28 Jan 2021 15:22:47 +010
Abstract: In this paper we address the problem of understanding Concurrency Theory from a combinatorial point of view. We are interested in quantitative results and algorithmic tools to refine our understanding of the classical combinatorial explosion phenomenon arising in concurrency. This paper is essentially focusing on the the notion of synchronization from the point of view of combinatorics. As a first step, we address the quantitative problem of counting the number of executions of simple processes interacting with synchronization barriers. We elaborate a systematic decomposition of processes that produces a symbolic integral formula to solve the problem. Based on this procedure, we develop a generic algorithm to generate process executions uniformly at random. For some interesting sub-classes of processes we propose very efficient counting and random sampling algorithms. All these algorithms have one important characteristic in common: they work on the control graph of processes and thus do not require the explicit construction of the state-space. PubDate: Mon, 25 Jan 2021 14:58:42 +010
Abstract: Y. Manoussakis (J. Graph Theory 16, 1992, 51-59) proposed the followingconjecture. \noindent\textbf{Conjecture}. {\it Let $D$ be a 2-strongly connected digraphof order $n$ such that for all distinct pairs of non-adjacent vertices $x$, $y$and $w$, $z$, we have $d(x)+d(y)+d(w)+d(z)\geq 4n-3$. Then $D$ is Hamiltonian.} In this paper, we confirm this conjecture. Moreover, we prove that if adigraph $D$ satisfies the conditions of this conjecture and has a pair ofnon-adjacent vertices $\{x,y\}$ such that $d(x)+d(y)\leq 2n-4$, then $D$contains cycles of all lengths $3, 4, \ldots , n$. PubDate: Mon, 18 Jan 2021 13:23:33 +010
Abstract: We provide a pair of ribbon graphs that have the same rotor routing andBernardi sandpile torsors, but different topological genus. This resolves aquestion posed by M. Chan [Cha]. We also show that if we are given a graph, butnot its ribbon structure, along with the rotor routing sandpile torsors, we areable to determine the ribbon graph's genus. PubDate: Thu, 07 Jan 2021 10:16:32 +010
Abstract: Neumann-Lara and Škrekovski conjectured that every planar digraph is 2-colourable. We show that this conjecture is equivalent to the more general statement that all oriented K_5-minor-free graphs are 2-colourable. PubDate: Tue, 05 Jan 2021 09:49:23 +010
Open Access journal
[1 journal]
