23
votes
Accepted
Is it decidable to determine if a given shape can tile the plane?
According to the introduction of [1],
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 [4].
[1] ...
- 526
18
votes
Accepted
Is Hartmanis-Stearns conjecture settled by this article?
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 ...
- 6,957
17
votes
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.
- 2,758
17
votes
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 ...
- 11.3k
16
votes
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 ...
- 50.8k
14
votes
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 ...
- 50.8k
14
votes
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, ...
- 22.6k
14
votes
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$. ...
- 6,979
12
votes
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 ...
- 50.8k
12
votes
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 ...
- 16.5k
12
votes
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 ...
- 8,866
12
votes
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/...
- 8,588
11
votes
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, ...
- 311
10
votes
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 ...
- 50.8k
10
votes
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,...
- 24.3k
9
votes
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 ...
- 161
9
votes
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 ...
- 14k
9
votes
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-...
9
votes
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 ...
- 6,655
8
votes
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 ...
- 1,952
8
votes
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\}$-...
- 2,490
8
votes
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. ...
- 18.1k
8
votes
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 ...
- 2,803
7
votes
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 ...
- 18.1k
7
votes
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 ...
7
votes
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 ...
- 4,633
7
votes
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$? ...
- 27.1k
7
votes
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 ...
- 6,957
7
votes
Accepted
Stable order on binary strings
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 ...
- 50.8k
7
votes
Accepted
On the coloring number of small graphs with small cliques
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$...
- 50.8k
Only top scored, non community-wiki answers of a minimum length are eligible