We generalise some well-known graph parameters to operator systems by considering their underlying quantum channels. In particular, we introduce the quantum complexity as the dimension of the smallest co-domain Hilbert space a quantum channel requires to realise a given operator system as its non-commutative confusability graph. We describe quantum complexity as a generalised minimum semidefinite rank and, in the case of a graph operator system, as a quantum intersection number. The quantum complexity and a closely related quantum version of orthogonal rank turn out to be upper bounds for the Shannon zero-error capacity of a quantum channel, and we construct examples for which these bounds beat the best previously known general upper bound for the capacity of quantum channels, given by the quantum Lovász theta number.

Oct 19 2017

math.CO arXiv:1710.06470v1

Let $D$ be a knot diagram, and let ${\mathcal D}$ denote the set of diagrams that can be obtained from $D$ by crossing exchanges. If $D$ has $n$ crossings, then ${\mathcal D}$ consists of $2^n$ diagrams. A folklore argument shows that at least one of these $2^n$ diagrams is unknot, from which it follows that every diagram has finite unknotting number. It is easy to see that this argument can be used to show that actually ${\mathcal D}$ has more than one unknot diagram, but it cannot yield more than $4n$ unknot diagrams. We improve this linear bound to a superpolynomial bound, by showing that at least $2^{\sqrt[3]{n}}$ of the diagrams in ${\mathcal D}$ are unknot. We also show that either all the diagrams in ${\mathcal D}$ are unknot, or there is a diagram in ${\mathcal D}$ that is a diagram of the trefoil knot.

Oct 19 2017

math.CO arXiv:1710.06680v1

A vertex u of a graph t-dominates a vertex v if there are at most t vertices different from u,v that are adjacent to v and not to u; and a graph is t-dominating if for every pair of distinct vertices, one of them t-dominates the other. Our main result says that if a graph is t-dominating, then it is close (in an appropriate sense) to being 0-dominating. We also show that an analogous statement for digraphs is false; and discuss some connections with the Erdos-Hajnal conjecture.

Oct 19 2017

math.CO arXiv:1710.06797v1

We find the number of compositions over finite abelian groups under two types of restrictions: (i) each part belongs to a given subset and (ii) small runs of consecutive parts must have given properties. Waring's problem over finite fields can be converted to type~(i) compositions, whereas Carlitz and locally Mullen compositions can be formulated as type~(ii) compositions. We use the multisection formula to translate the problem from integers to group elements, the transfer matrix method to do exact counting, and finally the Perron-Frobenius theorem to derive asymptotics. We also exhibit bijections involving certain restricted classes of compositions.

Oct 19 2017

math.CO arXiv:1710.06757v1

We derive a simple bijection between geometric plane perfect matchings on $2n$ points in convex position and triangulations on $n+2$ points in convex position. We then extend this bijection to monochromatic plane perfect matchings on periodically $k$-colored vertices and $(k+2)$-gonal tilings of convex point sets. These structures are related to a generalisation of Temperley-Lieb algebras and our bijections provide explicit one-to-one relations between matchings and tilings. Moreover, for a given element of one class, the corresponding element of the other class can be computed in linear time.

Oct 19 2017

math.CO arXiv:1710.06719v1

Given a graph $G$, the unraveled ball of radius $r$ around a vertex $v$ is the ball of radius $r$ around $v$ in the universal cover of $G$. We prove a lower bound on the maximum spectral radius of unraveled balls of a fixed radius, and we explore some of its applications to the problems in the neighborhood of the Alon--Boppana bound. In particular, we show that if the average degree of $G$ after deleting any ball of radius $r$ is at least $d$ then its second largest eigenvalue is at least $2\sqrt{d-1}\cos(\frac{\pi}{r+1})$.

We show that for a parabolic quasi-Coxeter element in an affine Coxeter group the Hurwitz action on its set of reduced factorizations into a product of reflections is transitive. We call an element of the Coxeter group parabolic quasi-Coxeter element if it has a reduced factorization into a product of reflections that generate a parabolic subgroup.

Oct 19 2017

math.CO arXiv:1710.06664v1

The notion of descent set, for permutations as well as for standard Young tableaux (SYT), is classical. Cellini introduced a natural notion of \em cyclic descent set for permutations, and Rhoades introduced such a notion for SYT --- but only for rectangular shapes. In this work we define \em cyclic extensions of descent sets in a general context, and prove existence and essential uniqueness for SYT of almost all shapes. The proof applies nonnegativity properties of Postnikov's toric Schur polynomials, providing a new interpretation of certain Gromov-Witten invariants.

Oct 19 2017

math.CO arXiv:1710.06644v1

A graph $G$ is called a $(3,j;n)$-minimal Ramsey graph if it has the least amount of edges, $e(3,j;n)$, given that $G$ is triangle-free, the independence number $\alpha(G) < j$ and that $G$ has $n$ vertices. Triangle-free graphs $G$ with $\alpha(G) < j$ and where $e(G) - e(3,j;n)$ is small are said to be almost minimal Ramsey graphs. We look at a construction of some almost minimal Ramsey graphs, called $H_{13}$-patterned graphs. We make computer calculations of the number of almost minimal Ramsey triangle-free graphs that are $H_{13}$-patterned. The results of these calculations indicate that many of these graphs are in fact $H_{13}$-patterned. In particular, all but one of the connected $(3,j;n)$-minimal Ramsey graphs for $j \leq 9$ are indeed $H_{13}$-patterned.

A simple-triangle graph is the intersection graph of triangles that are defined by a point on a horizontal line and an interval on another horizontal line. The time complexity of the recognition problem for simple-triangle graphs was a longstanding open problem, which was recently settled. This paper provides a new recognition algorithm for simple-triangle graphs to improve the time bound from $O(n^2 \overline{m})$ to $O(nm)$, where $n$, $m$, and $\overline{m}$ are the number of vertices, edges, and non-edges of the graph, respectively. The algorithm uses the vertex ordering characterization in our previous paper that a graph is a simple-triangle graph if and only if there is a linear ordering of the vertices containing both an alternating orientation of the graph and a transitive orientation of the complement of the graph.

Oct 19 2017

math.CO arXiv:1710.06535v1

In 1971, Tomescu conjectured [Le nombre des graphes connexes $k$-chromatiques minimaux aux sommets étiquetés, C. R. Acad. Sci. Paris 273 (1971), 1124--1126] that every connected graph $G$ on $n$ vertices with $\chi(G) = k \geq 4$ has at most $k!(k-1)^{n-k}$ $k$-colourings, where equality holds if and only if the graph is formed from $K_k$ by repeatedly adding leaves. In this note we prove (a strengthening of) the conjecture of Tomescu when $k=5$.

Cyclic sieving is a well-known phenomenon where certain interesting polynomials, especially $q$-analogues, have useful interpretations related to actions and representations of the cyclic group. We define sieving for an arbitrary group $G$ and study it for the dihedral group $I_2(n)$ of order $2n$. This requires understanding the generators of the representation ring of the dihedral group. For $n$ odd, we exhibit several instances of "dihedral sieving" which involve the generalized Fibonomial coefficients, recently studied by Amdeberhan, Chen, Moll, and Sagan.

Oct 19 2017

math.CO arXiv:1710.06490v1

Hultman, Linusson, Shareshian, and Sjöstrand gave a pattern avoidance characterization of the permutations for which the number of chambers of its associated inversion arrangement is the same as the size of its lower interval in Bruhat order. Hultman later gave a characterization, valid for an arbitrary finite reflection group, in terms of distances in the Bruhat graph. On the other hand, the pattern avoidance criterion for permutations had earlier appeared in independent work of Sjöstrand and of Gasharov and Reiner. We give characterizations of the elements of the hyperoctahedral groups satisfying Hultman's criterion that is in the spirit of those of Sjöstrand and of Gasharov and Reiner. We also give a pattern avoidance criterion using the notion of pattern avoidance defined by Billey and Postnikov.

We prove the Relative Hard Lefschetz theorem and the Relative Hodge-Riemann bilinear relations for combinatorial intersection cohomology sheaves on fans.