Combinatorics (math.CO)

  • PDF
    Bizarrely shaped voting districts are frequently lambasted as likely instances of gerrymandering. In order to systematically identify such instances, researchers have devised several tests for so-called geographic compactness (i.e., shape niceness). We demonstrate that under certain conditions, a party can gerrymander a competitive state into geographically compact districts to win an average of over 70% of the districts. Our results suggest that geometric features alone may fail to adequately combat partisan gerrymandering.
  • PDF
    Kontsevich designed a scheme to generate infinitesimal symmetries $\dot{\mathcal{P}} = \mathcal{Q}(\mathcal{P})$ of Poisson brackets $\mathcal{P}$ on all affine manifolds $M^r$; every such deformation is encoded by oriented graphs on $n+2$ vertices and $2n$ edges. In particular, these symmetries can be obtained by orienting sums of non-oriented graphs $\gamma$ on $n$ vertices and $2n-2$ edges. The bi-vector flow $\dot{\mathcal{P}} = \text{Or}(\gamma)(\mathcal{P})$ preserves the space of Poisson structures if $\gamma$ is a cocycle with respect to the vertex-expanding differential in the graph complex. A class of such cocycles $\boldsymbol{\gamma}_{2\ell+1}$ is known to exist: marked by $\ell \in \mathbb{N}$, each of them contains a $(2\ell+1)$-gon wheel with a nonzero coefficient. At $\ell=1$ the tetrahedron $\boldsymbol{\gamma}_3$ itself is a cocycle; at $\ell=2$ the Kontsevich--Willwacher pentagon-wheel cocycle $\boldsymbol{\gamma}_5$ consists of two graphs. We reconstruct the symmetry $\mathcal{Q}_5(\mathcal{P}) = \text{Or}(\boldsymbol{\gamma}_5)(\mathcal{P})$ and verify that $\mathcal{Q}_5$ is a Poisson cocycle indeed: $[\![\mathcal{P},\mathcal{Q}_5(\mathcal{P})]\!]\doteq 0$ via $[\![\mathcal{P},\mathcal{P}]\!]=0$.
  • PDF
    A platypus graph is a non-hamiltonian graph for which every vertex-deleted subgraph is traceable. They are closely related to families of graphs satisfying interesting conditions regarding longest paths and longest cycles, for instance hypohamiltonian, leaf-stable, and maximally non-hamiltonian graphs. In this paper, we first investigate cubic platypus graphs, covering all orders for which such graphs exist: in the general and polyhedral case as well as for snarks. We then present (not necessarily cubic) platypus graphs of girth up to 16---whereas no hypohamiltonian graphs of girth greater than 7 are known---and study their maximum degree, generalising two theorems of Chartrand, Gould, and Kapoor. Using computational methods, we determine the complete list of all non-isomorphic platypus graphs for various orders and girths. Finally, we address two questions raised by the third author in [J. Graph Theory \textbf86 (2017) 223--243].
  • PDF
    A $k$-positive matrix is a matrix where all minors of order $k$ or less are positive. Computing all such minors to test for $k$-positivity is inefficient, as there are $\binom{2n}{n}-1$ of them in an $n\times n$ matrix. However, there are minimal $k$-positivity tests which only require testing $n^2$ minors. These minimal tests can be related by series of exchanges, and form a family of sub-cluster algebras of the cluster algebra of total positivity tests. We give a description of the sub-cluster algebras that give $k$-positivity tests, ways to move between them, and an alternative combinatorial description of many of the tests.
  • PDF
    We introduce a generalization of semistandard composition tableaux called permuted composition tableaux. These tableaux are intimately related to permuted basement semistandard augmented fillings studied by Haglund, Mason and Remmel. Our primary motivation for studying permuted composition tableaux is to enumerate all possible ordered pairs of permutations $(\sigma_1,\sigma_2)$ that can be obtained by standardizing the entries in two adjacent columns of an arbitrary composition tableau. We refer to such pairs as compatible pairs. To study compatible pairs in depth, we define a $0$-Hecke action on permuted composition tableaux. This action naturally defines an equivalence relation on these tableaux. Certain distinguished representatives of the resulting equivalence classes in the special case of two-columned tableaux are in bijection with compatible pairs. We provide a bijection between two-columned tableaux and labeled binary trees. This bijection maps a quadruple of descent statistics for 2-columned tableaux to left and right ascent-descent statistics on labeled binary trees introduced by Gessel, and we use it to prove that the number of compatible pairs is $(n+1)^{n-1}$.
  • PDF
    A linear forest is a forest in which every connected component is a path. The linear arboricity of a graph $G$ is the minimum number of linear forests of $G$ covering all edges. In 1980, Akiyama, Exoo and Harary proposed a conjecture, known as the Linear Arboricity Conjecture (LAC), stating that every $d$-regular graph $G$ has linear arboricity $\lceil \frac{d+1}{2} \rceil$. In 1988, Alon proved that the LAC holds asymptotically. In 1999, the list version of the LAC was raised by An and Wu, which is called the List Linear Arboricity Conjecture. In this article, we prove that the List Linear Arboricity Conjecture holds asymptotically.

Recent comments

Danial Dervovic Dec 10 2017 15:25 UTC

Thank you for the insightful observations, Simon.

In response to the first point, there is a very short comment in the Discussion section to this effect. I felt an explicit dependence on $T$ as opposed to the diameter would make the implications of the result more clear. Namely, lifting can mix

Simon Apers Dec 09 2017 07:54 UTC

Thanks for the comment, Simone. A couple of observations:

- We noticed that Danial's result can in fact be proved more directly using the theorem that is used from ([arXiv:1705.08253][1]): by choosing the quantum walk Cesaro average as the goal distribution, it can be attained with a lifted Markov

Simone Severini Dec 07 2017 02:51 UTC

Closely related to

Simon Apers, Alain Sarlette, Francesco Ticozzi, Simulation of Quantum Walks and Fast Mixing with Classical Processes,

In my opinion, lifting is a good opportunity to put on a rigorous footing the relationship between classical and quantu

Māris Ozols Jul 26 2017 11:07 UTC

Conway's list still has four other $1000 problems left:

Mario Jun 08 2016 06:58 UTC

Too bad, the paper has been withdrawn due to a mistake :-/

Joshua Lockhart May 12 2016 12:14 UTC

Some of the figures in your bound entanglement paper look spookily like some of our graphs! Thanks for highlighting these connections Māris, I appreciate it.

Māris Ozols May 12 2016 07:07 UTC

You introduce some very interesting concepts in this paper! I just wanted to point out some connections that might be interesting to explore.

**Hamiltonian complexity**

The density matrix in your eq. (2) looks exactly like 2-local Hamiltonian that encodes classical computation in its ground state

Tom Wong Nov 09 2015 11:12 UTC

This resolves an open problem of whether the procedure of Emms et al (2006), which is based on quantum walks, can distinguish all non-isomorphic strongly regular graphs. Their conclusion: no, because they came up with an example where the procedure fails.

Zoltán Zimborás Sep 18 2015 04:26 UTC

I can only quote Derrick Stolee: 'Terry Tao just dropped a bomb'. :)

Omar Shehab Jul 01 2014 20:55 UTC

In the last paragraph of the first column of page 3 says,

> This space contains $2^{NU}$ strings, and we have just send that $N!$
> of these strings $p_\pi$ encode permutations $\pi$.

I have following confusions.

- First of all, $\pi$ is a single definite permutation. So the sentence says