# Tag Info

Accepted

### Is it decidable to determine if a given shape can tile the plane?

According to the introduction of , The complexity of determining if a single polyomino tiles the plane remains open [2,3], and There is an undecidability proof for sets of 5 polyominoes .  ...
Accepted

First, the name of the conjecture is "Hartmanis-Stearns", not "Hartmanis-Stearn". Second, the Hartmanis-Stearns conjecture concerns those real numbers computable by a multi-tape Turing machine in ...
Accepted

### Is optimally solving the n×n×n Rubik's Cube NP-hard?

One of my papers was just posted to arXiv and addresses this question: optimally solving the Rubik's Cube is NP-complete.

### Math talk: Theorem about git revision control system?

Interestingly, there is a nascent mathematisation of version control systems, although at this point it's only partially applicable to Git. It's called patch theory [1, 2, 3, 4, 5] and arose in the ...
Accepted

### Math talk: Theorem about git revision control system?

A git repository can be thought of as a partially ordered set of revisions (where one revision is earlier than another in the order if it is a direct or indirect successor of the earlier one). The ...
Accepted

### Permutations with forbidden subsequences

It's NP-complete for $k=3$ by a reduction from betweenness. In the betweenness problem, one is given $n$ items to be totally ordered, and constraints on some triples of items forcing one item of the ...

### Is it decidable to determine if a given shape can tile the plane?

An extended comment: a recent paper by Demaine & al. proves that one tile is enough to simulate an arbitrary computation: Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Matthew J. Patitz, ...
Accepted

### Finding subgraphs with high treewidth and constant degree

See the paper by Julia Chuzhoy and myself on Treewidth sparsifiers. We show that one can obtain a subgraph of degree at most 3 with treewidth $\Omega(k/polylog(k))$ where $k$ is the treewidth of $G$. ...
Accepted

### Pathwidth of planarized drawing of $K_{3,n}$

A naive drawing of $K_{3,n}$ will have pathwidth $O(n)$. I think that's tight, and that the pathwidth is always $\Omega(n)$. Here's an argument why. (1) Fix a drawing of $K_{3,n}$. Without loss of ...
Accepted

### Does the first order theory of a finite structure have bounded quantifier rank?

The theory of any finite structure is model complete. In fact, it is easy to see that any formula is equivalent to an existential formula with one quantifier per each element of the structure, after ...
Accepted

### Number of permutations that satisfy a given set of comparisons

As far as I can tell, your problem is equivalent to the following: given a partial order (represented by its comparability pairs, which forms a DAG), count how many linear extensions it has. This ...

### Combinatorics of a badminton tournament

I finally found the keyword allowing to search for solutions, it's called a "Whist Tournament". Solutions can be found here for instance: https://www.devenezia.com/downloads/round-robin/...
Accepted

### Random walk and mean hitting time in a simple undirected graph

I have decided to ask David Wilson himself, soon thereafter got a reply: For undirected graphs on $n$ vertices, the worst case mean hitting time is $\Theta(n^3)$. The example is the barbell graph, ...
Accepted

### The maximum number of induced cycles in a simple directed graph

I don't know what's already known but the obvious bounds are that it is at most $\binom{n}{n/2}$ (Sperner's theorem) and at least $3^{n/3}$ (for $n$ a multiple of three that is at least 9: form a ...
Accepted

### The asymptotic behavior of a recurrence related to stable matchings

Here is a proof. Parts of the proof involve some real analysis; I've sketched the details in an appendix, and if you know real analysis, you should be able to fill in the details fairly easily. First,...

### Counting words accepted by a regular grammar

I think this is a hard counting problem, see this paper: Counting the size of regular sequences of given length is #P-complete: S. Kannan, Z. Sweedyk, and S. R. Mahaney. Counting and random generation ...

### What is the maximum number of stable marriages for an instance of the Stable Marriage Problem?

An exponential upper bound has been given in Anna R. Karlin, Shayan Oveis Gharan, Robbie Weber: A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings. Later the base of the ...
Accepted

### Number of Automorphisms of a graph for graph isomorphism

Wormald has shown that if $G$ is a connected $3$-regular graph with 2n vertices then the number of automorphisms of $G$ divides $3n\cdot 2^n$. In particular this gives a non-trivial exponential upper-...
Accepted

### VC dimension of polynomials over tropical semirings?

I've realized that the answer to my question is - yes: the VC dimension of degree $\leq d$ polynomials on $n$ variables over any tropical semiring is at most a constant times $n^2\log(n+d)$. This can ...

### How many distinct colors are needed to lower-bound the choosability of a graph?

As a bit of unashamed self-promotion, Marthe Bonamy and I found more negative answers. In particular, Theorem 4 of http://arxiv.org/abs/1507.03495 improves upon the aforementioned result of Král' and ...

### Constant in Komlos conjecture

A simple way of obtaining a lower bound $c\ge\sqrt{2}$ is to consider pairs of vectors $u,v\in\mathbb{R}$. First of all, it makes sense to focus on pairs of unit vectors for which all $\{-1,1\}$-...

### Can the "mutual independence" condition in the Lovász local lemma be weakened?

The Lopsided Lovasz Local Lemma relaxes the mutual independence condition to negative dependence. We assume we have events $A_1, \ldots, A_n$, with a lopsidependency graph $G$ defined on $[n]$ s.t. ...

### Average-case analogue of Small-bias Spaces

Below I show how to explicity construct an average-case $\varepsilon$-biased space on $n$ bits of size $O(1/\varepsilon)$. In contrast, the best worst-case $\varepsilon$-biased spaces on $n$ bits ...
Accepted

### Combinatorial discrepancy of the system of all cuts

I doubt you can do better than $O(n^{3/2})$. Here is a lower bound, using old arguments by Spencer and Erdos, that shows that the discrepancy is $\Omega(n^{3/2})$ if you expand the set system to cuts ...
Accepted

### Implementation of Wilf-Zeilberger and related methods

It is implemented in Maxima (http://maxima.sourceforge.net/docs/manual/de/maxima_77.html#SEC400), to which Sage has interface. A few dozens of examples (ranging from very easy to very difficult) I ...

### Voronoi Diagram of Lines

In 2010 Hemmer et al. gave an exact algorithm for the Voronoi diagram of lines in $\mathbb{R}^3$. In their introduction, they state that the $\Omega(n^2)$ lower bound and $O(n^{3+\varepsilon})$ upper ...

### Pairwise comparison of bit vectors

This problem is sometimes called Subset Containment and it is computationally equivalent to: given $n$ sets $S_1,\ldots,S_n \subseteq [d]$, are there $i \neq j$ such that $S_i \cap S_j = \varnothing$? ...

### Applications of Christol theorem

There are lots of applications to transcendence in finite characteristic. Christol's theorem makes it possible to give proofs of theorems about transcendence of formal power series using the tools of ...
No. Given any linear ordering of the $n$-bit strings, find a sequence of at most $n+1$ strings going from the first string in the ordering to the last string in the ordering by single-bit changes per ...
Uniformly random $k^2$-vertex graphs have clique size $O(\log k)$, well under $k$, and independent set size also $O(\log k)$, implying that their chromatic number is $\Omega(k^2/\log k)$. As for $k^2$...