<![CDATA[Discrete Mathematics & Theoretical Computer Science - RSS]]>
https://dmtcs.episciences.org
Mon, 17 Jan 2022 17:48:59 +0100https://dmtcs.episciences.org/img/episciences_sign_50x50.png<![CDATA[Discrete Mathematics & Theoretical Computer Science - RSS]]>
https://dmtcs.episciences.org
Zend_Feedenhttp://blogs.law.harvard.edu/tech/rss<![CDATA[Upper paired domination versus upper domination]]>
https://dmtcs.episciences.org/8823
Thu, 16 Dec 2021 14:15:54 +0100<![CDATA[The treewidth of 2-section of hypergraphs]]>
https://dmtcs.episciences.org/8816
Thu, 09 Dec 2021 16:59:54 +0100<![CDATA[Antipowers in Uniform Morphic Words and the Fibonacci Word]]>
https://dmtcs.episciences.org/8805
Thu, 09 Dec 2021 16:53:04 +0100<![CDATA[List-antimagic labeling of vertex-weighted graphs]]>
https://dmtcs.episciences.org/8792
Thu, 02 Dec 2021 16:23:48 +0100<![CDATA[On non-adaptive majority problems of large query size]]>
https://dmtcs.episciences.org/8737
Fri, 26 Nov 2021 11:00:41 +0100<![CDATA[Certificate complexity and symmetry of nested canalizing functions]]>
https://dmtcs.episciences.org/8754
Fri, 26 Nov 2021 10:50:34 +0100<![CDATA[Fast Diameter Computation within Split Graphs]]>
https://dmtcs.episciences.org/8680
Mon, 15 Nov 2021 11:16:07 +0100<![CDATA[Five results on maximizing topological indices in graphs]]>
https://dmtcs.episciences.org/8688
Mon, 15 Nov 2021 11:10:33 +0100<![CDATA[On the genera of polyhedral embeddings of cubic graph]]>
https://dmtcs.episciences.org/8657
Fri, 05 Nov 2021 16:40:54 +0100<![CDATA[The algebra of binary trees is affine complete]]>
https://dmtcs.episciences.org/8654
Thu, 04 Nov 2021 09:44:33 +0100<![CDATA[Introduction to local certification]]>
https://dmtcs.episciences.org/8479
Wed, 15 Sep 2021 14:18:21 +0200<![CDATA[The undecidability of joint embedding for 3-dimensional permutation
classes]]>
https://dmtcs.episciences.org/8461
Tue, 14 Sep 2021 10:40:59 +0200<![CDATA[A tight lower bound for the online bounded space hypercube bin packing
problem]]>
https://dmtcs.episciences.org/8462
Tue, 14 Sep 2021 10:37:20 +0200<![CDATA[On the density of sets of the Euclidean plane avoiding distance 1]]>
https://dmtcs.episciences.org/8426
Tue, 31 Aug 2021 18:35:13 +0200<![CDATA[Lattice Paths and Pattern-Avoiding Uniquely Sorted Permutations]]>
https://dmtcs.episciences.org/8403
Tue, 31 Aug 2021 09:30:13 +0200<![CDATA[Binary patterns in the Prouhet-Thue-Morse sequence]]>
https://dmtcs.episciences.org/8398
Mon, 30 Aug 2021 14:58:00 +0200<![CDATA[The structure and the list 3-dynamic coloring of outer-1-planar graphs]]>
https://dmtcs.episciences.org/8381
Fri, 27 Aug 2021 08:57:03 +0200<![CDATA[Determining the Hausdorff Distance Between Trees in Polynomial Time]]>
https://dmtcs.episciences.org/8377
Thu, 19 Aug 2021 17:29:10 +0200<![CDATA[On the VC-dimension of half-spaces with respect to convex sets]]>
https://dmtcs.episciences.org/8376
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 be
shattered. We give two exemplary applications. One for a geometric set cover
problem and one for a range-query data structure problem, to motivate our
findings.
]]> 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 be
shattered. We give two exemplary applications. One for a geometric set cover
problem and one for a range-query data structure problem, to motivate our
findings.
]]>Thu, 19 Aug 2021 17:24:12 +0200<![CDATA[Two examples of Wilf-collapse]]>
https://dmtcs.episciences.org/8373
Thu, 19 Aug 2021 17:18:29 +0200<![CDATA[A birational lifting of the Stanley-Thomas word on products of two
chains]]>
https://dmtcs.episciences.org/8367
Wed, 18 Aug 2021 09:18:26 +0200<![CDATA[Enumeration of Dumont permutations avoiding certain four-letter patterns]]>
https://dmtcs.episciences.org/7639
Tue, 06 Jul 2021 14:35:41 +0200<![CDATA[Semipaired Domination in Some Subclasses of Chordal Graphs]]>
https://dmtcs.episciences.org/7650
Tue, 06 Jul 2021 14:30:51 +0200<![CDATA[Fillings of skew shapes avoiding diagonal patterns]]>
https://dmtcs.episciences.org/7594
Fri, 18 Jun 2021 14:31:44 +0200<![CDATA[Crisp-determinization of weighted tree automata over strong bimonoids]]>
https://dmtcs.episciences.org/7580
Tue, 15 Jun 2021 09:40:34 +0200<![CDATA[A note on tight cuts in matching-covered graphs]]>
https://dmtcs.episciences.org/7573
Mon, 14 Jun 2021 11:51:56 +0200<![CDATA[Destroying Bicolored $P_3$s by Deleting Few Edges]]>
https://dmtcs.episciences.org/7553
Tue, 08 Jun 2021 10:23:01 +0200<![CDATA[The Elser nuclei sum revisited]]>
https://dmtcs.episciences.org/7487
Thu, 03 Jun 2021 11:41:13 +0200<![CDATA[Generalized Fitch Graphs III: Symmetrized Fitch maps and Sets of
Symmetric Binary Relations that are explained by Unrooted Edge-labeled Trees]]>
https://dmtcs.episciences.org/7493
Thu, 03 Jun 2021 11:37:26 +0200<![CDATA[Wiener index in graphs with given minimum degree and maximum degree]]>
https://dmtcs.episciences.org/7533
Thu, 03 Jun 2021 11:31:33 +0200<![CDATA[Weak equivalence of higher-dimensional automata]]>
https://dmtcs.episciences.org/7490
Tue, 18 May 2021 11:47:50 +0200<![CDATA[Flip-sort and combinatorial aspects of pop-stack sorting]]>
https://dmtcs.episciences.org/7411
Fri, 30 Apr 2021 10:26:14 +0200<![CDATA[New Algorithms for Mixed Dominating Set]]>
https://dmtcs.episciences.org/7407
Fri, 30 Apr 2021 10:23:11 +0200<![CDATA[Row bounds needed to justifiably express flagged Schur functions with
Gessel-Viennot determinants]]>
https://dmtcs.episciences.org/7381
Fri, 23 Apr 2021 11:42:21 +0200<![CDATA[Catalan words avoiding pairs of length three patterns]]>
https://dmtcs.episciences.org/7369
Fri, 16 Apr 2021 09:43:30 +0200<![CDATA[Enumeration of Stack-Sorting Preimages via a Decomposition Lemma]]>
https://dmtcs.episciences.org/7324
Fri, 09 Apr 2021 17:03:26 +0200<![CDATA[Enumeration of Permutation Classes and Weighted Labelled Independent
Sets]]>
https://dmtcs.episciences.org/7295
Mon, 29 Mar 2021 11:02:41 +0200<![CDATA[Bounded affine permutations I. Pattern avoidance and enumeration]]>
https://dmtcs.episciences.org/7302
Mon, 29 Mar 2021 10:57:54 +0200<![CDATA[On the existence and non-existence of improper homomorphisms of oriented
and $2$-edge-coloured graphs to reflexive targets]]>
https://dmtcs.episciences.org/7292
Mon, 29 Mar 2021 10:53:54 +0200<![CDATA[Exponential multivalued forbidden configurations]]>
https://dmtcs.episciences.org/7283
3$. We also
prove a stability result for the $2\times 2$ identity matrix. Along the way, we
expose some interesting qualitative differences between the cases $r=2$, $r =
3$, and $r > 3$.
]]> 3$. We also
prove a stability result for the $2\times 2$ identity matrix. Along the way, we
expose some interesting qualitative differences between the cases $r=2$, $r =
3$, and $r > 3$.
]]>Tue, 23 Mar 2021 10:42:29 +0100<![CDATA[Wiener Index and Remoteness in Triangulations and Quadrangulations]]>
https://dmtcs.episciences.org/7247
Mon, 08 Mar 2021 09:48:59 +0100<![CDATA[Efficient enumeration of non-isomorphic interval graphs]]>
https://dmtcs.episciences.org/7246
Mon, 08 Mar 2021 09:45:41 +0100<![CDATA[Anti-power $j$-fixes of the Thue-Morse word]]>
https://dmtcs.episciences.org/7214
Thu, 25 Feb 2021 10:28:02 +0100<![CDATA[On BMRN*-colouring of planar digraphs]]>
https://dmtcs.episciences.org/7208
Thu, 25 Feb 2021 10:24:16 +0100<![CDATA[Unary profile of lambda terms with restricted De Bruijn indices]]>
https://dmtcs.episciences.org/7135
Fri, 12 Feb 2021 10:04:37 +0100<![CDATA[The number of distinct adjacent pairs in geometrically distributed words]]>
https://dmtcs.episciences.org/7121
Thu, 28 Jan 2021 15:22:47 +0100<![CDATA[Quantitative and Algorithmic aspects of Barrier Synchronization in Concurrency]]>
https://dmtcs.episciences.org/7120
Mon, 25 Jan 2021 14:58:42 +0100<![CDATA[A new sufficient condition for a Digraph to be Hamiltonian-A proof of
Manoussakis Conjecture]]>
https://dmtcs.episciences.org/7096
Mon, 18 Jan 2021 13:23:33 +0100<![CDATA[Determining Genus From Sandpile Torsor Algorithms]]>
https://dmtcs.episciences.org/7050
Thu, 07 Jan 2021 10:16:32 +0100<![CDATA[A Note on Graphs of Dichromatic Number 2]]>
https://dmtcs.episciences.org/7040
Tue, 05 Jan 2021 09:49:23 +0100<![CDATA[The LexCycle on $\overline{P_{2}\cup P_{3}}$-free Cocomparability Graphs]]>
https://dmtcs.episciences.org/6994
Mon, 28 Dec 2020 10:08:45 +0100<![CDATA[Two lower bounds for $p$-centered colorings]]>
https://dmtcs.episciences.org/6867
Wed, 11 Nov 2020 10:20:55 +0100<![CDATA[Even cycles and perfect matchings in claw-free plane graphs]]>
https://dmtcs.episciences.org/6827
Mon, 12 Oct 2020 09:36:00 +0200<![CDATA[Extension Complexity, MSO Logic, and Treewidth]]>
https://dmtcs.episciences.org/6811
Thu, 01 Oct 2020 17:42:02 +0200<![CDATA[Taking-and-merging games as rewrite games]]>
https://dmtcs.episciences.org/6795
epsilon.
We give sufficient conditions for a game to be such that the losing positions
(resp. the positions with a given Grundy value) form a regular language or a
context-free language. We formulate several related open questions in parallel
with the famous conjecture of Guy about the periodicity of the Grundy function
of octal games.
Finally we show that more general rewrite games quickly lead to undecidable
problems. Namely, it is undecidable whether there exists a winning position in
a given regular language, even if we restrict to games where each move strictly
reduces the length of the current position. We formulate several related open
questions in parallel with the famous conjecture of Guy about the periodicity
of the Grundy function of octal games.
]]>epsilon.
We give sufficient conditions for a game to be such that the losing positions
(resp. the positions with a given Grundy value) form a regular language or a
context-free language. We formulate several related open questions in parallel
with the famous conjecture of Guy about the periodicity of the Grundy function
of octal games.
Finally we show that more general rewrite games quickly lead to undecidable
problems. Namely, it is undecidable whether there exists a winning position in
a given regular language, even if we restrict to games where each move strictly
reduces the length of the current position. We formulate several related open
questions in parallel with the famous conjecture of Guy about the periodicity
of the Grundy function of octal games.
]]>Wed, 23 Sep 2020 13:47:19 +0200<![CDATA[A Double Exponential Lower Bound for the Distinct Vectors Problem]]>
https://dmtcs.episciences.org/6789
Fri, 18 Sep 2020 15:34:05 +0200<![CDATA[(Open) packing number of some graph products]]>
https://dmtcs.episciences.org/6730
Thu, 27 Aug 2020 09:18:21 +0200<![CDATA[Evacuating Robots from a Disk Using Face-to-Face Communication]]>
https://dmtcs.episciences.org/6732
Thu, 27 Aug 2020 09:13:53 +0200<![CDATA[A Büchi-Elgot-Trakhtenbrot theorem for automata with MSO graph storage]]>
https://dmtcs.episciences.org/6734
Thu, 27 Aug 2020 09:12:06 +0200<![CDATA[A Type System Describing Unboundedness]]>
https://dmtcs.episciences.org/6716
Tue, 18 Aug 2020 09:20:48 +0200<![CDATA[On an alternative sequence comparison statistic of Steele]]>
https://dmtcs.episciences.org/6625
Fri, 10 Jul 2020 12:03:55 +0200<![CDATA[The agreement distance of unrooted phylogenetic networks]]>
https://dmtcs.episciences.org/6567
Thu, 09 Jul 2020 10:30:40 +0200<![CDATA[Inversion sequences avoiding pairs of patterns]]>
https://dmtcs.episciences.org/6539
Mon, 29 Jun 2020 15:38:31 +0200<![CDATA[Dissecting a square into congruent polygons]]>
https://dmtcs.episciences.org/6596
Mon, 29 Jun 2020 15:34:40 +0200<![CDATA[On the heapability of finite partial orders]]>
https://dmtcs.episciences.org/6540
Mon, 29 Jun 2020 15:29:19 +0200<![CDATA[Complementary symmetric Rote sequences: the critical exponent and the
recurrence function]]>
https://dmtcs.episciences.org/6519
Sat, 06 Jun 2020 13:59:49 +0200<![CDATA[The Complexity of Helly-$B_{1}$ EPG Graph Recognition]]>
https://dmtcs.episciences.org/6506
Thu, 04 Jun 2020 16:56:38 +0200<![CDATA[New schemes for simplifying binary constraint satisfaction problems]]>
https://dmtcs.episciences.org/6507
Thu, 04 Jun 2020 16:38:55 +0200<![CDATA[Antifactors of regular bipartite graphs]]>
https://dmtcs.episciences.org/6520
Thu, 04 Jun 2020 16:33:38 +0200<![CDATA[Formal inverses of the generalized Thue-Morse sequences and variations
of the Rudin-Shapiro sequence]]>
https://dmtcs.episciences.org/6444
Mon, 25 May 2020 10:03:35 +0200<![CDATA[Complexity of Leading Digit Sequences]]>
https://dmtcs.episciences.org/6433
0$ that are not integral powers of $b$. In particular, we
show that, for all such pairs $(a,b)$, the complexity function $p_{a,b}(n)$ is
\emph{affine}, i.e., satisfies $p_{a,b}(n)=c_{a,b} n + d_{a,b}$ for all
$n\ge1$, with coefficients $c_{a,b}\ge1$ and $d_{a,b}\ge0$, given explicitly in
terms of $a$ and $b$. We also show that the requirement that $b$ be squarefree
cannot be dropped: If $b$ is not squarefree, then there exist integers $a$ with
$10$ that are not integral powers of $b$. In particular, we
show that, for all such pairs $(a,b)$, the complexity function $p_{a,b}(n)$ is
\emph{affine}, i.e., satisfies $p_{a,b}(n)=c_{a,b} n + d_{a,b}$ for all
$n\ge1$, with coefficients $c_{a,b}\ge1$ and $d_{a,b}\ge0$, given explicitly in
terms of $a$ and $b$. We also show that the requirement that $b$ be squarefree
cannot be dropped: If $b$ is not squarefree, then there exist integers $a$ with
$1Thu, 30 Apr 2020 11:13:09 +0200<![CDATA[The minimal probabilistic and quantum finite automata recognizing
uncountably many languages with fixed cutpoints]]>
https://dmtcs.episciences.org/6440
Thu, 30 Apr 2020 10:51:36 +0200<![CDATA[From generalized Tamari intervals to non-separable planar maps]]>
https://dmtcs.episciences.org/6421
Wed, 22 Apr 2020 23:33:39 +0200<![CDATA[Matrix product and sum rule for Macdonald polynomials]]>
https://dmtcs.episciences.org/6419
Wed, 22 Apr 2020 23:33:38 +0200<![CDATA[The number of corner polyhedra graphs]]>
https://dmtcs.episciences.org/6420
Wed, 22 Apr 2020 23:33:38 +0200<![CDATA[An equivalence of multistatistics on permutations]]>
https://dmtcs.episciences.org/6418
Wed, 22 Apr 2020 23:33:37 +0200<![CDATA[Counting quadrant walks via Tutte's invariant method (extended abstract)]]>
https://dmtcs.episciences.org/6416
Wed, 22 Apr 2020 23:33:36 +0200<![CDATA[Rectangular Young tableaux and the Jacobi ensemble]]>
https://dmtcs.episciences.org/6417
Wed, 22 Apr 2020 23:33:36 +0200<![CDATA[Continued Classification of 3D Lattice Models in the Positive Octant]]>
https://dmtcs.episciences.org/6415
Wed, 22 Apr 2020 23:33:35 +0200<![CDATA[On q-integrals over order polytopes (extended abstract)]]>
https://dmtcs.episciences.org/6413
Wed, 22 Apr 2020 23:33:34 +0200<![CDATA[Non-ambiguous trees: new results and generalization]]>
https://dmtcs.episciences.org/6414
Wed, 22 Apr 2020 23:33:34 +0200<![CDATA[A bijective proof of Macdonald's reduced word formula]]>
https://dmtcs.episciences.org/6412
Wed, 22 Apr 2020 23:33:33 +0200<![CDATA[Staircase diagrams and the enumeration of smooth Schubert varieties]]>
https://dmtcs.episciences.org/6411
Wed, 22 Apr 2020 23:33:32 +0200<![CDATA[Dual Immaculate Quasisymmetric Functions Expand Positively into Young Quasisymmetric Schur Functions]]>
https://dmtcs.episciences.org/6410
Wed, 22 Apr 2020 23:33:31 +0200<![CDATA[Schur polynomials and matrix positivity preservers]]>
https://dmtcs.episciences.org/6408
Wed, 22 Apr 2020 23:33:29 +0200<![CDATA[Extending the weak order on Coxeter groups]]>
https://dmtcs.episciences.org/6409
Wed, 22 Apr 2020 23:33:29 +0200<![CDATA[The Mixing Time for a Random Walk on the Symmetric Group Generated by Random Involutions]]>
https://dmtcs.episciences.org/6407
Wed, 22 Apr 2020 23:33:28 +0200<![CDATA[Toric matrix Schubert varieties and root polytopes (extended abstract)]]>
https://dmtcs.episciences.org/6405
Wed, 22 Apr 2020 23:33:27 +0200<![CDATA[The generalized Gelfand–Graev characters of GLn(Fq)]]>
https://dmtcs.episciences.org/6406
Wed, 22 Apr 2020 23:33:27 +0200<![CDATA[Order Filter Model for Minuscule Plücker Relations]]>
https://dmtcs.episciences.org/6404
Wed, 22 Apr 2020 23:33:26 +0200<![CDATA[The configuration space of a robotic arm in a tunnel of width 2]]>
https://dmtcs.episciences.org/6402
Wed, 22 Apr 2020 23:33:25 +0200<![CDATA[The twist for positroids]]>
https://dmtcs.episciences.org/6403
Wed, 22 Apr 2020 23:33:25 +0200<![CDATA[Brick polytopes, lattices and Hopf algebras]]>
https://dmtcs.episciences.org/6401
Wed, 22 Apr 2020 23:33:24 +0200<![CDATA[Compatibility fans realizing graphical nested complexes]]>
https://dmtcs.episciences.org/6400
Wed, 22 Apr 2020 23:33:23 +0200<![CDATA[The facial weak order in finite Coxeter groups]]>
https://dmtcs.episciences.org/6399
Wed, 22 Apr 2020 23:33:23 +0200<![CDATA[Normal Supercharacter Theory]]>
https://dmtcs.episciences.org/6397
Wed, 22 Apr 2020 23:33:22 +0200<![CDATA[A bijection for nonorientable general maps]]>
https://dmtcs.episciences.org/6398
Wed, 22 Apr 2020 23:33:22 +0200<![CDATA[Matrix-Ball Construction of affine Robinson-Schensted correspondence]]>
https://dmtcs.episciences.org/6396
Wed, 22 Apr 2020 23:33:21 +0200<![CDATA[Quasi-isomorphisms of cluster algebras and the combinatorics of webs (extended abstract)]]>
https://dmtcs.episciences.org/6395
Wed, 22 Apr 2020 23:33:20 +0200<![CDATA[Affine type A geometric crystal structure on the Grassmannian]]>
https://dmtcs.episciences.org/6393
Wed, 22 Apr 2020 23:33:19 +0200<![CDATA[Resonance in orbits of plane partitions]]>
https://dmtcs.episciences.org/6394
Wed, 22 Apr 2020 23:33:19 +0200<![CDATA[Total positivity for the Lagrangian Grassmannian]]>
https://dmtcs.episciences.org/6392
Wed, 22 Apr 2020 23:33:18 +0200<![CDATA[New hook-content formulas for strict partitions]]>
https://dmtcs.episciences.org/6391
Wed, 22 Apr 2020 23:33:17 +0200<![CDATA[Links in the complex of weakly separated collections]]>
https://dmtcs.episciences.org/6389
Wed, 22 Apr 2020 23:33:16 +0200<![CDATA[Asymptotics of lattice walks via analytic combinatorics in several variables]]>
https://dmtcs.episciences.org/6390
Wed, 22 Apr 2020 23:33:16 +0200<![CDATA[Categorifying the tensor product of the Kirillov-Reshetikhin crystal B1,1 and a fundamental crystal]]>
https://dmtcs.episciences.org/6388
Wed, 22 Apr 2020 23:33:15 +0200<![CDATA[Rational Dyck Paths in the Non Relatively Prime Case]]>
https://dmtcs.episciences.org/6387
Wed, 22 Apr 2020 23:33:14 +0200<![CDATA[A combinatorial analysis of Severi degrees]]>
https://dmtcs.episciences.org/6385
Wed, 22 Apr 2020 23:33:13 +0200<![CDATA[The Prism tableau model for Schubert polynomials]]>
https://dmtcs.episciences.org/6386
Wed, 22 Apr 2020 23:33:13 +0200<![CDATA[The Delta Conjecture]]>
https://dmtcs.episciences.org/6384
Wed, 22 Apr 2020 23:33:12 +0200<![CDATA[Maximal green sequences for arbitrary triangulations of marked surfaces (Extended Abstract)]]>
https://dmtcs.episciences.org/6383
Wed, 22 Apr 2020 23:33:11 +0200<![CDATA[GL(n, q)-analogues of factorization problems in the symmetric group]]>
https://dmtcs.episciences.org/6382
Wed, 22 Apr 2020 23:33:10 +0200<![CDATA[On intervals of the consecutive pattern poset]]>
https://dmtcs.episciences.org/6380
Wed, 22 Apr 2020 23:33:09 +0200<![CDATA[Monodromy and K-theory of Schubert curves via generalized jeu de taquin]]>
https://dmtcs.episciences.org/6381
Wed, 22 Apr 2020 23:33:09 +0200<![CDATA[Oriented Flip Graphs and Noncrossing Tree Partitions]]>
https://dmtcs.episciences.org/6379
Wed, 22 Apr 2020 23:33:08 +0200<![CDATA[Noncrossing partitions, toggles, and homomesy]]>
https://dmtcs.episciences.org/6378
Wed, 22 Apr 2020 23:33:06 +0200<![CDATA[A Formula for the Möbius Function of the Permutation Poset Based on a Topological Decomposition]]>
https://dmtcs.episciences.org/6376
Wed, 22 Apr 2020 23:33:05 +0200<![CDATA[Combinatorial descriptions of the crystal structure on certain PBW bases]]>
https://dmtcs.episciences.org/6377
Wed, 22 Apr 2020 23:33:05 +0200<![CDATA[Intersections of Amoebas]]>
https://dmtcs.episciences.org/6375
Wed, 22 Apr 2020 23:33:04 +0200<![CDATA[Refined dual stable Grothendieck polynomials and generalized Bender-Knuth involutions]]>
https://dmtcs.episciences.org/6374
Wed, 22 Apr 2020 23:33:03 +0200<![CDATA[Schur-positivity via products of grid classes]]>
https://dmtcs.episciences.org/6373
Wed, 22 Apr 2020 23:33:02 +0200<![CDATA[Separation of Variables and the Computation of Fourier Transforms on Finite Groups, II]]>
https://dmtcs.episciences.org/6372
Wed, 22 Apr 2020 23:33:01 +0200<![CDATA[Some results on counting roots of polynomials and the Sylvester resultant.]]>
https://dmtcs.episciences.org/6371
Wed, 22 Apr 2020 23:33:00 +0200<![CDATA[Yang-Baxter basis of Hecke algebra and Casselman's problem (extended abstract)]]>
https://dmtcs.episciences.org/6370
Wed, 22 Apr 2020 23:32:59 +0200<![CDATA[Almost simplicial polytopes: the lower and upper bound theorems]]>
https://dmtcs.episciences.org/6369
Wed, 22 Apr 2020 23:32:58 +0200<![CDATA[Counting connected graphs with large excess]]>
https://dmtcs.episciences.org/6368
Wed, 22 Apr 2020 23:32:57 +0200<![CDATA[A noncommutative geometric LR rule]]>
https://dmtcs.episciences.org/6367
Wed, 22 Apr 2020 23:32:56 +0200<![CDATA[Relaxations of the matroid axioms I: Independence, Exchange and Circuits]]>
https://dmtcs.episciences.org/6365
Wed, 22 Apr 2020 23:32:55 +0200<![CDATA[Symmetric Fundamental Expansions to Schur Positivity]]>
https://dmtcs.episciences.org/6366
Wed, 22 Apr 2020 23:32:55 +0200<![CDATA[Strange Expectations and Simultaneous Cores]]>
https://dmtcs.episciences.org/6364
Wed, 22 Apr 2020 23:32:54 +0200<![CDATA[Elliptic rook and file numbers]]>
https://dmtcs.episciences.org/6362
Wed, 22 Apr 2020 23:32:53 +0200<![CDATA[Symmetric Chain Decompositions and the Strong Sperner Property for Noncrossing Partition Lattices]]>
https://dmtcs.episciences.org/6363
Wed, 22 Apr 2020 23:32:53 +0200<![CDATA[A dual approach to structure constants for K-theory of Grassmannians]]>
https://dmtcs.episciences.org/6361
Wed, 22 Apr 2020 23:32:52 +0200<![CDATA[A Hopf algebra of subword complexes (Extended abstract)]]>
https://dmtcs.episciences.org/6359
Wed, 22 Apr 2020 23:32:51 +0200<![CDATA[McKay Centralizer Algebras]]>
https://dmtcs.episciences.org/6360
Wed, 22 Apr 2020 23:32:51 +0200<![CDATA[Tropical Ideals]]>
https://dmtcs.episciences.org/6358
Wed, 22 Apr 2020 23:32:50 +0200<![CDATA[Defining amplituhedra and Grassmann polytopes]]>
https://dmtcs.episciences.org/6356
Wed, 22 Apr 2020 23:32:49 +0200<![CDATA[Slicings of parallelogram polyominoes, or how Baxter and Schröder can be reconciled]]>
https://dmtcs.episciences.org/6357
Wed, 22 Apr 2020 23:32:49 +0200<![CDATA[Hook formulas for skew shapes]]>
https://dmtcs.episciences.org/6354
Wed, 22 Apr 2020 23:32:48 +0200<![CDATA[The topology of the external activity complex of a matroid]]>
https://dmtcs.episciences.org/6355
Wed, 22 Apr 2020 23:32:48 +0200<![CDATA[A two-sided analogue of the Coxeter complex]]>
https://dmtcs.episciences.org/6353
Wed, 22 Apr 2020 23:32:47 +0200<![CDATA[The Smith normal form distribution of a random integer matrix]]>
https://dmtcs.episciences.org/6352
Wed, 22 Apr 2020 23:32:46 +0200<![CDATA[On (non-) freeness of some tridendriform algebras]]>
https://dmtcs.episciences.org/6350
Wed, 22 Apr 2020 23:32:45 +0200<![CDATA[Cataland: Why the Fuss?]]>
https://dmtcs.episciences.org/6351
Wed, 22 Apr 2020 23:32:45 +0200<![CDATA[Rational Shi tableaux and the skew length statistic]]>
https://dmtcs.episciences.org/6349
Wed, 22 Apr 2020 23:32:44 +0200<![CDATA[On trees, tanglegrams, and tangled chains]]>
https://dmtcs.episciences.org/6348
Wed, 22 Apr 2020 23:32:43 +0200<![CDATA[Diagonally and antidiagonally symmetric alternating sign matrices of odd order]]>
https://dmtcs.episciences.org/6346
Wed, 22 Apr 2020 23:32:42 +0200<![CDATA[Parabolic double cosets in Coxeter groups]]>
https://dmtcs.episciences.org/6347
Wed, 22 Apr 2020 23:32:42 +0200<![CDATA[Cyclic inclusion-exclusion and the kernel of P -partitions]]>
https://dmtcs.episciences.org/6344
Wed, 22 Apr 2020 23:32:41 +0200<![CDATA[Plane partitions and the combinatorics of some families of reduced Kronecker coefficients.]]>
https://dmtcs.episciences.org/6345
Wed, 22 Apr 2020 23:32:41 +0200<![CDATA[Weak Separation, Pure Domains and Cluster Distance]]>
https://dmtcs.episciences.org/6343
Wed, 22 Apr 2020 23:32:40 +0200<![CDATA[The colored symmetric and exterior algebras]]>
https://dmtcs.episciences.org/6342
Wed, 22 Apr 2020 23:32:39 +0200<![CDATA[Parking functions, tree depth and factorizations of the full cycle into transpositions]]>
https://dmtcs.episciences.org/6340
Wed, 22 Apr 2020 23:32:38 +0200<![CDATA[Fully packed loop configurations : polynomiality and nested arches]]>
https://dmtcs.episciences.org/6341
Wed, 22 Apr 2020 23:32:38 +0200<![CDATA[Asymptotics of Bivariate Analytic Functions with Algebraic Singularities]]>
https://dmtcs.episciences.org/6339
Wed, 22 Apr 2020 23:32:37 +0200<![CDATA[Factorial Characters and Tokuyama's Identity for Classical Groups]]>
https://dmtcs.episciences.org/6338
Wed, 22 Apr 2020 23:32:36 +0200<![CDATA[Scheduling Problems and Generalized Graph Coloring]]>
https://dmtcs.episciences.org/6336
Wed, 22 Apr 2020 23:32:35 +0200<![CDATA[Symmetric matrices, Catalan paths, and correlations]]>
https://dmtcs.episciences.org/6337
Wed, 22 Apr 2020 23:32:35 +0200<![CDATA[The flag upper bound theorem for 3- and 5-manifolds]]>
https://dmtcs.episciences.org/6335
Wed, 22 Apr 2020 23:32:34 +0200<![CDATA[Quasisymmetric functions from combinatorial Hopf monoids and Ehrhart Theory]]>
https://dmtcs.episciences.org/6334
Wed, 22 Apr 2020 23:32:33 +0200<![CDATA[DHD-puzzles]]>
https://dmtcs.episciences.org/6332
Wed, 22 Apr 2020 23:32:32 +0200<![CDATA[A triple product formula for plane partitions derived from biorthogonal polynomials]]>
https://dmtcs.episciences.org/6333
Wed, 22 Apr 2020 23:32:32 +0200<![CDATA[A lattice point counting generalisation of the Tutte polynomial]]>
https://dmtcs.episciences.org/6331
Wed, 22 Apr 2020 23:32:31 +0200<![CDATA[Asymptotic laws for knot diagrams]]>
https://dmtcs.episciences.org/6329
Wed, 22 Apr 2020 23:32:30 +0200<![CDATA[Asymptotics of polygons in restricted geometries subject to a force]]>
https://dmtcs.episciences.org/6330
0 the force stretches the polygons, while when f < 0 the force is compressive. In this extended abstract we obtain and prove the asymptotic form of the free energy in the limit f → −∞. We conjecture that the f → −∞ asymptote is the same as the free energy of Hamiltonian polygons, which visit every vertex in a L × M × N box.
]]> 0 the force stretches the polygons, while when f < 0 the force is compressive. In this extended abstract we obtain and prove the asymptotic form of the free energy in the limit f → −∞. We conjecture that the f → −∞ asymptote is the same as the free energy of Hamiltonian polygons, which visit every vertex in a L × M × N box.
]]>Wed, 22 Apr 2020 23:32:30 +0200<![CDATA[Non-representable hyperbolic matroids]]>
https://dmtcs.episciences.org/6328
Wed, 22 Apr 2020 23:32:29 +0200<![CDATA[A type B analog of the Lie representation]]>
https://dmtcs.episciences.org/6327
Wed, 22 Apr 2020 23:32:28 +0200<![CDATA[Combinatorial description of the cohomology of the affine flag variety]]>
https://dmtcs.episciences.org/6326
Wed, 22 Apr 2020 23:32:27 +0200<![CDATA[A non-partitionable Cohen–Macaulay simplicial complex]]>
https://dmtcs.episciences.org/6325
Wed, 22 Apr 2020 23:32:26 +0200<![CDATA[Decomposition of the product of a monomial and a Demazure atom]]>
https://dmtcs.episciences.org/6323
Wed, 22 Apr 2020 23:32:25 +0200<![CDATA[Fourientation activities and the Tutte polynomial]]>
https://dmtcs.episciences.org/6324
Wed, 22 Apr 2020 23:32:25 +0200<![CDATA[Kraskiewicz-Pragacz modules and Pieri and dual Pieri rules for Schubert polynomials]]>
https://dmtcs.episciences.org/6321
Wed, 22 Apr 2020 23:32:24 +0200<![CDATA[Cumulants of Jack symmetric functions and b-conjecture (extended abstract)]]>
https://dmtcs.episciences.org/6322
Wed, 22 Apr 2020 23:32:24 +0200<![CDATA[Rhombic alternative tableaux, assemblees of permutations, and the ASEP]]>
https://dmtcs.episciences.org/6320
Wed, 22 Apr 2020 23:32:23 +0200<![CDATA[Minimal factorizations of a cycle: a multivariate generating function]]>
https://dmtcs.episciences.org/6318
Wed, 22 Apr 2020 23:32:22 +0200<![CDATA[A combinatorial approach to Macdonald q, t-symmetry via the Carlitz bijection]]>
https://dmtcs.episciences.org/6319
Wed, 22 Apr 2020 23:32:22 +0200<![CDATA[Cayley graphs of basic algebraic structures]]>
https://dmtcs.episciences.org/6287
Mon, 20 Apr 2020 09:16:02 +0200<![CDATA[The super-connectivity of Johnson graphs]]>
https://dmtcs.episciences.org/6270
Tue, 14 Apr 2020 11:13:25 +0200<![CDATA[The Chromatic Number of the Disjointness Graph of the Double Chain]]>
https://dmtcs.episciences.org/6209
Sun, 22 Mar 2020 09:58:41 +0100<![CDATA[New tools for state complexity]]>
https://dmtcs.episciences.org/6179
Mon, 16 Mar 2020 10:28:28 +0100<![CDATA[A method for eternally dominating strong grids]]>
https://dmtcs.episciences.org/6184
Mon, 16 Mar 2020 10:21:39 +0100<![CDATA[The 3-way flower intersection problem for Steiner triple systems]]>
https://dmtcs.episciences.org/6186
Mon, 16 Mar 2020 10:15:00 +0100<![CDATA[The repetition threshold for binary rich words]]>
https://dmtcs.episciences.org/6082
Mon, 24 Feb 2020 15:05:19 +0100<![CDATA[Analysis of a Model for Generating Weakly Scale-free Networks]]>
https://dmtcs.episciences.org/6089
k_{min} > 0$. Preferential attachment is the mechanism that
has been considered responsible for such organization of these networks. In
many real networks, degree distribution before the $k_{min}$ varies very slowly
to the extent of being uniform as compared with the degree distribution for $k
> k_{min}$ . In this paper, we proposed a model that describe this particular
degree distribution for the whole range of $k>0$. We adopt a two step approach.
In the first step, at every time stamp we add a new node to the network and
attach it with an existing node using preferential attachment method. In the
second step, we add edges between existing pairs of nodes with the node
selection based on the uniform probability distribution. Our approach generates
weakly scale-free networks that closely follow the degree distribution of
real-world networks. We perform comprehensive mathematical analysis of the
model in the discrete domain and compare the degree distribution generated by
these models with that of real-world networks.
]]> k_{min} > 0$. Preferential attachment is the mechanism that
has been considered responsible for such organization of these networks. In
many real networks, degree distribution before the $k_{min}$ varies very slowly
to the extent of being uniform as compared with the degree distribution for $k
> k_{min}$ . In this paper, we proposed a model that describe this particular
degree distribution for the whole range of $k>0$. We adopt a two step approach.
In the first step, at every time stamp we add a new node to the network and
attach it with an existing node using preferential attachment method. In the
second step, we add edges between existing pairs of nodes with the node
selection based on the uniform probability distribution. Our approach generates
weakly scale-free networks that closely follow the degree distribution of
real-world networks. We perform comprehensive mathematical analysis of the
model in the discrete domain and compare the degree distribution generated by
these models with that of real-world networks.
]]>Mon, 24 Feb 2020 15:02:25 +0100<![CDATA[A Characterization of Morphic Words with Polynomial Growth]]>
https://dmtcs.episciences.org/6073
Thu, 06 Feb 2020 17:00:08 +0100<![CDATA[Statistics on Linear Chord Diagrams]]>
https://dmtcs.episciences.org/6038
Thu, 23 Jan 2020 17:56:22 +0100<![CDATA[On the Complexity of Digraph Colourings and Vertex Arboricity]]>
https://dmtcs.episciences.org/6020
1$. In this paper, we consider the complexity
of corresponding decision problems for related notions of fractional colourings
for digraphs and graphs, including the star dichromatic number, the fractional
dichromatic number and the circular vertex arboricity. We prove the following
results:
Deciding if the star dichromatic number of a digraph is at most $p$ is
NP-complete for every rational $p>1$.
Deciding if the fractional dichromatic number of a digraph is at most $p$ is
NP-complete for every $p>1, p \neq 2$.
Deciding if the circular vertex arboricity of a graph is at most $p$ is
NP-complete for every rational $p>1$.
To show these results, different techniques are required in each case. In
order to prove the first result, we relate the star dichromatic number to a new
notion of homomorphisms between digraphs, called circular homomorphisms, which
might be of independent interest. We provide a classification of the
computational complexities of the corresponding homomorphism colouring problems
similar to the one derived by Feder et al. for acyclic homomorphisms.
]]>1$. In this paper, we consider the complexity
of corresponding decision problems for related notions of fractional colourings
for digraphs and graphs, including the star dichromatic number, the fractional
dichromatic number and the circular vertex arboricity. We prove the following
results:
Deciding if the star dichromatic number of a digraph is at most $p$ is
NP-complete for every rational $p>1$.
Deciding if the fractional dichromatic number of a digraph is at most $p$ is
NP-complete for every $p>1, p \neq 2$.
Deciding if the circular vertex arboricity of a graph is at most $p$ is
NP-complete for every rational $p>1$.
To show these results, different techniques are required in each case. In
order to prove the first result, we relate the star dichromatic number to a new
notion of homomorphisms between digraphs, called circular homomorphisms, which
might be of independent interest. We provide a classification of the
computational complexities of the corresponding homomorphism colouring problems
similar to the one derived by Feder et al. for acyclic homomorphisms.
]]>Tue, 21 Jan 2020 15:55:24 +0100<![CDATA[From light edges to strong edge-colouring of 1-planar graphs]]>
https://dmtcs.episciences.org/5985
Thu, 09 Jan 2020 10:24:43 +0100<![CDATA[Vertex order with optimal number of adjacent predecessors]]>
https://dmtcs.episciences.org/5996
Thu, 09 Jan 2020 10:13:29 +0100<![CDATA[A code for square permutations and convex permutominoes]]>
https://dmtcs.episciences.org/5842
Mon, 30 Dec 2019 13:31:35 +0100<![CDATA[The undecidability of joint embedding and joint homomorphism for
hereditary graph classes]]>
https://dmtcs.episciences.org/5923
Fri, 13 Dec 2019 18:05:17 +0100<![CDATA[Power domination in maximal planar graphs]]>
https://dmtcs.episciences.org/5967
Fri, 13 Dec 2019 16:01:55 +0100<![CDATA[Prolific Compositions]]>
https://dmtcs.episciences.org/5930
Fri, 13 Dec 2019 15:57:51 +0100<![CDATA[Cyclic permutations avoiding pairs of patterns of length three]]>
https://dmtcs.episciences.org/5909
Tue, 26 Nov 2019 14:45:09 +0100<![CDATA[Symmetry Properties of Nested Canalyzing Functions]]>
https://dmtcs.episciences.org/5920
Tue, 26 Nov 2019 14:39:22 +0100<![CDATA[Enumeration of super-strong Wilf equivalence classes of permutations in
the generalized factor order]]>
https://dmtcs.episciences.org/5880
Mon, 11 Nov 2019 12:12:23 +0100<![CDATA[Generalized Petersen graphs and Kronecker covers]]>
https://dmtcs.episciences.org/5891
Mon, 11 Nov 2019 11:41:35 +0100<![CDATA[Equitable Coloring and Equitable Choosability of Planar Graphs without
chordal 4- and 6-Cycles]]>
https://dmtcs.episciences.org/5896
Mon, 11 Nov 2019 11:31:41 +0100<![CDATA[Uniquely-Wilf classes]]>
https://dmtcs.episciences.org/5859
Mon, 04 Nov 2019 13:58:27 +0100<![CDATA[Consecutive Patterns in Inversion Sequences]]>
https://dmtcs.episciences.org/5856
Mon, 04 Nov 2019 13:54:33 +0100<![CDATA[On the number of pancake stacks requiring four flips to be sorted]]>
https://dmtcs.episciences.org/5879
Mon, 04 Nov 2019 13:50:08 +0100<![CDATA[Classical pattern distributions in $\mathcal{S}_{n}(132)$ and
$\mathcal{S}_{n}(123)$]]>
https://dmtcs.episciences.org/5855
Mon, 04 Nov 2019 13:44:15 +0100<![CDATA[An improved algorithm for the vertex cover $P_3$ problem on graphs of
bounded treewidth]]>
https://dmtcs.episciences.org/5867
Mon, 04 Nov 2019 13:32:49 +0100<![CDATA[On the inducibility of small trees]]>
https://dmtcs.episciences.org/5804
Thu, 17 Oct 2019 15:50:52 +0200<![CDATA[Proofs of Conjectures about Pattern-Avoiding Linear Extensions]]>
https://dmtcs.episciences.org/5796
Wed, 02 Oct 2019 09:52:20 +0200<![CDATA[Monochromatic loose paths in multicolored $k$-uniform cliques]]>
https://dmtcs.episciences.org/5793
0$ such that for all $k\ge 2$,
$\ell\ge3$, $2\le r\le k-1$, and $n\ge k(\ell+1)r(1+\ln(r))$, there is an
algorithm such that for every $r$-edge-coloring of the edges of $K_n^{(k)}$, it
finds a monochromatic copy of $P_\ell^{(k)}$ in time at most $cn^k$. We also
prove a non-constructive upper bound $R(P_\ell^{(k)};r)\le(k-1)\ell r$.
]]>0$ such that for all $k\ge 2$,
$\ell\ge3$, $2\le r\le k-1$, and $n\ge k(\ell+1)r(1+\ln(r))$, there is an
algorithm such that for every $r$-edge-coloring of the edges of $K_n^{(k)}$, it
finds a monochromatic copy of $P_\ell^{(k)}$ in time at most $cn^k$. We also
prove a non-constructive upper bound $R(P_\ell^{(k)};r)\le(k-1)\ell r$.
]]>Wed, 02 Oct 2019 09:45:10 +0200<![CDATA[Embeddings of 3-connected 3-regular planar graphs on surfaces of
non-negative Euler characteristic]]>
https://dmtcs.episciences.org/5784
Fri, 27 Sep 2019 14:13:40 +0200<![CDATA[New results on classical and quantum counter automata]]>
https://dmtcs.episciences.org/5788
Fri, 27 Sep 2019 13:34:14 +0200<![CDATA[Expected size of a tree in the fixed point forest]]>
https://dmtcs.episciences.org/5765
Fri, 27 Sep 2019 11:53:22 +0200<![CDATA[Structure of conflict graphs in constraint alignment problems and
algorithms]]>
https://dmtcs.episciences.org/5755
Wed, 11 Sep 2019 09:18:44 +0200<![CDATA[Constrained ear decompositions in graphs and digraphs]]>
https://dmtcs.episciences.org/5626
Mon, 02 Sep 2019 11:47:42 +0200<![CDATA[Clustered Spanning Tree - Conditions for Feasibility]]>
https://dmtcs.episciences.org/5710
be a hypergraph, where V is a set of vertices and S is a set of not necessarily disjoint clusters Si ⊆ V. The Clustered Spanning Tree problem is to find a spanning tree of G which satisfies that each cluster induces a subtree, when it exists. We provide an efficient and unique algorithm which finds a feasible solution tree for H when it exists, or states that no feasible solution exists. The paper also uses special structures of the intersection graph of H to construct a feasible solution more efficiently. For cases when the hypergraph does not have a feasible solution tree, we consider adding vertices to exactly one cluster in order to gain feasibility. We characterize when such addition can gain feasibility, find the appropriate cluster and a possible set of vertices to be added.
]]> be a hypergraph, where V is a set of vertices and S is a set of not necessarily disjoint clusters Si ⊆ V. The Clustered Spanning Tree problem is to find a spanning tree of G which satisfies that each cluster induces a subtree, when it exists. We provide an efficient and unique algorithm which finds a feasible solution tree for H when it exists, or states that no feasible solution exists. The paper also uses special structures of the intersection graph of H to construct a feasible solution more efficiently. For cases when the hypergraph does not have a feasible solution tree, we consider adding vertices to exactly one cluster in order to gain feasibility. We characterize when such addition can gain feasibility, find the appropriate cluster and a possible set of vertices to be added.
]]>Tue, 27 Aug 2019 15:55:09 +0200<![CDATA[On the centroid of increasing trees]]>
https://dmtcs.episciences.org/5691
Tue, 27 Aug 2019 15:49:59 +0200<![CDATA[Fractional matching preclusion for generalized augmented cubes]]>
https://dmtcs.episciences.org/5688
Tue, 13 Aug 2019 08:56:59 +0200<![CDATA[$(2/2/3)$-SAT problem and its applications in dominating set problems]]>
https://dmtcs.episciences.org/5678
Mon, 12 Aug 2019 11:38:12 +0200<![CDATA[On cordial labeling of hypertrees]]>
https://dmtcs.episciences.org/5658
Wed, 07 Aug 2019 09:18:23 +0200<![CDATA[Super edge-connectivity and matching preclusion of data center networks]]>
https://dmtcs.episciences.org/5652
Tue, 30 Jul 2019 17:50:15 +0200<![CDATA[Extremal properties of flood-filling games]]>
https://dmtcs.episciences.org/5642
Tue, 30 Jul 2019 13:43:03 +0200<![CDATA[On almost hypohamiltonian graphs]]>
https://dmtcs.episciences.org/5632
Tue, 30 Jul 2019 13:39:03 +0200<![CDATA[A note on the convexity number for complementary prisms]]>
https://dmtcs.episciences.org/5629
Tue, 30 Jul 2019 13:30:12 +0200<![CDATA[Backbone colouring and algorithms for TDMA scheduling]]>
https://dmtcs.episciences.org/5589
Sat, 13 Jul 2019 14:04:12 +0200<![CDATA[The maximum number of $P_\ell$ copies in $P_k$-free graphs]]>
https://dmtcs.episciences.org/5622
Sat, 13 Jul 2019 10:02:11 +0200<![CDATA[The Adaptive sampling revisited]]>
https://dmtcs.episciences.org/5588
Tue, 25 Jun 2019 09:35:08 +0200<![CDATA[On the multipacking number of grid graphs]]>
https://dmtcs.episciences.org/5579
Thu, 20 Jun 2019 10:33:55 +0200<![CDATA[On-line algorithms for multiplication and division in real and complex
numeration systems]]>
https://dmtcs.episciences.org/5569
1$, and the digit
set $A$ is a finite set of digits including $0$. Thus a number can be seen as a
finite or infinite string of digits. An on-line algorithm processes the input
piece-by-piece in a serial fashion. On-line arithmetic, introduced by Trivedi
and Ercegovac, is a mode of computation where operands and results flow through
arithmetic units in a digit serial manner, starting with the most significant
digit.
In this paper, we first formulate a generalized version of the on-line
algorithms for multiplication and division of Trivedi and Ercegovac for the
cases that $\beta$ is any real or complex number, and digits are real or
complex. We then define the so-called OL Property, and show that if $(\beta,
A)$ has the OL Property, then on-line multiplication and division are feasible
by the Trivedi-Ercegovac algorithms. For a real base $\beta$ and a digit set
$A$ of contiguous integers, the system $(\beta, A)$ has the OL Property if $\#
A > |\beta|$. For a complex base $\beta$ and symmetric digit set $A$ of
contiguous integers, the system $(\beta, A)$ has the OL Property if $\# A >
\beta\overline{\beta} + |\beta + \overline{\beta}|$. Provided that addition and
subtraction are realizable in parallel in the system $(\beta, A)$ and that
preprocessing of the denominator is possible, our on-line algorithms for
multiplication and division have linear time complexity. Three examples are
presented in detail: base $\beta=\frac{3+\sqrt{5}}{2}$ with digits
$A=\{-1,0,1\}$; base $\beta=2i$ with digits $A = \{-2,-1, 0,1,2\}$; and base
$\beta = -\frac{3}{2} + i \frac{\sqrt{3}}{2} = -1 + \omega$, where $\omega =
\exp{\frac{2i\pi}{3}}$, with digits $A = \{0, \pm 1, \pm \omega, \pm \omega^2
\}$.
]]>1$, and the digit
set $A$ is a finite set of digits including $0$. Thus a number can be seen as a
finite or infinite string of digits. An on-line algorithm processes the input
piece-by-piece in a serial fashion. On-line arithmetic, introduced by Trivedi
and Ercegovac, is a mode of computation where operands and results flow through
arithmetic units in a digit serial manner, starting with the most significant
digit.
In this paper, we first formulate a generalized version of the on-line
algorithms for multiplication and division of Trivedi and Ercegovac for the
cases that $\beta$ is any real or complex number, and digits are real or
complex. We then define the so-called OL Property, and show that if $(\beta,
A)$ has the OL Property, then on-line multiplication and division are feasible
by the Trivedi-Ercegovac algorithms. For a real base $\beta$ and a digit set
$A$ of contiguous integers, the system $(\beta, A)$ has the OL Property if $\#
A > |\beta|$. For a complex base $\beta$ and symmetric digit set $A$ of
contiguous integers, the system $(\beta, A)$ has the OL Property if $\# A >
\beta\overline{\beta} + |\beta + \overline{\beta}|$. Provided that addition and
subtraction are realizable in parallel in the system $(\beta, A)$ and that
preprocessing of the denominator is possible, our on-line algorithms for
multiplication and division have linear time complexity. Three examples are
presented in detail: base $\beta=\frac{3+\sqrt{5}}{2}$ with digits
$A=\{-1,0,1\}$; base $\beta=2i$ with digits $A = \{-2,-1, 0,1,2\}$; and base
$\beta = -\frac{3}{2} + i \frac{\sqrt{3}}{2} = -1 + \omega$, where $\omega =
\exp{\frac{2i\pi}{3}}$, with digits $A = \{0, \pm 1, \pm \omega, \pm \omega^2
\}$.
]]>Thu, 20 Jun 2019 10:29:32 +0200<![CDATA[Search-and-Fetch with 2 Robots on a Disk: Wireless and Face-to-Face
Communication Models]]>
https://dmtcs.episciences.org/5528
Thu, 13 Jun 2019 15:58:53 +0200<![CDATA[On the End-Vertex Problem of Graph Searches]]>
https://dmtcs.episciences.org/5572
Thu, 13 Jun 2019 15:40:15 +0200<![CDATA[Alternating Hamiltonian cycles in $2$-edge-colored multigraphs]]>
https://dmtcs.episciences.org/5564
Thu, 13 Jun 2019 15:33:15 +0200<![CDATA[Stable gonality is computable]]>
https://dmtcs.episciences.org/5557
Thu, 13 Jun 2019 15:28:19 +0200<![CDATA[Efficient enumeration of solutions produced by closure operations]]>
https://dmtcs.episciences.org/5549
Thu, 13 Jun 2019 15:23:30 +0200<![CDATA[Consecutive patterns in restricted permutations and involutions]]>
https://dmtcs.episciences.org/5519
Wed, 05 Jun 2019 11:23:05 +0200<![CDATA[Planar 3-SAT with a Clause/Variable Cycle]]>
https://dmtcs.episciences.org/5521
Wed, 05 Jun 2019 11:16:09 +0200<![CDATA[Bisplit graphs satisfy the Chen-Chvátal conjecture]]>
https://dmtcs.episciences.org/5509
Wed, 29 May 2019 09:26:16 +0200<![CDATA[New Bounds for the Dichromatic Number of a Digraph]]>
https://dmtcs.episciences.org/5505
Thu, 23 May 2019 17:34:39 +0200<![CDATA[Computing metric hulls in graphs]]>
https://dmtcs.episciences.org/5504
Thu, 23 May 2019 15:14:19 +0200<![CDATA[Characterising and recognising game-perfect graphs]]>
https://dmtcs.episciences.org/5499
Thu, 23 May 2019 11:54:49 +0200<![CDATA[The agreement distance of rooted phylogenetic networks]]>
https://dmtcs.episciences.org/5487
Thu, 23 May 2019 11:16:07 +0200<![CDATA[Non-crossing paths with geographic constraints]]>
https://dmtcs.episciences.org/5495
Thu, 23 May 2019 11:12:53 +0200<![CDATA[The 2-domination and Roman domination numbers of grid graphs]]>
https://dmtcs.episciences.org/5482
Thu, 23 May 2019 11:08:17 +0200<![CDATA[Parameterized Complexity of Equitable Coloring]]>
https://dmtcs.episciences.org/5464
Thu, 16 May 2019 13:24:04 +0200<![CDATA[Number of orbits of Discrete Interval Exchanges]]>
https://dmtcs.episciences.org/5462
Thu, 16 May 2019 13:19:54 +0200<![CDATA[Exact values for three domination-like problems in circular and infinite grid graphs of small height]]>
https://dmtcs.episciences.org/5458
Thu, 16 May 2019 13:15:52 +0200<![CDATA[On Stronger Types of Locating-dominating Codes]]>
https://dmtcs.episciences.org/5344
Sat, 11 May 2019 12:10:31 +0200<![CDATA[Some results on the palette index of graphs]]>
https://dmtcs.episciences.org/5360
Sat, 11 May 2019 12:03:15 +0200<![CDATA[FPT algorithms to recognize well covered graphs]]>
https://dmtcs.episciences.org/5342
Tue, 02 Apr 2019 14:20:11 +0200<![CDATA[On Weakly Distinguishing Graph Polynomials]]>
https://dmtcs.episciences.org/5340
Tue, 02 Apr 2019 11:34:53 +0200<![CDATA[A general decomposition theory for the 1-2-3 Conjecture and locally irregular decompositions]]>
https://dmtcs.episciences.org/5334
Tue, 02 Apr 2019 11:27:40 +0200<![CDATA[Bounds for the smallest $k$-chromatic graphs of given girth]]>
https://dmtcs.episciences.org/5259
5$. In
particular, the new bounds include: $n_4(7) \leq 77$, $26 \leq n_6(4) \leq 66$,
$30 \leq n_7(4) \leq 171$.
]]> 5$. In
particular, the new bounds include: $n_4(7) \leq 77$, $26 \leq n_6(4) \leq 66$,
$30 \leq n_7(4) \leq 171$.
]]>Mon, 11 Mar 2019 16:08:17 +0100<![CDATA[Slimness of graphs]]>
https://dmtcs.episciences.org/5245
Mon, 04 Mar 2019 16:04:50 +0100<![CDATA[Packing chromatic vertex-critical graphs]]>
https://dmtcs.episciences.org/5186
Mon, 18 Feb 2019 15:45:17 +0100<![CDATA[Packing coloring of generalized Sierpinski graphs]]>
https://dmtcs.episciences.org/5178
Fri, 08 Feb 2019 11:36:37 +0100<![CDATA[On the insertion of n-powers]]>
https://dmtcs.episciences.org/5155
Tue, 05 Feb 2019 16:08:07 +0100<![CDATA[$K_{1,3}$-covering red and blue points in the plane]]>
https://dmtcs.episciences.org/5126
3b$, there are too many red points and at
least $r-3b$ of them will remain uncovered in any $K_{1,3}$-covering.
Furthermore, in all the cases we provide efficient algorithms to compute the
corresponding coverings.
]]>3b$, there are too many red points and at
least $r-3b$ of them will remain uncovered in any $K_{1,3}$-covering.
Furthermore, in all the cases we provide efficient algorithms to compute the
corresponding coverings.
]]>Thu, 31 Jan 2019 17:01:00 +0100<![CDATA[Decision Problems for Subclasses of Rational Relations over Finite and
Infinite Words]]>
https://dmtcs.episciences.org/5141
Thu, 31 Jan 2019 16:49:43 +0100<![CDATA[An output-sensitive Algorithm to partition a Sequence of Integers into
Subsets with equal Sums]]>
https://dmtcs.episciences.org/5122
Thu, 24 Jan 2019 16:36:20 +0100<![CDATA[On the maximum number of minimum total dominating sets in forests]]>
https://dmtcs.episciences.org/5092
Wed, 23 Jan 2019 11:30:07 +0100<![CDATA[Binding Number, Toughness and General Matching Extendability in Graphs]]>
https://dmtcs.episciences.org/5091
Thu, 17 Jan 2019 13:37:26 +0100<![CDATA[Solving Two Conjectures regarding Codes for Location in Circulant Graphs]]>
https://dmtcs.episciences.org/5049
Tue, 08 Jan 2019 16:00:19 +0100<![CDATA[Sigma Partitioning: Complexity and Random Graphs]]>
https://dmtcs.episciences.org/5037
Mon, 17 Dec 2018 15:39:19 +0100<![CDATA[Solving the kernel perfect problem by (simple) forbidden subdigraphs for
digraphs in some families of generalized tournaments and generalized
bipartite tournaments]]>
https://dmtcs.episciences.org/5025
Tue, 11 Dec 2018 10:24:21 +0100<![CDATA[Pattern Avoidance for Random Permutations]]>
https://dmtcs.episciences.org/5011
Tue, 04 Dec 2018 15:42:38 +0100<![CDATA[Complexity of locally-injective homomorphisms to tournaments]]>
https://dmtcs.episciences.org/4999
Fri, 30 Nov 2018 11:33:11 +0100<![CDATA[Decycling a graph by the removal of a matching: new algorithmic and
structural aspects in some classes of graphs]]>
https://dmtcs.episciences.org/4979
Tue, 20 Nov 2018 11:33:15 +0100<![CDATA[On Almost Well-Covered Graphs of Girth at Least 6]]>
https://dmtcs.episciences.org/4982
Tue, 20 Nov 2018 11:28:34 +0100<![CDATA[A Note on Flips in Diagonal Rectangulations]]>
https://dmtcs.episciences.org/4943
Fri, 09 Nov 2018 15:34:53 +0100<![CDATA[General bounds on limited broadcast domination]]>
https://dmtcs.episciences.org/4923
Mon, 29 Oct 2018 17:37:28 +0100<![CDATA[IMP with exceptions over decorated logic]]>
https://dmtcs.episciences.org/4927
Mon, 29 Oct 2018 17:18:58 +0100<![CDATA[Pattern Avoidance in Reverse Double Lists]]>
https://dmtcs.episciences.org/4919
Mon, 29 Oct 2018 17:10:26 +0100<![CDATA[The 26 Wilf-equivalence classes of length five quasi-consecutive
patterns]]>
https://dmtcs.episciences.org/4912
Wed, 24 Oct 2018 11:21:40 +0200<![CDATA[Steiner Distance in Product Networks]]>
https://dmtcs.episciences.org/4887
Tue, 23 Oct 2018 11:14:34 +0200<![CDATA[Summation formulas for Fox-Wright function]]>
https://dmtcs.episciences.org/4889
Mon, 22 Oct 2018 14:29:30 +0200<![CDATA[Parameterized Power Vertex Cover]]>
https://dmtcs.episciences.org/4873
Mon, 08 Oct 2018 15:44:44 +0200<![CDATA[Fast strategies in biased Maker--Breaker games]]>
https://dmtcs.episciences.org/4874
Mon, 08 Oct 2018 15:37:12 +0200<![CDATA[On locally irregular decompositions and the 1-2 Conjecture in digraphs]]>
https://dmtcs.episciences.org/4859
Mon, 01 Oct 2018 14:11:10 +0200<![CDATA[Semitotal domination in trees]]>
https://dmtcs.episciences.org/4841
Fri, 28 Sep 2018 17:11:41 +0200<![CDATA[Convexity of tableau sets for type A Demazure characters (key
polynomials), parabolic Catalan numbers]]>
https://dmtcs.episciences.org/4697
Thu, 16 Aug 2018 10:27:14 +0200<![CDATA[Quadrant marked mesh patterns in 123-avoiding permutations]]>
https://dmtcs.episciences.org/4735
Fri, 03 Aug 2018 11:38:59 +0200<![CDATA[Tropical Vertex-Disjoint Cycles of a Vertex-Colored Digraph: Barter
Exchange with Multiple Items Per Agent]]>
https://dmtcs.episciences.org/4690
Tue, 31 Jul 2018 12:03:57 +0200<![CDATA[On fixed-parameter tractability of the mixed domination problem for
graphs with bounded tree-width]]>
https://dmtcs.episciences.org/4686
Tue, 31 Jul 2018 11:58:49 +0200<![CDATA[Weighted Regular Tree Grammars with Storage]]>
https://dmtcs.episciences.org/4660
Tue, 03 Jul 2018 16:54:58 +0200<![CDATA[Group twin coloring of graphs]]>
https://dmtcs.episciences.org/4649
Tue, 26 Jun 2018 17:14:31 +0200<![CDATA[Expected Number of Distinct Subsequences in Randomly Generated Binary
Strings]]>
https://dmtcs.episciences.org/4590
Tue, 26 Jun 2018 11:19:47 +0200<![CDATA[Continued fractions for permutation statistics]]>
https://dmtcs.episciences.org/4602
Mon, 25 Jun 2018 11:08:15 +0200<![CDATA[A Sufficient Condition for Graphic Sequences with Given Largest and
Smallest Entries, Length, and Sum]]>
https://dmtcs.episciences.org/4600
Mon, 25 Jun 2018 11:02:23 +0200<![CDATA[On a Class of Graphs with Large Total Domination Number]]>
https://dmtcs.episciences.org/4549
Mon, 04 Jun 2018 10:37:11 +0200<![CDATA[Computing Minimum Rainbow and Strong Rainbow Colorings of Block Graphs]]>
https://dmtcs.episciences.org/4547
0$ unless P = NP. We
then turn our attention to block graphs, which also form a subclass of chordal
graphs. We determine the strong rainbow connection number of block graphs, and
show it can be computed in linear time. Finally, we provide a polynomial-time
characterization of bridgeless block graphs with rainbow connection number at
most 4.
]]> 0$ unless P = NP. We
then turn our attention to block graphs, which also form a subclass of chordal
graphs. We determine the strong rainbow connection number of block graphs, and
show it can be computed in linear time. Finally, we provide a polynomial-time
characterization of bridgeless block graphs with rainbow connection number at
most 4.
]]>Mon, 04 Jun 2018 10:30:35 +0200<![CDATA[On neighbour sum-distinguishing $\{0,1\}$-edge-weightings of bipartite
graphs]]>
https://dmtcs.episciences.org/4554
Mon, 04 Jun 2018 10:27:12 +0200<![CDATA[Permutation complexity of images of Sturmian words by marked morphisms]]>
https://dmtcs.episciences.org/4551
Mon, 04 Jun 2018 10:22:33 +0200<![CDATA[Forbidden subgraphs for constant domination number]]>
https://dmtcs.episciences.org/4548
Mon, 04 Jun 2018 10:19:22 +0200<![CDATA[Proof of a local antimagic conjecture]]>
https://dmtcs.episciences.org/4550
Mon, 04 Jun 2018 10:15:49 +0200<![CDATA[Weakly threshold graphs]]>
https://dmtcs.episciences.org/4524
k} \min\{k,d_i\} - 1$ for all positive $k \leq
\max\{i:d_i \geq i-1\}$. The weakly threshold graphs are the realizations of
the weakly threshold sequences. The weakly threshold graphs properly include
the threshold graphs and satisfy pleasing extensions of many properties of
threshold graphs. We demonstrate a majorization property of weakly threshold
sequences and an iterative construction algorithm for weakly threshold graphs,
as well as a forbidden induced subgraph characterization. We conclude by
exactly enumerating weakly threshold sequences and graphs.
]]> k} \min\{k,d_i\} - 1$ for all positive $k \leq
\max\{i:d_i \geq i-1\}$. The weakly threshold graphs are the realizations of
the weakly threshold sequences. The weakly threshold graphs properly include
the threshold graphs and satisfy pleasing extensions of many properties of
threshold graphs. We demonstrate a majorization property of weakly threshold
sequences and an iterative construction algorithm for weakly threshold graphs,
as well as a forbidden induced subgraph characterization. We conclude by
exactly enumerating weakly threshold sequences and graphs.
]]>Mon, 04 Jun 2018 10:08:17 +0200<![CDATA[Rowmotion and generalized toggle groups]]>
https://dmtcs.episciences.org/4518
Fri, 25 May 2018 17:04:47 +0200<![CDATA[Annular and pants thrackles]]>
https://dmtcs.episciences.org/4534
Fri, 25 May 2018 16:59:37 +0200<![CDATA[A Linear Kernel for Planar Total Dominating Set]]>
https://dmtcs.episciences.org/4487
Wed, 16 May 2018 16:19:58 +0200<![CDATA[On interval number in cycle convexity]]>
https://dmtcs.episciences.org/4456
Mon, 07 May 2018 10:26:53 +0200<![CDATA[A Central Limit Theorem for Vincular Permutation Patterns]]>
https://dmtcs.episciences.org/4357
Mon, 26 Mar 2018 11:21:09 +0200<![CDATA[Non-adaptive Group Testing on Graphs]]>
https://dmtcs.episciences.org/4351
Mon, 26 Mar 2018 11:13:44 +0200<![CDATA[Protected node profile of Tries]]>
https://dmtcs.episciences.org/4386
Mon, 26 Mar 2018 11:04:02 +0200<![CDATA[Asymptotic results on Klazar set partition avoidance]]>
https://dmtcs.episciences.org/4373
Mon, 19 Mar 2018 11:02:07 +0100<![CDATA[On subtrees of the representation tree in rational base numeration
systems]]>
https://dmtcs.episciences.org/4331
Mon, 05 Mar 2018 09:53:22 +0100<![CDATA[Finding Hamilton cycles in random intersection graphs]]>
https://dmtcs.episciences.org/4339
Mon, 05 Mar 2018 09:48:23 +0100<![CDATA[Growing and Destroying Catalan-Stanley Trees]]>
https://dmtcs.episciences.org/4322
Wed, 28 Feb 2018 16:37:21 +0100<![CDATA[On consecutive pattern-avoiding permutations of length 4, 5 and beyond]]>
https://dmtcs.episciences.org/4303
Mon, 26 Feb 2018 10:53:53 +0100<![CDATA[Equivalence classes of mesh patterns with a dominating pattern]]>
https://dmtcs.episciences.org/4265
Fri, 09 Feb 2018 10:58:50 +0100<![CDATA[Improving bounds on packing densities of 4-point permutations]]>
https://dmtcs.episciences.org/4263
Tue, 06 Feb 2018 17:39:16 +0100<![CDATA[A Study of $k$-dipath Colourings of Oriented Graphs]]>
https://dmtcs.episciences.org/4236
Thu, 01 Feb 2018 14:42:05 +0100<![CDATA[Weak embeddings of posets to the Boolean lattice]]>
https://dmtcs.episciences.org/4232
Wed, 24 Jan 2018 14:06:55 +0100<![CDATA[A bijection between the set of nesting-similarity classes and L & P
matchings]]>
https://dmtcs.episciences.org/4220
Mon, 22 Jan 2018 08:55:56 +0100<![CDATA[Hitting minors, subdivisions, and immersions in tournaments]]>
https://dmtcs.episciences.org/4212
Wed, 17 Jan 2018 09:38:58 +0100<![CDATA[A Variation on Chip-Firing: the diffusion game]]>
https://dmtcs.episciences.org/4214
Wed, 17 Jan 2018 09:30:10 +0100<![CDATA[Three matching intersection property for matching covered graphs]]>
https://dmtcs.episciences.org/4207
Mon, 15 Jan 2018 11:43:15 +0100<![CDATA[On Minimum Maximal Distance-k Matchings]]>
https://dmtcs.episciences.org/4199
Thu, 11 Jan 2018 14:10:17 +0100<![CDATA[Graphs of Edge-Intersecting Non-Splitting Paths in a Tree:
Representations of Holes-Part II]]>
https://dmtcs.episciences.org/4197
is
a representation of G.
Our goal is to characterize the representation of chordless ENPT cycles
(holes). To achieve this goal, we first assume that the EPT graph induced by
the vertices of an ENPT hole is given. In [2] we introduce three assumptions
(P1), (P2), (P3) defined on EPT, ENPT pairs of graphs. In the same study, we
define two problems HamiltonianPairRec, P3-HamiltonianPairRec and characterize
the representations of ENPT holes that satisfy (P1), (P2), (P3).
In this work, we continue our work by relaxing these three assumptions one by
one. We characterize the representations of ENPT holes satisfying (P3) by
providing a polynomial-time algorithm to solve P3-HamiltonianPairRec. We also
show that there does not exist a polynomial-time algorithm to solve
HamiltonianPairRec, unless P=NP.
]]> is
a representation of G.
Our goal is to characterize the representation of chordless ENPT cycles
(holes). To achieve this goal, we first assume that the EPT graph induced by
the vertices of an ENPT hole is given. In [2] we introduce three assumptions
(P1), (P2), (P3) defined on EPT, ENPT pairs of graphs. In the same study, we
define two problems HamiltonianPairRec, P3-HamiltonianPairRec and characterize
the representations of ENPT holes that satisfy (P1), (P2), (P3).
In this work, we continue our work by relaxing these three assumptions one by
one. We characterize the representations of ENPT holes satisfying (P3) by
providing a polynomial-time algorithm to solve P3-HamiltonianPairRec. We also
show that there does not exist a polynomial-time algorithm to solve
HamiltonianPairRec, unless P=NP.
]]>Thu, 11 Jan 2018 13:36:58 +0100<![CDATA[Monotone Simultaneous Paths Embeddings in $\mathbb{R}^d$]]>
https://dmtcs.episciences.org/4177
Fri, 05 Jan 2018 11:41:38 +0100<![CDATA[Best and worst case permutations for random online domination of the
path]]>
https://dmtcs.episciences.org/4145
Wed, 20 Dec 2017 11:48:15 +0100<![CDATA[Total Domination, Connected Vertex Cover and Steiner Tree with Conflicts]]>
https://dmtcs.episciences.org/4154
Wed, 20 Dec 2017 11:43:45 +0100<![CDATA[Multidimensional Binary Vector Assignment problem: standard, structural
and above guarantee parameterizations]]>
https://dmtcs.episciences.org/4150
Wed, 20 Dec 2017 11:33:20 +0100<![CDATA[Asymptotic distribution of fixed points of pattern-avoiding involutions]]>
https://dmtcs.episciences.org/4135
Mon, 11 Dec 2017 13:37:42 +0100<![CDATA[A Characterization for Decidable Separability by Piecewise Testable
Languages]]>
https://dmtcs.episciences.org/4131
Mon, 11 Dec 2017 11:46:30 +0100<![CDATA[Splittability and 1-amalgamability of permutation classes]]>
https://dmtcs.episciences.org/4125
Tue, 05 Dec 2017 10:56:28 +0100<![CDATA[Parabolic Catalan numbers count flagged Schur functions and their
appearances as type A Demazure characters (key polynomials)]]>
https://dmtcs.episciences.org/4119
Tue, 05 Dec 2017 10:50:02 +0100<![CDATA[Self-Stabilizing Disconnected Components Detection and Rooted Shortest-Path Tree Maintenance in Polynomial Steps]]>
https://dmtcs.episciences.org/4116
Thu, 30 Nov 2017 17:05:03 +0100<![CDATA[Periodic balanced binary triangles]]>
https://dmtcs.episciences.org/4101
Tue, 28 Nov 2017 20:32:42 +0100<![CDATA[Witness structures and immediate snapshot complexes]]>
https://dmtcs.episciences.org/4086
Tue, 28 Nov 2017 11:19:21 +0100<![CDATA[A sufficient condition for a balanced bipartite digraph to be
hamiltonian]]>
https://dmtcs.episciences.org/4058
Fri, 10 Nov 2017 13:31:54 +0100<![CDATA[Circular Separation Dimension of a Subclass of Planar Graphs]]>
https://dmtcs.episciences.org/4031
Fri, 03 Nov 2017 13:57:46 +0100<![CDATA[Depth, Highness and DNR degrees]]>
https://dmtcs.episciences.org/4012
Thu, 26 Oct 2017 10:22:26 +0200<![CDATA[On path-cycle decompositions of triangle-free graphs]]>
https://dmtcs.episciences.org/4010
Thu, 26 Oct 2017 10:17:39 +0200<![CDATA[Tight upper bound on the maximum anti-forcing numbers of graphs]]>
https://dmtcs.episciences.org/3981
Tue, 17 Oct 2017 11:07:09 +0200<![CDATA[Longest Gapped Repeats and Palindromes]]>
https://dmtcs.episciences.org/3988
Fri, 13 Oct 2017 14:32:21 +0200<![CDATA[On rank-width of even-hole-free graphs]]>
https://dmtcs.episciences.org/3827
Thu, 05 Oct 2017 13:39:06 +0200<![CDATA[Binary Codes and Period-2 Orbits of Sequential Dynamical Systems]]>
https://dmtcs.episciences.org/3971
Tue, 03 Oct 2017 11:40:34 +0200<![CDATA[Lattice paths with catastrophes]]>
https://dmtcs.episciences.org/3967
Fri, 29 Sep 2017 16:58:21 +0200<![CDATA[Irreversible 2-conversion set in graphs of bounded degree]]>
https://dmtcs.episciences.org/3952
Tue, 26 Sep 2017 13:54:32 +0200<![CDATA[Inkdots as advice for finite automata]]>
https://dmtcs.episciences.org/3941
Tue, 26 Sep 2017 13:50:45 +0200<![CDATA[Refined Enumeration of Corners in Tree-like Tableaux]]>
https://dmtcs.episciences.org/3937
Tue, 26 Sep 2017 13:47:44 +0200<![CDATA[Tight Euler tours in uniform hypergraphs - computational aspects]]>
https://dmtcs.episciences.org/3934
Tue, 26 Sep 2017 13:43:07 +0200<![CDATA[Stammering tableaux]]>
https://dmtcs.episciences.org/3930
Fri, 15 Sep 2017 13:36:00 +0200<![CDATA[Post-surjectivity and balancedness of cellular automata over groups]]>
https://dmtcs.episciences.org/3918
Fri, 15 Sep 2017 13:30:58 +0200<![CDATA[Characterizations of minimal dominating sets and the well-dominated
property in lexicographic product graphs]]>
https://dmtcs.episciences.org/3865
Wed, 30 Aug 2017 15:49:35 +0200<![CDATA[On a combination of the 1-2-3 Conjecture and the Antimagic Labelling Conjecture]]>
https://dmtcs.episciences.org/3849
Tue, 08 Aug 2017 12:14:00 +0200<![CDATA[Asymptotics of the occupancy scheme in a random environment and its
applications to tries]]>
https://dmtcs.episciences.org/3842
Fri, 04 Aug 2017 20:31:07 +0200<![CDATA[Rises in forests of binary shrubs]]>
https://dmtcs.episciences.org/3800
Wed, 19 Jul 2017 11:55:50 +0200<![CDATA[A Bijection on Classes Enumerated by the Schröder Numbers]]>
https://dmtcs.episciences.org/3790
Wed, 19 Jul 2017 11:46:44 +0200<![CDATA[Evaluations of series of the $q$-Watson, $q$-Dixon, and $q$-Whipple type]]>
https://dmtcs.episciences.org/3739
Tue, 27 Jun 2017 10:30:43 +0200<![CDATA[Nonrepetitive edge-colorings of trees]]>
https://dmtcs.episciences.org/3724
Tue, 27 Jun 2017 10:27:45 +0200<![CDATA[Equivalence of the filament and overlap graphs of subtrees of limited
trees]]>
https://dmtcs.episciences.org/3715
Tue, 20 Jun 2017 11:37:51 +0200<![CDATA[Composing short 3-compressing words on a 2-letter alphabet]]>
https://dmtcs.episciences.org/3709
Tue, 20 Jun 2017 11:34:52 +0200<![CDATA[Graphs of Edge-Intersecting and Non-Splitting One Bend Paths in a Grid]]>
https://dmtcs.episciences.org/3708
Mon, 12 Jun 2017 13:18:19 +0200<![CDATA[Improved kernels for Signed Max Cut parameterized above lower bound on
(r,l)-graphs]]>
https://dmtcs.episciences.org/3682
Wed, 07 Jun 2017 11:25:02 +0200<![CDATA[On universal partial words]]>
https://dmtcs.episciences.org/3690
Wed, 31 May 2017 11:00:18 +0200<![CDATA[The quotients between the (revised) Szeged index and Wiener index of
graphs]]>
https://dmtcs.episciences.org/3314
Tue, 09 May 2017 10:48:50 +0200<![CDATA[Decidability of multiset, set and numerically decipherable directed
figure codes]]>
https://dmtcs.episciences.org/3301
Wed, 03 May 2017 10:17:40 +0200<![CDATA[Pairwise Stability in Two Sided Market with Strictly Increasing
Valuation Functions]]>
https://dmtcs.episciences.org/3259
Wed, 12 Apr 2017 14:50:47 +0200<![CDATA[The permutation class Av(4213,2143)]]>
https://dmtcs.episciences.org/3236
Tue, 04 Apr 2017 16:33:15 +0200<![CDATA[S-Restricted Compositions Revisited]]>
https://dmtcs.episciences.org/3220
Tue, 28 Mar 2017 10:24:04 +0200<![CDATA[On the shelling antimatroids of split graphs]]>
https://dmtcs.episciences.org/3201
Fri, 24 Mar 2017 17:07:54 +0100<![CDATA[Wilf classification of triples of 4-letter patterns II]]>
https://dmtcs.episciences.org/3219
Fri, 24 Mar 2017 16:40:12 +0100<![CDATA[Wilf classification of triples of 4-letter patterns I]]>
https://dmtcs.episciences.org/3218
Fri, 24 Mar 2017 16:37:57 +0100<![CDATA[A class of symmetric difference-closed sets related to commuting involutions]]>
https://dmtcs.episciences.org/3210
Thu, 23 Mar 2017 11:33:33 +0100<![CDATA[Permutation Pattern matching in (213, 231)-avoiding permutations]]>
https://dmtcs.episciences.org/3199
Wed, 22 Mar 2017 11:10:58 +0100<![CDATA[The Existence of Planar Hypotraceable Oriented Graphs]]>
https://dmtcs.episciences.org/3149
Thu, 16 Mar 2017 14:27:09 +0100<![CDATA[A characterization of trees with equal 2-domination and 2-independence
numbers]]>
https://dmtcs.episciences.org/3158
Thu, 09 Mar 2017 08:53:33 +0100<![CDATA[A New Game Invariant of Graphs: the Game Distinguishing Number]]>
https://dmtcs.episciences.org/3127
Thu, 02 Mar 2017 15:48:34 +0100<![CDATA[Descent c-Wilf Equivalence]]>
https://dmtcs.episciences.org/3164
Thu, 02 Mar 2017 15:13:07 +0100<![CDATA[Right-jumps and pattern avoiding permutations]]>
https://dmtcs.episciences.org/3131
Fri, 10 Feb 2017 09:11:59 +0100<![CDATA[Postorder Preimages]]>
https://dmtcs.episciences.org/3116
Mon, 06 Feb 2017 17:17:25 +0100<![CDATA[Mixing Times of Markov Chains on Degree Constrained Orientations of
Planar Graphs]]>
https://dmtcs.episciences.org/3121
Fri, 03 Feb 2017 11:43:52 +0100<![CDATA[The Complexity of Pattern Matching for $321$-Avoiding and Skew-Merged
Permutations]]>
https://dmtcs.episciences.org/2607
Wed, 21 Dec 2016 15:02:07 +0100<![CDATA[Enumeration of Corners in Tree-like Tableaux]]>
https://dmtcs.episciences.org/2546
Fri, 02 Dec 2016 14:27:20 +0100<![CDATA[Stokes posets and serpent nests]]>
https://dmtcs.episciences.org/2572
Fri, 02 Dec 2016 14:12:07 +0100<![CDATA[Constructions of words rich in palindromes and pseudopalindromes]]>
https://dmtcs.episciences.org/2202
Tue, 22 Nov 2016 15:00:59 +0100<![CDATA[Sequential selection of the k best out of nrankable objects]]>
https://dmtcs.episciences.org/2185
infinity and in the corresponding asymptotic performance of the threshold algorithm.]]> infinity and in the corresponding asymptotic performance of the threshold algorithm.]]>Fri, 28 Oct 2016 12:01:41 +0200<![CDATA[Most Complex Regular Ideal Languages]]>
https://dmtcs.episciences.org/2167
Mon, 17 Oct 2016 11:42:14 +0200<![CDATA[Ramsey-type theorems for lines in 3-space]]>
https://dmtcs.episciences.org/2036
Mon, 19 Sep 2016 10:08:44 +0200<![CDATA[Pattern avoidance for set partitions à la Klazar]]>
https://dmtcs.episciences.org/2023
k$ and all partitions
$\tau_1$ of $[k]$ with exactly two blocks. We conjecture that this result holds
for all partitions $\tau_1$ of $[k]$. Finally, we enumerate $\Pi_n(\tau)$ for
all partitions $\tau$ of $[4]$.
]]>k$ and all partitions
$\tau_1$ of $[k]$ with exactly two blocks. We conjecture that this result holds
for all partitions $\tau_1$ of $[k]$. Finally, we enumerate $\Pi_n(\tau)$ for
all partitions $\tau$ of $[4]$.
]]>Wed, 07 Sep 2016 09:52:25 +0200<![CDATA[Linear recognition of generalized Fibonacci cubes $Q_h(111)$]]>
https://dmtcs.episciences.org/2165
Sat, 03 Sep 2016 00:00:00 +0200<![CDATA[Matchings of quadratic size extend to long cycles in hypercubes]]>
https://dmtcs.episciences.org/2012
Thu, 01 Sep 2016 17:18:52 +0200<![CDATA[Connected Tropical Subgraphs in Vertex-Colored Graphs]]>
https://dmtcs.episciences.org/2151
Sun, 07 Aug 2016 00:00:00 +0200<![CDATA[An extremal problem for a graphic sequence to have a realization containing every 2-tree with prescribed size]]>
https://dmtcs.episciences.org/2152
-tree if $G=K_3$, or $G$ has a vertex $v$ of degree 2, whose neighbors are adjacent, and $G-v$ is a 2-tree. Clearly, if $G$ is a 2-tree on $n$ vertices, then $|E(G)|=2n-3$. A non-increasing sequence $\pi =(d_1, \ldots ,d_n)$ of nonnegative integers is a graphic sequence if it is realizable by a simple graph $G$ on $n$ vertices. Yin and Li (Acta Mathematica Sinica, English Series, 25(2009)795–802) proved that if $k \geq 2$, $n \geq \frac{9}{2}k^2 + \frac{19}{2}k$ and $\pi =(d_1, \ldots ,d_n)$ is a graphic sequence with $\sum \limits_{i=1}^n d_i > (k-2)n$, then $\pi$ has a realization containing every tree on $k$ vertices as a subgraph. Moreover, the lower bound $(k-2)n$ is the best possible. This is a variation of a conjecture due to Erdős and Sós. In this paper, we investigate an analogue extremal problem for 2-trees and prove that if $k \geq 3$, $n \geq 2k^2-k$ and $\pi =(d_1, \ldots ,d_n)$ is a graphic sequence with $\sum \limits_{i=1}^n d_i > \frac{4kn}{3} - \frac{5n}{3}$ then $\pi$ has a realization containing every 2-tree on $k$ vertices as a subgraph. We also show that the lower bound $\frac{4kn}{3} - \frac{5n}{3}$ is almost the best possible.]]>-tree if $G=K_3$, or $G$ has a vertex $v$ of degree 2, whose neighbors are adjacent, and $G-v$ is a 2-tree. Clearly, if $G$ is a 2-tree on $n$ vertices, then $|E(G)|=2n-3$. A non-increasing sequence $\pi =(d_1, \ldots ,d_n)$ of nonnegative integers is a graphic sequence if it is realizable by a simple graph $G$ on $n$ vertices. Yin and Li (Acta Mathematica Sinica, English Series, 25(2009)795–802) proved that if $k \geq 2$, $n \geq \frac{9}{2}k^2 + \frac{19}{2}k$ and $\pi =(d_1, \ldots ,d_n)$ is a graphic sequence with $\sum \limits_{i=1}^n d_i > (k-2)n$, then $\pi$ has a realization containing every tree on $k$ vertices as a subgraph. Moreover, the lower bound $(k-2)n$ is the best possible. This is a variation of a conjecture due to Erdős and Sós. In this paper, we investigate an analogue extremal problem for 2-trees and prove that if $k \geq 3$, $n \geq 2k^2-k$ and $\pi =(d_1, \ldots ,d_n)$ is a graphic sequence with $\sum \limits_{i=1}^n d_i > \frac{4kn}{3} - \frac{5n}{3}$ then $\pi$ has a realization containing every 2-tree on $k$ vertices as a subgraph. We also show that the lower bound $\frac{4kn}{3} - \frac{5n}{3}$ is almost the best possible.]]>Sat, 06 Aug 2016 00:00:00 +0200<![CDATA[A Context free language associated with interval maps]]>
https://dmtcs.episciences.org/3197
Sat, 06 Aug 2016 00:00:00 +0200<![CDATA[On degree-sequence characterization and the extremal number of edges for various Hamiltonian properties under fault tolerance]]>
https://dmtcs.episciences.org/2149
$k$-vertex fault traceable, $k$-vertex fault Hamiltonian, or $k$-vertex fault Hamiltonian-connected if $G-F$ remains traceable, Hamiltonian, and Hamiltonian-connected for all $F$ with $0 \leq |F| \leq k$, respectively. The notations $h_1(n, \delta ,k)$, $h_2(n, \delta ,k)$, and $h_3(n, \delta ,k)$ denote the minimum number of edges required to guarantee an $n$-vertex graph with minimum degree $\delta (G) \geq \delta$ to be $k$-vertex fault traceable, $k$-vertex fault Hamiltonian, and $k$-vertex fault Hamiltonian-connected, respectively. In this paper, we establish a theorem which uses the degree sequence of a given graph to characterize the $k$-vertex fault traceability/hamiltonicity/Hamiltonian-connectivity, respectively. Then we use this theorem to obtain the formulas for $h_i(n, \delta ,k)$ for $1 \leq i \leq 3$, which improves and extends the known results for $k=0$.]]>$k$-vertex fault traceable, $k$-vertex fault Hamiltonian, or $k$-vertex fault Hamiltonian-connected if $G-F$ remains traceable, Hamiltonian, and Hamiltonian-connected for all $F$ with $0 \leq |F| \leq k$, respectively. The notations $h_1(n, \delta ,k)$, $h_2(n, \delta ,k)$, and $h_3(n, \delta ,k)$ denote the minimum number of edges required to guarantee an $n$-vertex graph with minimum degree $\delta (G) \geq \delta$ to be $k$-vertex fault traceable, $k$-vertex fault Hamiltonian, and $k$-vertex fault Hamiltonian-connected, respectively. In this paper, we establish a theorem which uses the degree sequence of a given graph to characterize the $k$-vertex fault traceability/hamiltonicity/Hamiltonian-connectivity, respectively. Then we use this theorem to obtain the formulas for $h_i(n, \delta ,k)$ for $1 \leq i \leq 3$, which improves and extends the known results for $k=0$.]]>Tue, 02 Aug 2016 00:00:00 +0200<![CDATA[Energy-optimal algorithms for computing aggregative functions in random networks]]>
https://dmtcs.episciences.org/2160
Mon, 25 Jul 2016 00:00:00 +0200<![CDATA[Edge Disjoint Hamilton Cycles in Knödel Graphs]]>
https://dmtcs.episciences.org/2148
Fri, 22 Jul 2016 00:00:00 +0200<![CDATA[Pattern avoidance in forests of binary shrubs]]>
https://dmtcs.episciences.org/1541
Thu, 21 Jul 2016 12:09:41 +0200<![CDATA[Traceability of locally hamiltonian and locally traceable graphs]]>
https://dmtcs.episciences.org/2144
locally $\mathcal{P}$ if $\langle N(v) \rangle$ has property $\mathcal{P}$ for every $v \in V(G)$ where $\langle N(v) \rangle$ is the induced graph on the open neighbourhood of the vertex $v$. Pareek and Skupien (C. M. Pareek and Z. Skupien , On the smallest non-Hamiltonian locally Hamiltonian graph, J. Univ. Kuwait (Sci.), 10:9 - 17, 1983) posed the following two questions. Question 1 Is 9 the smallest order of a connected nontraceable locally traceable graph? Question 2 Is 14 the smallest order of a connected nontraceable locally hamiltonian graph? We answer the second question in the affirmative, but show that the correct number for the first question is 10. We develop a technique to construct connected locally hamiltonian and locally traceable graphs that are not traceable. We use this technique to construct such graphs with various prescribed properties.]]>locally $\mathcal{P}$ if $\langle N(v) \rangle$ has property $\mathcal{P}$ for every $v \in V(G)$ where $\langle N(v) \rangle$ is the induced graph on the open neighbourhood of the vertex $v$. Pareek and Skupien (C. M. Pareek and Z. Skupien , On the smallest non-Hamiltonian locally Hamiltonian graph, J. Univ. Kuwait (Sci.), 10:9 - 17, 1983) posed the following two questions. Question 1 Is 9 the smallest order of a connected nontraceable locally traceable graph? Question 2 Is 14 the smallest order of a connected nontraceable locally hamiltonian graph? We answer the second question in the affirmative, but show that the correct number for the first question is 10. We develop a technique to construct connected locally hamiltonian and locally traceable graphs that are not traceable. We use this technique to construct such graphs with various prescribed properties.]]>Fri, 01 Jul 2016 00:00:00 +0200<![CDATA[On the complexity of edge-colored subgraph partitioning problems in network optimization]]>
https://dmtcs.episciences.org/2159
monochromatic if all its edges have the same color, and called multicolored if all its edges have distinct colors. The monochromatic clique and multicolored cycle partition problems have important applications in the problems of network optimization arising in information science and operations research. We investigate the computational complexity of the problems of determining the minimum number of monochromatic cliques or multicolored cycles that, respectively, partition $V(G)$. We show that the minimum monochromatic clique partition problem is APX-hard on monochromatic-diamond-free graphs, and APX-complete on monochromatic-diamond-free graphs in which the size of a maximum monochromatic clique is bounded by a constant. We also show that the minimum multicolored cycle partition problem is NP-complete, even if the input graph $G$ is triangle-free. Moreover, for the weighted version of the minimum monochromatic clique partition problem on monochromatic-diamond-free graphs, we derive an approximation algorithm with (tight) approximation guarantee ln $|V(G)|+1$.]]>monochromatic if all its edges have the same color, and called multicolored if all its edges have distinct colors. The monochromatic clique and multicolored cycle partition problems have important applications in the problems of network optimization arising in information science and operations research. We investigate the computational complexity of the problems of determining the minimum number of monochromatic cliques or multicolored cycles that, respectively, partition $V(G)$. We show that the minimum monochromatic clique partition problem is APX-hard on monochromatic-diamond-free graphs, and APX-complete on monochromatic-diamond-free graphs in which the size of a maximum monochromatic clique is bounded by a constant. We also show that the minimum multicolored cycle partition problem is NP-complete, even if the input graph $G$ is triangle-free. Moreover, for the weighted version of the minimum monochromatic clique partition problem on monochromatic-diamond-free graphs, we derive an approximation algorithm with (tight) approximation guarantee ln $|V(G)|+1$.]]>Fri, 01 Jul 2016 00:00:00 +0200<![CDATA[Pattern Avoidance in Task-Precedence Posets]]>
https://dmtcs.episciences.org/1515
Fri, 24 Jun 2016 15:02:33 +0200<![CDATA[Packing densities of layered permutations and the minimum number of
monotone sequences in layered permutations]]>
https://dmtcs.episciences.org/1516
Thu, 23 Jun 2016 13:06:48 +0200<![CDATA[Variance and Covariance of Several Simultaneous Outputs of a Markov
Chain]]>
https://dmtcs.episciences.org/1517
Thu, 23 Jun 2016 12:59:03 +0200<![CDATA[The inapproximability for the $(0,1)$-additive number]]>
https://dmtcs.episciences.org/2145
additive labeling of a graph $G$ is a function $\ell :V(G) \rightarrow \mathbb{N}$, such that for every two adjacent vertices $v$ and $u$ of $G$, $\Sigma_{w \sim v} \ell (w) \neq \Sigma_{w \sim u} \ell (w)$ ($x \sim y$ means that $x$ is joined to $y$). The additive number of $G$, denoted by $\eta (G)$, is the minimum number $k$ such that $G$ has a additive labeling $\ell : V(G) \rightarrow \mathbb{N}_k$. The additive choosability of a graph $G$, denoted by $\eta_\ell (G)$, is the smallest number $k$ such that $G$ has an additive labeling for any assignment of lists of size $k$ to the vertices of $G$, such that the label of each vertex belongs to its own list. Seamone in his PhD thesis conjectured that for every graph $G$, $\eta(G)= \eta_\ell (G)$. We give a negative answer to this conjecture and we show that for every $k$ there is a graph $G$ such that $\eta_\ell (G) - \eta(G) \geq k$. A $(0,1)$-additive labeling of a graph $G$ is a function $\ell :V(G) \rightarrow \{0,1 \}$, such that for every two adjacent vertices $v$ and $u$ of $G$, $\Sigma_{w \sim v} \ell (w) \neq \Sigma_{w \sim u} \ell (w)$. A graph may lack any $(0,1)$-additive labeling. We show that it is NP-complete to decide whether a $(0,1)$-additive labeling exists for some families of graphs such as perfect graphs and planar triangle-free graphs. For a graph $G$ with some $(0,1)$-additive labelings, the $(0,1)$-additive number of $G$ is defined as $\sigma_1 (G) = \mathrm{min}_{\ell \in \Gamma} \Sigma_{v \in V (G)} \ell (v)$ where $\Gamma$ is the set of $(0,1)$-additive labelings of $G$. We prove that given a planar graph that admits a $(0,1)$-additive labeling, for all $\epsilon > 0$ , approximating the $(0,1)$-additive number within $n^{1-\epsilon}$ is NP-hard.]]>additive labeling of a graph $G$ is a function $\ell :V(G) \rightarrow \mathbb{N}$, such that for every two adjacent vertices $v$ and $u$ of $G$, $\Sigma_{w \sim v} \ell (w) \neq \Sigma_{w \sim u} \ell (w)$ ($x \sim y$ means that $x$ is joined to $y$). The additive number of $G$, denoted by $\eta (G)$, is the minimum number $k$ such that $G$ has a additive labeling $\ell : V(G) \rightarrow \mathbb{N}_k$. The additive choosability of a graph $G$, denoted by $\eta_\ell (G)$, is the smallest number $k$ such that $G$ has an additive labeling for any assignment of lists of size $k$ to the vertices of $G$, such that the label of each vertex belongs to its own list. Seamone in his PhD thesis conjectured that for every graph $G$, $\eta(G)= \eta_\ell (G)$. We give a negative answer to this conjecture and we show that for every $k$ there is a graph $G$ such that $\eta_\ell (G) - \eta(G) \geq k$. A $(0,1)$-additive labeling of a graph $G$ is a function $\ell :V(G) \rightarrow \{0,1 \}$, such that for every two adjacent vertices $v$ and $u$ of $G$, $\Sigma_{w \sim v} \ell (w) \neq \Sigma_{w \sim u} \ell (w)$. A graph may lack any $(0,1)$-additive labeling. We show that it is NP-complete to decide whether a $(0,1)$-additive labeling exists for some families of graphs such as perfect graphs and planar triangle-free graphs. For a graph $G$ with some $(0,1)$-additive labelings, the $(0,1)$-additive number of $G$ is defined as $\sigma_1 (G) = \mathrm{min}_{\ell \in \Gamma} \Sigma_{v \in V (G)} \ell (v)$ where $\Gamma$ is the set of $(0,1)$-additive labelings of $G$. We prove that given a planar graph that admits a $(0,1)$-additive labeling, for all $\epsilon > 0$ , approximating the $(0,1)$-additive number within $n^{1-\epsilon}$ is NP-hard.]]>Fri, 17 Jun 2016 00:00:00 +0200<![CDATA[The irregularity of two types of trees]]>
https://dmtcs.episciences.org/2146
Wed, 08 Jun 2016 00:00:00 +0200<![CDATA[A proof of Zhil'tsov's theorem on decidability of equational theory of epigroups]]>
https://dmtcs.episciences.org/2155
Tue, 07 Jun 2016 00:00:00 +0200<![CDATA[Partitioning the vertex set of $G$ to make $G\,\Box\, H$ an efficient
open domination graph]]>
https://dmtcs.episciences.org/1503
Thu, 02 Jun 2016 16:21:12 +0200<![CDATA[Snow Leopard Permutations and Their Even and Odd Threads]]>
https://dmtcs.episciences.org/1489
Wed, 01 Jun 2016 09:43:53 +0200<![CDATA[Statistics for 3-letter patterns with repetitions in compositions]]>
https://dmtcs.episciences.org/2156
Tue, 31 May 2016 00:00:00 +0200<![CDATA[Permutations of context-free, ET0L and indexed languages]]>
https://dmtcs.episciences.org/2164
Tue, 31 May 2016 00:00:00 +0200<![CDATA[Asymptotics for minimal overlapping patterns for generalized Euler
permutations, standard tableaux of rectangular shape, and column strict
arrays]]>
https://dmtcs.episciences.org/1490
Fri, 20 May 2016 18:16:41 +0200<![CDATA[Planar graphs with $\Delta \geq 7$ and no triangle adjacent to a $C_4$ are minimally edge and total choosable]]>
https://dmtcs.episciences.org/2147
list edge coloring and list total coloring. Edge coloring is the problem of coloring the edges while ensuring that two edges that are adjacent receive different colors. Total coloring is the problem of coloring the edges and the vertices while ensuring that two edges that are adjacent, two vertices that are adjacent, or a vertex and an edge that are incident receive different colors. In their list extensions, instead of having the same set of colors for the whole graph, every vertex or edge is assigned some set of colors and has to be colored from it. A graph is minimally edge or total choosable if it is list $\Delta$-edge-colorable or list $(\Delta +1)$-total-colorable, respectively, where $\Delta$ is the maximum degree in the graph. It is already known that planar graphs with $\Delta \geq 8$ and no triangle adjacent to a $C_4$ are minimally edge and total choosable (Li Xu 2011), and that planar graphs with $\Delta \geq 7$ and no triangle sharing a vertex with a $C_4$ or no triangle adjacent to a $C_k (\forall 3 \leq k \leq 6)$ are minimally total colorable (Wang Wu 2011). We strengthen here these results and prove that planar graphs with $\Delta \geq 7$ and no triangle adjacent to a $C_4$ are minimally edge and total choosable.]]>list edge coloring and list total coloring. Edge coloring is the problem of coloring the edges while ensuring that two edges that are adjacent receive different colors. Total coloring is the problem of coloring the edges and the vertices while ensuring that two edges that are adjacent, two vertices that are adjacent, or a vertex and an edge that are incident receive different colors. In their list extensions, instead of having the same set of colors for the whole graph, every vertex or edge is assigned some set of colors and has to be colored from it. A graph is minimally edge or total choosable if it is list $\Delta$-edge-colorable or list $(\Delta +1)$-total-colorable, respectively, where $\Delta$ is the maximum degree in the graph. It is already known that planar graphs with $\Delta \geq 8$ and no triangle adjacent to a $C_4$ are minimally edge and total choosable (Li Xu 2011), and that planar graphs with $\Delta \geq 7$ and no triangle sharing a vertex with a $C_4$ or no triangle adjacent to a $C_k (\forall 3 \leq k \leq 6)$ are minimally total colorable (Wang Wu 2011). We strengthen here these results and prove that planar graphs with $\Delta \geq 7$ and no triangle adjacent to a $C_4$ are minimally edge and total choosable.]]>Thu, 12 May 2016 00:00:00 +0200<![CDATA[Automata in SageMath---Combinatorics meet Theoretical Computer Science]]>
https://dmtcs.episciences.org/1475
Tue, 10 May 2016 10:00:47 +0200<![CDATA[Combinatorial optimization in networks with Shared Risk Link Groups]]>
https://dmtcs.episciences.org/1459
Tue, 03 May 2016 11:30:11 +0200<![CDATA[Rainbow eulerian multidigraphs and the product of cycles]]>
https://dmtcs.episciences.org/2153
Thu, 21 Apr 2016 00:00:00 +0200<![CDATA[Robust Wireless Sensor Network Deployment]]>
https://dmtcs.episciences.org/2163
Thu, 21 Apr 2016 00:00:00 +0200<![CDATA[On the number of vertices of each rank in phylogenetic trees and their
generalizations]]>
https://dmtcs.episciences.org/1431
Mon, 11 Apr 2016 21:55:16 +0200<![CDATA[Heredity for generalized power domination]]>
https://dmtcs.episciences.org/1422
Sun, 03 Apr 2016 23:25:50 +0200<![CDATA[Patterns in Inversion Sequences I]]>
https://dmtcs.episciences.org/1421
\pi_i \}|$. This correspondence makes it
a natural extension to study patterns in inversion sequences much in the same
way that patterns have been studied in permutations. This paper, the first of
two on patterns in inversion sequences, focuses on the enumeration of inversion
sequences that avoid words of length three. Our results connect patterns in
inversion sequences to a number of well-known numerical sequences including
Fibonacci numbers, Bell numbers, Schr\"oder numbers, and Euler up/down numbers.
]]> \pi_i \}|$. This correspondence makes it
a natural extension to study patterns in inversion sequences much in the same
way that patterns have been studied in permutations. This paper, the first of
two on patterns in inversion sequences, focuses on the enumeration of inversion
sequences that avoid words of length three. Our results connect patterns in
inversion sequences to a number of well-known numerical sequences including
Fibonacci numbers, Bell numbers, Schr\"oder numbers, and Euler up/down numbers.
]]>Thu, 31 Mar 2016 11:47:19 +0200<![CDATA[Open k-monopolies in graphs: complexity and related concepts]]>
https://dmtcs.episciences.org/1407
Tue, 29 Mar 2016 21:20:25 +0200<![CDATA[An Erdős--Hajnal analogue for permutation classes]]>
https://dmtcs.episciences.org/1417
Thu, 24 Mar 2016 17:45:14 +0100<![CDATA[Sticky Seeding in Discrete-Time Reversible-Threshold Networks]]>
https://dmtcs.episciences.org/1405
Thu, 17 Mar 2016 11:49:04 +0100<![CDATA[The Flip Diameter of Rectangulations and Convex Subdivisions]]>
https://dmtcs.episciences.org/1413
Thu, 17 Mar 2016 10:57:41 +0100<![CDATA[Asymptotic Density of Zimin Words]]>
https://dmtcs.episciences.org/1414
Thu, 17 Mar 2016 09:46:11 +0100<![CDATA[Factoriality and the Pin-Reutenauer procedure]]>
https://dmtcs.episciences.org/1412
Tue, 15 Mar 2016 14:04:03 +0100<![CDATA[Arithmetic completely regular codes]]>
https://dmtcs.episciences.org/2150
Sat, 27 Feb 2016 00:00:00 +0100<![CDATA[Dendriform structures for restriction-deletion and restriction-contraction matroid Hopf algebras]]>
https://dmtcs.episciences.org/2157
Fri, 26 Feb 2016 00:00:00 +0100<![CDATA[Edge-partitioning graphs into regular and locally irregular components]]>
https://dmtcs.episciences.org/2154
Wed, 17 Feb 2016 00:00:00 +0100<![CDATA[The complexity of deciding whether a graph admits an orientation with fixed weak diameter]]>
https://dmtcs.episciences.org/2161
Wed, 17 Feb 2016 00:00:00 +0100<![CDATA[$2\times 2$ monotone grid classes are finitely based]]>
https://dmtcs.episciences.org/1378
Thu, 11 Feb 2016 11:31:02 +0100<![CDATA[Avoiding patterns in irreducible permutations]]>
https://dmtcs.episciences.org/2158
i.e., those in which there is no index $i$ such that $\sigma (i+1) - \sigma (i)=1$. The problem is addressed completely in the case of avoiding one or two patterns of length three, and several well known sequences are encountered in the process, such as Catalan, Motzkin, Fibonacci, Tribonacci, Padovan and Binary numbers. Also, we present constructive bijections between the set of Motzkin paths of length $n-1$ and the sets of irreducible permutations of length $n$ (respectively fixed point free irreducible involutions of length $2n$) avoiding a pattern $\alpha$ for $\alpha \in \{132,213,321\}$. This induces two new bijections between the set of Dyck paths and some restricted sets of permutations.]]>i.e., those in which there is no index $i$ such that $\sigma (i+1) - \sigma (i)=1$. The problem is addressed completely in the case of avoiding one or two patterns of length three, and several well known sequences are encountered in the process, such as Catalan, Motzkin, Fibonacci, Tribonacci, Padovan and Binary numbers. Also, we present constructive bijections between the set of Motzkin paths of length $n-1$ and the sets of irreducible permutations of length $n$ (respectively fixed point free irreducible involutions of length $2n$) avoiding a pattern $\alpha$ for $\alpha \in \{132,213,321\}$. This induces two new bijections between the set of Dyck paths and some restricted sets of permutations.]]>Mon, 18 Jan 2016 00:00:00 +0100<![CDATA[Vertex-Coloring Edge-Weighting of Bipartite Graphs with Two Edge Weights]]>
https://dmtcs.episciences.org/2162
Tue, 05 Jan 2016 00:00:00 +0100<![CDATA[The double competition multigraph of a digraph]]>
https://dmtcs.episciences.org/2133
Thu, 31 Dec 2015 00:00:00 +0100<![CDATA[A relation on 132-avoiding permutation patterns]]>
https://dmtcs.episciences.org/2141
avoiding if it does not contain the permutation $τ$. For any $n$, the popularity of a permutation $τ$, denoted $A$_{$n$}($τ$), is the number of copies of $τ$ contained in the set of all 132-avoiding permutations of length $n$. Rudolph conjectures that for permutations $τ$ and $μ$ of the same length, $A$_{$n$}($τ$) ≤ $A$_{$n$}($μ$) for all $n$ if and only if the spine structure of $τ$ is less than or equal to the spine structure of $μ$ in refinement order. We prove one direction of this conjecture, by showing that if the spine structure of $τ$ is less than or equal to the spine structure of $μ$, then $A$_{$n$}($τ$) ≤ $A$_{$n$}($μ$) for all $n$. We disprove the opposite direction by giving a counterexample, and hence disprove the conjecture.]]>avoiding if it does not contain the permutation $τ$. For any $n$, the popularity of a permutation $τ$, denoted $A$_{$n$}($τ$), is the number of copies of $τ$ contained in the set of all 132-avoiding permutations of length $n$. Rudolph conjectures that for permutations $τ$ and $μ$ of the same length, $A$_{$n$}($τ$) ≤ $A$_{$n$}($μ$) for all $n$ if and only if the spine structure of $τ$ is less than or equal to the spine structure of $μ$ in refinement order. We prove one direction of this conjecture, by showing that if the spine structure of $τ$ is less than or equal to the spine structure of $μ$, then $A$_{$n$}($τ$) ≤ $A$_{$n$}($μ$) for all $n$. We disprove the opposite direction by giving a counterexample, and hence disprove the conjecture.]]>Tue, 15 Dec 2015 00:00:00 +0100<![CDATA[Some undecidable problems about the trace-subshift associated to a Turing machine]]>
https://dmtcs.episciences.org/2137
Wed, 02 Dec 2015 00:00:00 +0100<![CDATA[The game colouring number of powers of forests]]>
https://dmtcs.episciences.org/1339
Tue, 24 Nov 2015 20:53:58 +0100<![CDATA[Spanning connectedness and Hamiltonian thickness of graphs and interval graphs]]>
https://dmtcs.episciences.org/2082
Mon, 23 Nov 2015 00:00:00 +0100<![CDATA[Cubical coloring — fractional covering by cuts and semidefinite programming]]>
https://dmtcs.episciences.org/2134
Wed, 18 Nov 2015 00:00:00 +0100<![CDATA[On the Dynamics of Systems of Urns]]>
https://dmtcs.episciences.org/2143
Fri, 16 Oct 2015 00:00:00 +0200<![CDATA[Symmetries of Monocoronal Tilings]]>
https://dmtcs.episciences.org/2142
Mon, 05 Oct 2015 00:00:00 +0200<![CDATA[Persisting randomness in randomly growing discrete structures: graphs
and search trees]]>
https://dmtcs.episciences.org/1289
Thu, 01 Oct 2015 09:37:31 +0200<![CDATA[Reducing the rank of a matroid]]>
https://dmtcs.episciences.org/2135
rank reduction problem for matroids: Given a matroid $M$ and an integer $k$, find a minimum size subset of elements of $M$ whose removal reduces the rank of $M$ by at least $k$. When $M$ is a graphical matroid this problem is the minimum $k$-cut problem, which admits a 2-approximation algorithm. In this paper we show that the rank reduction problem for transversal matroids is essentially at least as hard to approximate as the densest $k$-subgraph problem. We also prove that, while the problem is easily solvable in polynomial time for partition matroids, it is NP-hard when considering the intersection of two partition matroids. Our proof shows, in particular, that the maximum vertex cover problem is NP-hard on bipartite graphs, which answers an open problem of B. Simeone.]]>rank reduction problem for matroids: Given a matroid $M$ and an integer $k$, find a minimum size subset of elements of $M$ whose removal reduces the rank of $M$ by at least $k$. When $M$ is a graphical matroid this problem is the minimum $k$-cut problem, which admits a 2-approximation algorithm. In this paper we show that the rank reduction problem for transversal matroids is essentially at least as hard to approximate as the densest $k$-subgraph problem. We also prove that, while the problem is easily solvable in polynomial time for partition matroids, it is NP-hard when considering the intersection of two partition matroids. Our proof shows, in particular, that the maximum vertex cover problem is NP-hard on bipartite graphs, which answers an open problem of B. Simeone.]]>Wed, 16 Sep 2015 00:00:00 +0200<![CDATA[Classical Automata on Promise Problems]]>
https://dmtcs.episciences.org/2138
Wed, 16 Sep 2015 00:00:00 +0200<![CDATA[On avoidance of patterns of the form σ-τ by words over a finite alphabet]]>
https://dmtcs.episciences.org/2140
$n$ avoiding any $τ$ of the form 11$a-b$.]]>$n$ avoiding any $τ$ of the form 11$a-b$.]]>Wed, 16 Sep 2015 00:00:00 +0200<![CDATA[Disimplicial arcs, transitive vertices, and disimplicial eliminations]]>
https://dmtcs.episciences.org/2131
diclique of a digraph is a pair $V$ → $W$ of sets of vertices such that $v$ → $w$ is an arc for every $v$ ∈ $V$ and $w$ ∈ $W$. An arc $v$ → $w$ is disimplicial when it belongs to a unique maximal diclique. We show that the problem of finding the disimplicial arcs is equivalent, in terms of time and space complexity, to that of locating the transitive vertices. As a result, an efficient algorithm to find the bisimplicial edges of bipartite graphs is obtained. Then, we develop simple algorithms to build disimplicial elimination schemes, which can be used to generate bisimplicial elimination schemes for bipartite graphs. Finally, we study two classes related to perfect disimplicial elimination digraphs, namely weakly diclique irreducible digraphs and diclique irreducible digraphs. The former class is associated to finite posets, while the latter corresponds to dedekind complete finite posets.]]>diclique of a digraph is a pair $V$ → $W$ of sets of vertices such that $v$ → $w$ is an arc for every $v$ ∈ $V$ and $w$ ∈ $W$. An arc $v$ → $w$ is disimplicial when it belongs to a unique maximal diclique. We show that the problem of finding the disimplicial arcs is equivalent, in terms of time and space complexity, to that of locating the transitive vertices. As a result, an efficient algorithm to find the bisimplicial edges of bipartite graphs is obtained. Then, we develop simple algorithms to build disimplicial elimination schemes, which can be used to generate bisimplicial elimination schemes for bipartite graphs. Finally, we study two classes related to perfect disimplicial elimination digraphs, namely weakly diclique irreducible digraphs and diclique irreducible digraphs. The former class is associated to finite posets, while the latter corresponds to dedekind complete finite posets.]]>Tue, 15 Sep 2015 00:00:00 +0200<![CDATA[Packing Plane Perfect Matchings into a Point Set]]>
https://dmtcs.episciences.org/2132
2$n$⌋$-1$. For some special configurations of point sets, we give the exact answer. We also consider some restricted variants of this problem.]]>2$n$⌋$-1$. For some special configurations of point sets, we give the exact answer. We also consider some restricted variants of this problem.]]>Tue, 15 Sep 2015 00:00:00 +0200<![CDATA[Improving Vertex Cover as a Graph Parameter]]>
https://dmtcs.episciences.org/2136
Mon, 14 Sep 2015 00:00:00 +0200<![CDATA[The complexity of $P$<sub>4</sub>-decomposition of regular graphs and multigraphs]]>
https://dmtcs.episciences.org/2128
Wed, 09 Sep 2015 00:00:00 +0200<![CDATA[On graphs double-critical with respect to the colouring number]]>
https://dmtcs.episciences.org/2129
double-col-critical if the colouring number of $G-V(e)$ is at most the colouring number of $G$ minus 2. A connected graph G is said to be double-col-critical if each edge of $G$ is double-col-critical. We characterise the double-col-critical graphs with colouring number at most 5. In addition, we prove that every 4-col-critical non-complete graph has at most half of its edges being double-col-critical, and that the extremal graphs are precisely the odd wheels on at least six vertices. We observe that for any integer $k$ greater than 4 and any positive number $ε$, there is a $k$-col-critical graph with the ratio of double-col-critical edges between $1- ε$ and 1.]]>double-col-critical if the colouring number of $G-V(e)$ is at most the colouring number of $G$ minus 2. A connected graph G is said to be double-col-critical if each edge of $G$ is double-col-critical. We characterise the double-col-critical graphs with colouring number at most 5. In addition, we prove that every 4-col-critical non-complete graph has at most half of its edges being double-col-critical, and that the extremal graphs are precisely the odd wheels on at least six vertices. We observe that for any integer $k$ greater than 4 and any positive number $ε$, there is a $k$-col-critical graph with the ratio of double-col-critical edges between $1- ε$ and 1.]]>Wed, 09 Sep 2015 00:00:00 +0200<![CDATA[The game chromatic number of trees and forests]]>
https://dmtcs.episciences.org/2130
Mon, 17 Aug 2015 00:00:00 +0200<![CDATA[Minimum Number of Colors: the Turk’s Head Knots Case Study]]>
https://dmtcs.episciences.org/2139
Tue, 14 Jul 2015 00:00:00 +0200<![CDATA[How often should you clean your room?]]>
https://dmtcs.episciences.org/2109
Mon, 29 Jun 2015 00:00:00 +0200<![CDATA[On substitution tilings of the plane with n-fold rotational symmetry]]>
https://dmtcs.episciences.org/2108
Fri, 12 Jun 2015 00:00:00 +0200<![CDATA[Intervals and factors in the Bruhat order]]>
https://dmtcs.episciences.org/2110
Fri, 12 Jun 2015 00:00:00 +0200<![CDATA[Snarks with total chromatic number 5]]>
https://dmtcs.episciences.org/2111
Fri, 29 May 2015 00:00:00 +0200<![CDATA[On the Hausdorff measure of regular ω-languages in Cantor space]]>
https://dmtcs.episciences.org/2112
Thu, 21 May 2015 00:00:00 +0200<![CDATA[Hamiltonian decomposition of prisms over cubic graphs]]>
https://dmtcs.episciences.org/2079
Mon, 11 May 2015 00:00:00 +0200<![CDATA[Maximum difference about the size of optimal identifying codes in graphs differing by one vertex]]>
https://dmtcs.episciences.org/2107
Wed, 06 May 2015 00:00:00 +0200<![CDATA[An efficient certificateless aggregate signature scheme for vehicular ad-hoc networks]]>
https://dmtcs.episciences.org/2106
Mon, 04 May 2015 00:00:00 +0200<![CDATA[A note on a recent attempt to improve the Pin-Frankl bound]]>
https://dmtcs.episciences.org/2101
Mon, 27 Apr 2015 00:00:00 +0200<![CDATA[Output sensitive algorithms for covering many points]]>
https://dmtcs.episciences.org/2102
Mon, 27 Apr 2015 00:00:00 +0200<![CDATA[Parameterized complexity of synchronization and road coloring]]>
https://dmtcs.episciences.org/2103
Wed, 22 Apr 2015 00:00:00 +0200<![CDATA[Graphs with large disjunctive total domination number]]>
https://dmtcs.episciences.org/2104
Wed, 22 Apr 2015 00:00:00 +0200<![CDATA[Extending a perfect matching to a Hamiltonian cycle]]>
https://dmtcs.episciences.org/2105
Sat, 28 Mar 2015 00:00:00 +0100<![CDATA[A conjecture on the number of Hamiltonian cycles on thin grid cylinder graphs]]>
https://dmtcs.episciences.org/2113
Sat, 28 Mar 2015 00:00:00 +0100<![CDATA[Cost-effectiveness of algorithms]]>
https://dmtcs.episciences.org/2114
Sat, 28 Mar 2015 00:00:00 +0100<![CDATA[On probe 2-clique graphs and probe diamond-free graphs]]>
https://dmtcs.episciences.org/2122
Sat, 28 Mar 2015 00:00:00 +0100<![CDATA[p-box: a new graph model]]>
https://dmtcs.episciences.org/2121
Fri, 27 Mar 2015 00:00:00 +0100<![CDATA[Guarded subgraphs and the domination game]]>
https://dmtcs.episciences.org/2123
Fri, 27 Mar 2015 00:00:00 +0100<![CDATA[Avoider-enforcer star games]]>
https://dmtcs.episciences.org/2124
Thu, 26 Mar 2015 00:00:00 +0100<![CDATA[Bootstrapping and double-exponential limit laws]]>
https://dmtcs.episciences.org/2125
Wed, 18 Mar 2015 00:00:00 +0100<![CDATA[Edge stability in secure graph domination]]>
https://dmtcs.episciences.org/2120
Mon, 16 Mar 2015 00:00:00 +0100<![CDATA[Connectivity of Fibonacci cubes, Lucas cubes and generalized cubes]]>
https://dmtcs.episciences.org/2115
Thu, 12 Feb 2015 00:00:00 +0100<![CDATA[Classification of skew translation generalized quadrangles, I]]>
https://dmtcs.episciences.org/2116
Thu, 12 Feb 2015 00:00:00 +0100<![CDATA[Symmetric bipartite graphs and graphs with loops]]>
https://dmtcs.episciences.org/2119
Thu, 12 Feb 2015 00:00:00 +0100<![CDATA[On the 1-2-3-conjecture]]>
https://dmtcs.episciences.org/2117
Tue, 10 Feb 2015 00:00:00 +0100<![CDATA[An approximability-related parameter on graphs―-properties and applications]]>
https://dmtcs.episciences.org/2118
Thu, 05 Feb 2015 00:00:00 +0100<![CDATA[Ore-degree threshold for the square of a Hamiltonian cycle]]>
https://dmtcs.episciences.org/2127
Mon, 02 Feb 2015 00:00:00 +0100<![CDATA[A randomized algorithm for finding a maximum clique in the visibility graph of a simple polygon]]>
https://dmtcs.episciences.org/2126
Wed, 21 Jan 2015 00:00:00 +0100<![CDATA[Generalized Polarization Modules (extended abstract)]]>
https://dmtcs.episciences.org/2456
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Depth in Coxeter groups of type $B$]]>
https://dmtcs.episciences.org/2457
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Tableaux combinatorics for two-species PASEP probabilities]]>
https://dmtcs.episciences.org/2458
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Weighted Tree-Numbers of Matroid Complexes]]>
https://dmtcs.episciences.org/2459
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Lattice structure of Grassmann-Tamari orders]]>
https://dmtcs.episciences.org/2460
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Scaling Limits of Random Graphs from Subcritical Classes: Extended abstract]]>
https://dmtcs.episciences.org/2461
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Cohomology classes of rank varieties and a counterexample to a conjecture of Liu]]>
https://dmtcs.episciences.org/2462
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Walks in the Quarter Plane with Multiple Steps]]>
https://dmtcs.episciences.org/2463
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Invariance properties for coefficients of symmetric functions]]>
https://dmtcs.episciences.org/2464
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[The number of directed $k$-convex polyominoes]]>
https://dmtcs.episciences.org/2465
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[On non-conjugate Coxeter elements in well-generated reflection groups]]>
https://dmtcs.episciences.org/2466
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Some combinatorial identities involving noncommuting variables]]>
https://dmtcs.episciences.org/2467
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[A Categorification of One-Variable Polynomials]]>
https://dmtcs.episciences.org/2468
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Arrangements Of Minors In The Positive Grassmannian And a Triangulation of The Hypersimplex]]>
https://dmtcs.episciences.org/2469
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Affine charge and the $k$-bounded Pieri rule]]>
https://dmtcs.episciences.org/2470
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Enumeration of minimal acyclic automata via generalized parking functions]]>
https://dmtcs.episciences.org/2471
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[The Bruhat order on conjugation-invariant sets of involutions in the symmetric group]]>
https://dmtcs.episciences.org/2472
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Enumerating some symmetry classes of rhombus tilings of holey hexagons]]>
https://dmtcs.episciences.org/2473
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Lozenge tilings with free boundary]]>
https://dmtcs.episciences.org/2474
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[The polytope of Tesler matrices]]>
https://dmtcs.episciences.org/2475
0$ is given by the Mahonian numbers and calculate the volume of $Tes_n(1,1,...,1)$ to be a product of consecutive Catalan numbers multiplied by the number of standard Young tableaux of staircase shape.]]>0$ is given by the Mahonian numbers and calculate the volume of $Tes_n(1,1,...,1)$ to be a product of consecutive Catalan numbers multiplied by the number of standard Young tableaux of staircase shape.]]>Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[The frequency of pattern occurrence in random walks]]>
https://dmtcs.episciences.org/2476
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Maximal increasing sequences in fillings of almost-moon polyominoes]]>
https://dmtcs.episciences.org/2477
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Factoring peak polynomials]]>
https://dmtcs.episciences.org/2478
\pi_{i+1}$. Let $P(\pi)$ denote the set of peaks of $\pi$. Given any set $S$ of positive integers, define ${P_S(n)=\{\pi\in S_n:P(\pi)=S\}}$. Billey-Burdzy-Sagan showed that for all fixed subsets of positive integers $S$ and sufficiently large $n$, $|P_S(n)|=p_S(n)2^{n-|S|-1}$ for some polynomial $p_S(x)$ depending on $S$. They conjectured that the coefficients of $p_S(x)$ expanded in a binomial coefficient basis centered at $max(S)$ are all positive. We show that this is a consequence of a stronger conjecture that bounds the modulus of the roots of $p_S(x)$. Furthermore, we give an efficient explicit formula for peak polynomials in the binomial basis centered at $0$, which we use to identify many integer roots of peak polynomials along with certain inequalities and identities.]]> \pi_{i+1}$. Let $P(\pi)$ denote the set of peaks of $\pi$. Given any set $S$ of positive integers, define ${P_S(n)=\{\pi\in S_n:P(\pi)=S\}}$. Billey-Burdzy-Sagan showed that for all fixed subsets of positive integers $S$ and sufficiently large $n$, $|P_S(n)|=p_S(n)2^{n-|S|-1}$ for some polynomial $p_S(x)$ depending on $S$. They conjectured that the coefficients of $p_S(x)$ expanded in a binomial coefficient basis centered at $max(S)$ are all positive. We show that this is a consequence of a stronger conjecture that bounds the modulus of the roots of $p_S(x)$. Furthermore, we give an efficient explicit formula for peak polynomials in the binomial basis centered at $0$, which we use to identify many integer roots of peak polynomials along with certain inequalities and identities.]]>Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Generalised cluster algebras and $q$-characters at roots of unity]]>
https://dmtcs.episciences.org/2479
generalised cluster algebra; we focus on an example in type $C_n$. On the other hand, Chari and Pressley (1997), as well as Frenkel and Mukhin (2002), have studied the restricted integral form $U^{\mathtt{res}}_ε (\widehat{\mathfrak{g}})$ of a quantum affine algebra $U_q(\widehat{\mathfrak{g}})$ where $q=ε$ is a root of unity. Our main result states that the Grothendieck ring of a tensor subcategory $C_{ε^\mathbb{z}}$ of representations of $U^{\mathtt{res}}_ε (L\mathfrak{sl}_2)$ is a generalised cluster algebra of type $C_{l−1}$, where $l$ is the order of $ε^2$. We also state a conjecture for $U^{\mathtt{res}}_ε (L\mathfrak{sl}_3)$, and sketch a proof for $l=2$. ]]>generalised cluster algebra; we focus on an example in type $C_n$. On the other hand, Chari and Pressley (1997), as well as Frenkel and Mukhin (2002), have studied the restricted integral form $U^{\mathtt{res}}_ε (\widehat{\mathfrak{g}})$ of a quantum affine algebra $U_q(\widehat{\mathfrak{g}})$ where $q=ε$ is a root of unity. Our main result states that the Grothendieck ring of a tensor subcategory $C_{ε^\mathbb{z}}$ of representations of $U^{\mathtt{res}}_ε (L\mathfrak{sl}_2)$ is a generalised cluster algebra of type $C_{l−1}$, where $l$ is the order of $ε^2$. We also state a conjecture for $U^{\mathtt{res}}_ε (L\mathfrak{sl}_3)$, and sketch a proof for $l=2$. ]]>Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[On bijections between monotone rooted trees and the comb basis]]>
https://dmtcs.episciences.org/2480
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Subwords and Plane Partitions]]>
https://dmtcs.episciences.org/2481
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Genomic Tableaux and Combinatorial $K$-Theory]]>
https://dmtcs.episciences.org/2482
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Kraśkiewicz-Pragacz modules and some positivity properties of Schubert polynomials]]>
https://dmtcs.episciences.org/2483
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Alignments, crossings, cycles, inversions, and weak Bruhat order in permutation tableaux of type $B$]]>
https://dmtcs.episciences.org/2484
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[The freeness of Ish arrangements]]>
https://dmtcs.episciences.org/2485
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Upper bounds on the growth rates of hard squares and related models via corner transfer matrices]]>
https://dmtcs.episciences.org/2486
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Triangular fully packed loop configurations of excess 2]]>
https://dmtcs.episciences.org/2487
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Mixed volumes of hypersimplices]]>
https://dmtcs.episciences.org/2488
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Generalized Tesler matrices, virtual Hilbert series, and Macdonald polynomial operators]]>
https://dmtcs.episciences.org/2489
virtual Hilbert series, a new class of symmetric function specializations which are defined by their values on (modified) Macdonald polynomials. As a result of this interpretation, we obtain a Tesler matrix expression for the Hall inner product $\langle \Delta_f e_n, p_{1^{n}}\rangle$, where $\Delta_f$ is a symmetric function operator from the theory of diagonal harmonics. We use our Tesler matrix expression, along with various facts about Tesler matrices, to provide simple formulas for $\langle \Delta_{e_1} e_n, p_{1^{n}}\rangle$ and $\langle \Delta_{e_k} e_n, p_{1^{n}}\rangle \mid_{t=0}$ involving $q; t$-binomial coefficients and ordered set partitions, respectively.]]>virtual Hilbert series, a new class of symmetric function specializations which are defined by their values on (modified) Macdonald polynomials. As a result of this interpretation, we obtain a Tesler matrix expression for the Hall inner product $\langle \Delta_f e_n, p_{1^{n}}\rangle$, where $\Delta_f$ is a symmetric function operator from the theory of diagonal harmonics. We use our Tesler matrix expression, along with various facts about Tesler matrices, to provide simple formulas for $\langle \Delta_{e_1} e_n, p_{1^{n}}\rangle$ and $\langle \Delta_{e_k} e_n, p_{1^{n}}\rangle \mid_{t=0}$ involving $q; t$-binomial coefficients and ordered set partitions, respectively.]]>Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Bridge Graphs and Deodhar Parametrizations for Positroid Varieties]]>
https://dmtcs.episciences.org/2490
parametrization of a positroid variety $\Pi$ of dimension $d$ is a regular map $(\mathbb{C}^{\times})^{d} \rightarrow \Pi$ which is birational onto a dense subset of $\Pi$. There are several remarkable combinatorial constructions which yield parametrizations of positroid varieties. We investigate the relationship between two families of such parametrizations, and prove they are essentially the same. Our first family is defined in terms of Postnikov’s boundary measurement map, and the domain of each parametrization is the space of edge weights of a planar network. We focus on a special class of planar networks called bridge graphs, which have applications to particle physics. Our second family arises from Marsh and Rietsch’s parametrizations of Deodhar components of the flag variety, which are indexed by certain subexpressions of reduced words. Projecting to the Grassmannian gives a family of parametrizations for each positroid variety. We show that each Deodhar parametrization for a positroid variety corresponds to a bridge graph, while each parametrization from a bridge graph agrees with some projected Deodhar parametrization.]]>parametrization of a positroid variety $\Pi$ of dimension $d$ is a regular map $(\mathbb{C}^{\times})^{d} \rightarrow \Pi$ which is birational onto a dense subset of $\Pi$. There are several remarkable combinatorial constructions which yield parametrizations of positroid varieties. We investigate the relationship between two families of such parametrizations, and prove they are essentially the same. Our first family is defined in terms of Postnikov’s boundary measurement map, and the domain of each parametrization is the space of edge weights of a planar network. We focus on a special class of planar networks called bridge graphs, which have applications to particle physics. Our second family arises from Marsh and Rietsch’s parametrizations of Deodhar components of the flag variety, which are indexed by certain subexpressions of reduced words. Projecting to the Grassmannian gives a family of parametrizations for each positroid variety. We show that each Deodhar parametrization for a positroid variety corresponds to a bridge graph, while each parametrization from a bridge graph agrees with some projected Deodhar parametrization.]]>Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[A uniform realization of the combinatorial $R$-matrix]]>
https://dmtcs.episciences.org/2491
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Four Variations on Graded Posets]]>
https://dmtcs.episciences.org/2492
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[A representation-theoretic proof of the branching rule for Macdonald polynomials]]>
https://dmtcs.episciences.org/2493
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Rigged configurations of type $D_4^{(3)}$ and the filling map]]>
https://dmtcs.episciences.org/2494
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Bijections of dominant regions in the $m$-Shi arrangements of type $A$, $B$ and $C$]]>
https://dmtcs.episciences.org/2495
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Type C parking functions and a zeta map]]>
https://dmtcs.episciences.org/2496
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Pieri rules for Schur functions in superspace]]>
https://dmtcs.episciences.org/2497
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[A Nekrasov-Okounkov type formula for affine $\widetilde{C}$]]>
https://dmtcs.episciences.org/2498
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Formal Group Laws and Chromatic Symmetric Functions of Hypergraphs]]>
https://dmtcs.episciences.org/2499
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[The $(m, n)$-rational $q, t$-Catalan polynomials for $m=3$ and their $q, t$-symmetry]]>
https://dmtcs.episciences.org/2500
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Enumeration and structure of inhomogeneous graphs]]>
https://dmtcs.episciences.org/2501
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[On Schubert calculus in elliptic cohomology]]>
https://dmtcs.episciences.org/2502
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Negative $q$-Stirling numbers]]>
https://dmtcs.episciences.org/2503
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Non-commutative Frobenius characteristic of generalized parking functions : Application to enumeration]]>
https://dmtcs.episciences.org/2504
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Ehrhart Positivity for Generalized Permutohedra]]>
https://dmtcs.episciences.org/2505
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Combinatorial Hopf Algebras of Simplicial Complexes]]>
https://dmtcs.episciences.org/2506
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Bruhat interval polytopes]]>
https://dmtcs.episciences.org/2507
Bruhat interval polytope $Q_{u,v}$ is the convex hull of all permutation vectors $z=(z(1),z(2),...,z(n))$ with $u$ ≤ $z$ ≤ $v$. Note that when $u=e$ and $v=w_0$ are the shortest and longest elements of the symmetric group, $Q_{e,w_0}$ is the classical permutohedron. Bruhat interval polytopes were studied recently in the 2013 paper “The full Kostant-Toda hierarchy on the positive flag variety” by Kodama and the second author, in the context of the Toda lattice and the moment map on the flag variety. In this paper we study combinatorial aspects of Bruhat interval polytopes. For example, we give an inequality description and a dimension formula for Bruhat interval polytopes, and prove that every face of a Bruhat interval polytope is a Bruhat interval polytope. A key tool in the proof of the latter statement is a generalization of the well-known lifting property for Coxeter groups. Motivated by the relationship between the lifting property and $R$-polynomials, we also give a generalization of the standard recurrence for $R$-polynomials.]]>Bruhat interval polytope $Q_{u,v}$ is the convex hull of all permutation vectors $z=(z(1),z(2),...,z(n))$ with $u$ ≤ $z$ ≤ $v$. Note that when $u=e$ and $v=w_0$ are the shortest and longest elements of the symmetric group, $Q_{e,w_0}$ is the classical permutohedron. Bruhat interval polytopes were studied recently in the 2013 paper “The full Kostant-Toda hierarchy on the positive flag variety” by Kodama and the second author, in the context of the Toda lattice and the moment map on the flag variety. In this paper we study combinatorial aspects of Bruhat interval polytopes. For example, we give an inequality description and a dimension formula for Bruhat interval polytopes, and prove that every face of a Bruhat interval polytope is a Bruhat interval polytope. A key tool in the proof of the latter statement is a generalization of the well-known lifting property for Coxeter groups. Motivated by the relationship between the lifting property and $R$-polynomials, we also give a generalization of the standard recurrence for $R$-polynomials.]]>Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Combinatorics of symplectic invariant tensors]]>
https://dmtcs.episciences.org/2508
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Cyclic Sieving and Plethysm Coefficients]]>
https://dmtcs.episciences.org/2509
jeu-de-taquin promotion.This work extends results of Stembridge and Rhoades linking fixed points of the Schützenberger actions to ribbon tableaux enumeration. The conclusion for the case $n=2$ is equivalent to the domino tableaux rule of Carré and Leclerc for discriminating between the symmetric and antisymmetric parts of the square of a Schur function.]]>jeu-de-taquin promotion.This work extends results of Stembridge and Rhoades linking fixed points of the Schützenberger actions to ribbon tableaux enumeration. The conclusion for the case $n=2$ is equivalent to the domino tableaux rule of Carré and Leclerc for discriminating between the symmetric and antisymmetric parts of the square of a Schur function.]]>Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[The Real-rootedness of Eulerian Polynomials via the Hermite–Biehler Theorem]]>
https://dmtcs.episciences.org/2510
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Card-Shuffling via Convolutions of Projections on Combinatorial Hopf Algebras]]>
https://dmtcs.episciences.org/2511
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Fan realizations of type $A$ subword complexes and multi-associahedra of rank 3]]>
https://dmtcs.episciences.org/2512
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[A combinatorial model for exceptional sequences in type A]]>
https://dmtcs.episciences.org/2513
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Combinatorial proofs of freeness of some P-algebras]]>
https://dmtcs.episciences.org/2514
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Dual filtered graphs]]>
https://dmtcs.episciences.org/2515
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Dyck path triangulations and extendability (extended abstract)]]>
https://dmtcs.episciences.org/2516
n$, any triangulations of $\Delta_{m-1}^{(k-1)}\times\Delta_{n-1}$ extends to a unique triangulation of $\Delta_{m-1}\times\Delta_{n-1}$. Moreover, with an explicit construction, we prove that the bound $k>n$ is optimal. We also exhibit interpretations of our results in the language of tropical oriented matroids, which are analogous to classical results in oriented matroid theory.]]>n$, any triangulations of $\Delta_{m-1}^{(k-1)}\times\Delta_{n-1}$ extends to a unique triangulation of $\Delta_{m-1}\times\Delta_{n-1}$. Moreover, with an explicit construction, we prove that the bound $k>n$ is optimal. We also exhibit interpretations of our results in the language of tropical oriented matroids, which are analogous to classical results in oriented matroid theory.]]>Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Pieri rule for the affine flag variety]]>
https://dmtcs.episciences.org/2517
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Sign variation, the Grassmannian, and total positivity]]>
https://dmtcs.episciences.org/2518
totally nonnegative Grassmannian is the set of $k$-dimensional subspaces $V$ of ℝ^{$n$} whose nonzero Plücker coordinates (i.e. $k × k$ minors of a $k × n$ matrix whose rows span $V$) all have the same sign. Total positivity has been much studied in the past two decades from an algebraic, combinatorial, and topological perspective, but first arose in the theory of oscillations in analysis. It was in the latter context that Gantmakher and Krein (1950) and Schoenberg and Whitney (1951) independently showed that a subspace $V$ is totally nonnegative iff every vector in $V$, when viewed as a sequence of $n$ numbers and ignoring any zeros, changes sign fewer than $k$ times. We generalize this result, showing that the vectors in $V$ change sign fewer than $l$ times iff certain sequences of the Plücker coordinates of some generic perturbation of $V$ change sign fewer than $l − k + 1$ times. We give an algorithm which constructs such a generic perturbation. Also, we determine the positroid cell of each totally nonnegative $V$ from sign patterns of vectors in $V$. These results generalize to oriented matroids.]]>totally nonnegative Grassmannian is the set of $k$-dimensional subspaces $V$ of ℝ^{$n$} whose nonzero Plücker coordinates (i.e. $k × k$ minors of a $k × n$ matrix whose rows span $V$) all have the same sign. Total positivity has been much studied in the past two decades from an algebraic, combinatorial, and topological perspective, but first arose in the theory of oscillations in analysis. It was in the latter context that Gantmakher and Krein (1950) and Schoenberg and Whitney (1951) independently showed that a subspace $V$ is totally nonnegative iff every vector in $V$, when viewed as a sequence of $n$ numbers and ignoring any zeros, changes sign fewer than $k$ times. We generalize this result, showing that the vectors in $V$ change sign fewer than $l$ times iff certain sequences of the Plücker coordinates of some generic perturbation of $V$ change sign fewer than $l − k + 1$ times. We give an algorithm which constructs such a generic perturbation. Also, we determine the positroid cell of each totally nonnegative $V$ from sign patterns of vectors in $V$. These results generalize to oriented matroids.]]>Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Coxeter-biCatalan combinatorics]]>
https://dmtcs.episciences.org/2519
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[$Y$ -meshes and generalized pentagram maps]]>
https://dmtcs.episciences.org/2520
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Universal geometric coefficients for the four-punctured sphere (Extended Abstract)]]>
https://dmtcs.episciences.org/2521
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Equivariant Giambelli formula for the symplectic Grassmannians — Pfaffian Sum Formula]]>
https://dmtcs.episciences.org/2522
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[A lattice on decreasing trees : the metasylvester lattice]]>
https://dmtcs.episciences.org/2523
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Atomic Bases and $T$-path Formula for Cluster Algebras of Type $D$]]>
https://dmtcs.episciences.org/2524
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Stability of Kronecker coefficients via discrete tomography (Extended abstract)]]>
https://dmtcs.episciences.org/2525
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Stability properties of Plethysm: new approach with combinatorial proofs (Extended abstract)]]>
https://dmtcs.episciences.org/2526
Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[A categorification of the chromatic symmetric polynomial]]>
https://dmtcs.episciences.org/2527
*($G$) of graded $S_n$-modules, whose graded Frobenius series $Frob_G(q,t)$ reduces to the chromatic symmetric function at $q=t=1$. We also obtain analogues of several familiar properties of the chromatic symmetric polynomials in terms of homology.]]>*($G$) of graded $S_n$-modules, whose graded Frobenius series $Frob_G(q,t)$ reduces to the chromatic symmetric function at $q=t=1$. We also obtain analogues of several familiar properties of the chromatic symmetric polynomials in terms of homology.]]>Thu, 01 Jan 2015 00:00:00 +0100<![CDATA[Statistics on Lattice Walks and q-Lassalle Numbers]]>
https://dmtcs.episciences.org/2528