- arXiv.org
- Applied Physics
- Popular Physics
- History and Philosophy of Physics
- Optics
- Fluid Dynamics
- Physics and Society
- Biological Physics
- Space Physics
- General Physics
- Data Analysis, Statistics and Probability
- Atomic Physics
- Geophysics
- Atomic and Molecular Clusters
- Medical Physics
- Plasma Physics
- Instrumentation and Detectors
- Physics Education
- Atmospheric and Oceanic Physics
- Chemical Physics
- Computational Physics
- Classical Physics
- Accelerator Physics

- Number Theory
- Statistics Theory
- History and Overview
- Information Theory
- Analysis of PDEs
- Algebraic Geometry
- Combinatorics
- Symplectic Geometry
- Mathematical Physics
- Complex Variables
- Probability
- Operator Algebras
- Group Theory
- Representation Theory
- Quantum Algebra
- Numerical Analysis
- Geometric Topology
- Dynamical Systems
- Differential Geometry
- Logic
- Optimization and Control
- General Topology
- General Mathematics
- Metric Geometry
- Algebraic Topology
- Functional Analysis
- Classical Analysis and ODEs
- Spectral Theory
- Category Theory
- Commutative Algebra
- Rings and Algebras
- K-Theory and Homology

- General Literature
- Neural and Evolutionary Computing
- Symbolic Computation
- Information Theory
- Mathematical Software
- Emerging Technologies
- Computer Vision and Pattern Recognition
- Learning
- Operating Systems
- Programming Languages
- Software Engineering
- Multiagent Systems
- Social and Information Networks
- Sound
- Information Retrieval
- Databases
- Formal Languages and Automata Theory
- Distributed, Parallel, and Cluster Computing
- Computer Science and Game Theory
- Artificial Intelligence
- Cryptography and Security
- Computational Complexity
- Discrete Mathematics
- Hardware Architecture
- Numerical Analysis
- Human-Computer Interaction
- Other Computer Science
- Systems and Control
- Digital Libraries
- Robotics
- Networking and Internet Architecture
- Logic in Computer Science
- Computational Geometry
- Data Structures and Algorithms
- Computational Engineering, Finance, and Science
- Graphics
- Performance
- Computation and Language
- Multimedia
- Computers and Society

- 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.
- 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$.
- 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].
- Dec 15 2017 math.CO arXiv:1712.05037v1A $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.
- Dec 15 2017 math.CO arXiv:1712.05008v1We 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}$.
- 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.

For every quantum walk there is a (classical) lifted Markov chain with th...

Danial Dervovic Dec 10 2017 15:25 UTCSimon Apers Dec 09 2017 07:54 UTC

...(continued)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

...(continued)Closely related to

Simon Apers, Alain Sarlette, Francesco Ticozzi, Simulation of Quantum Walks and Fast Mixing with Classical Processes, https://scirate.com/arxiv/1712.01609

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:

https://oeis.org/A248380/a248380.pdf

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

...(continued)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

...(continued)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

- Supported by Silverpond.