4
votes
1answer
288 views

Application of Combinatorics, Logic and computability theory in physical science: Tiling of Wang Tile with proportionality

The original problem of Domino Tiling and Wang Tile has great theoretical interest on computability theory... However, the great emerging problem on application of Wang Tile in material science and ...
2
votes
1answer
95 views

Conjecture of a subset of Wang tile which might be decidable

From the two papers proving the undecidability of Wang tile in 1966 by Berger and in 1971 by RM Robinson, the tiles used in proving undecidability has a general common feature: The left color and ...
2
votes
1answer
216 views

A variant of Kruskal's theorem

For $X$ and $Y$ finite sequences of finite trees, let us say that $X$ is everywhere contained in $Y$ ($X\subseteq_{ec}Y$) iff, for every $y\in Y$, there is some $x\in X$ such that $x$ is a minor of ...
4
votes
1answer
178 views

Is Van der Waerden's function elementary

Van der Waerden's function was proved to have elementary upper bound on growth rate. Is the Van der Waerden's function itself elementary in the sense of Kalmar?
3
votes
0answers
184 views

Binary search with maximum consecutive lies about “is X in subset S?”

Here's the original problem: Alice tells Bob "I have thought of an integer between 1 and 2000. Tell me 1000 numbers. If your set contains my number, I'll give you this prize." Bob really wants ...
8
votes
4answers
407 views

Order-independent properties arising naturally in mathematics

The motivation for the following question comes from finite model theory, but it is not a technical question about this field, and it is particularly directed at people working in other fields. It ...
9
votes
1answer
410 views

A conjecture on intersection of some intervals.

It was proved here that if $a\in \mathbb{N}_{\geq3}$ then $$\bigcap_{i = 1}^{a} \bigcup_{j = 0}^{i-1} \left[\frac{1+aj}{i},\frac{a(j+1)-1}{i}\right] = \varnothing \tag{1}$$ It may be conjectured ...
8
votes
2answers
673 views

Sperner's lemma and Tucker's lemma

In their article "A Borsuk-Ulam Equivalent that Directly Implies Sperner's Lemma" (American Mathematical Monthly, April 2013), Nyman and Su write "[W]e are unaware of a direct proof that Tucker's ...
23
votes
4answers
1k views

In what rigorous sense are Sperner's Lemma and the Brouwer Fixed Point Theorem equivalent?

I understand that one can give a proof of each of these propositions assuming the truth of the other. But this seems a bit squishy to me, since there is a trivial sense in which any two true theorems ...
2
votes
1answer
118 views

On the Combinatorial Classification of Modal Kripke Frames

We have that S5 modal logic is characterized by the modal axioms $K$, $M$ (reflexive), $4$ (transitive), and $B$ (symmetric). That is, an equivalence relation on a set of possible world (which can be ...
6
votes
1answer
164 views

Models of ZFA corresponding exactly with a particular class of groups

I recently read [1], in which Blass exhibits a correspondence between: Permutation models of ZFA in which the axiom of choice (AC) fails but the Boolean prime ideal theorem (BPIT) holds; and ...
16
votes
1answer
503 views

Polynomial-time algorithm to compare numbers in Conway chained arrow notation

I am looking for a polynomial-time algorithm which, given a character string containing two numbers in Conway's chained arrow notation for large numbers, indicates whether the first number is less ...
9
votes
6answers
1k views

Non-constructive proofs vs. efficient algorithms

My question concerns what is meant by "nonconstructive", and whether it has ever been defined in terms of computational complexity. The wikipedia article on constructive proof begins, "a constructive ...
2
votes
1answer
165 views

A categorical framework for Freiman s-morphisms

Let $\mathfrak A_i$ be groups ($i = 1, 2$), written multiplicatively, and $s$ a non-negative integer (here, as usual, I am abusing notation and denoting the operations of $\mathfrak A_1$ and ...
4
votes
2answers
400 views

$\beta\mathbb{N}$ vs $\beta\mathbb{Z}$

Just started learning the Stone-Cech compactification of discrete groups this week. My motivation comes from a question on $\beta\mathbb{Z}$. Surprisingly, I realized there are muchhhh more literature ...
9
votes
1answer
429 views

Constructing an injective reduction of equivalence relations

[Metastuff: I asked this question in a slightly different way on mathSE last week, and it didn't go anywhere, which is why I am asking here. I added the DST tag because it's basically a problem about ...
15
votes
4answers
752 views

Proving univariate polynomials (defined by sums, binomial coeffs, etc.) are nonnegative: is it 'routine'?

My colleagues and I are working on a project related to an old paper of C. Borell and we have boiled it down to the following problem: Show, for all integers $1 \leq i \leq k$, that the univariate ...
19
votes
5answers
11k views

How large is TREE(3) ?

Friedman, in http://www.math.osu.edu/~friedman.8/pdf/EnormousInt112201.pdf, shows that TREE(3) is much larger than n(4), itself bounded below by $A^{A(187195)}(3)$ (where $A$ is the Ackerman ...
11
votes
2answers
4k views

What is “Seetapun Enigma”?

A friend of mine just asked me this very question. While I had some training in combinatorics, I have never heard of the "Seetapun Enigma", which, supposedly, is related to the Ramsey's theorem. A ...
5
votes
1answer
232 views

Existence of 'uniform transformations' of sequences of rationals (apres Friedman)

Let $\mathbb{Q}^*$ be the set of finite sequences of rationals, and let $x \sim y$ if and only if they have the same length, and for all $1 \le i,j \le length(x)$, $x_i \lt x_j$ iff $y_i \lt y_j$ ...
3
votes
2answers
764 views

Are context-free languages with context-free complements necessarily deterministic context-free?

Let $L \subseteq A^\star$ be a formal language over $A$ generated by a context-free grammar, and $L' = A^\star - L$ be the relative complement in $A^\star$. If $L$ and $L'$ are both context-free, are ...
17
votes
6answers
2k views

undecidable sentences of first-order arithmetic whose truth values are unknown

Godel's undecidable sentences in first-order arithmetic were guaranteed to be true, by construction. But are there examples of specific sentences known to be undecidable in first-order arithmetic ...
3
votes
2answers
474 views

Is there Ramsey Theorem for infinitary tuples?

I'm wondering if there's any sort of Ramsey relation that allows for the tuples to be of arbitrary infinite size $\mu$? This $\mu$ is below some strongly compact cardinal, so I'm not worried about ...
5
votes
1answer
509 views

Characterization of infinite paths in graphs

First an introduction. A directed graph we all know what is, and a graph is serial whenever every vertex has a successor. I do not consider the empty graph. A pair $(\mathcal{G},s)$ is called a ...
1
vote
0answers
175 views

Maximizing the number of 'correct' literals in planar monotone 3SAT

I'm trying to find the complexity of this optimization problem: Given an instance of planar monotone 3SAT, with positive clauses $C_i = v_{i1} V v_{i2} V v_{i3}$ and negative clauses $D_i = ...
3
votes
1answer
739 views

Does BQP^P = BQP ? … and what proof machinery is available?

Update #3: Over on TCS StackExchange, I have rated as "accepted" an ingenious construction by Luca Trevisan, which answers a two-part question (as reframed by Tsuyoshi Ito) that is in essence "Do ...
7
votes
3answers
815 views

Singular Cardinals, and A Strange Question.

Let $\mu$ be any infinite cardinal, and define a collection $N\subset[\mu]^\mu$ to be, maximal almost disjoint (MAD) over $\mu$, iff $\forall\{A,B\}\in[N]^2$ $( A\cap B \in [\mu]^{<\mu})$ ...
9
votes
2answers
2k views

Quantum PCP Theorem

Although I think I know the answers to these, I'd just like to collect them all in one place. What is the quantum PCP theorem, what implications does its proof have for simulation of Hamiltonians and ...
4
votes
1answer
286 views

Subsets of sequences of natural numbers vs. strategies under ZFC

This question is related to a previous question of mine: Determinacy interchanging the roles of both players Given any set A of sequences of natural numbers, every strategy (no matter for which ...
18
votes
2answers
1k views

Is there a name for a family of finite sequences that block all infinite sequences?

Let ${\bf N}^\omega = \bigcup_{m=1}^\infty {\bf N}^m$ denote the space of all finite sequences $(N_1,\ldots,N_m)$ of natural numbers. For want of a better name, let me call a family ${\mathcal T} ...
12
votes
7answers
678 views

Replacing logician-constructive with combinatorist-constructive?

Logicians interpret the word "constructive" in a very well-defined way: they take it to mean, more or less, "computability". Taking constructivity seriously and working in a world where everything ...
27
votes
2answers
609 views

What is the minimal size of a partial order that is universal for all partial orders of size n?

A partial order $\mathbb{B}$ is universal for a class $\cal{P}$ of partial orders if every order in $\cal{P}$ embeds order-preservingly into $\mathbb{B}$. For example, every partial order ...
3
votes
1answer
184 views

characterization of regular languages among (say) those computable in linear time

For a given language A let A(n) denote the number of words in A of length smaller or equal to n. It is know that if A is a regular language then the function $ f(x) = \sum_{i=0}^\infty A(n)x^n$ is in ...
5
votes
4answers
2k views

Examples of inductive proofs that can be generalized by transfinite induction

Hello. I am currently searching for some nice examples of proofs by induction in the finite case, that can be generalized to the infinite case using transfinite induction (and dont become trivial ...
4
votes
3answers
905 views

Pigeonhole Principle for infinite case

Suppose $X_n$ are finite sets for any natural integer $n$. let $Y$ be an infinite subset of $\prod_n X_n$. Do there exist $y$ and $y'$ in $Y$ and an infinite subset $S$ of $\mathbb N$ such that ...
0
votes
1answer
391 views

cardinal equivalence: for each boolean formula, |quantifications| = |assignments|. [closed]

Cardinal Equivalence Theorem For each boolean formula, |quantifications| = |assignments|. The set of valid quantifications has some cardinality, call that ...
32
votes
15answers
6k views

Strong induction without a base case

Strong induction proves a sequence of statements $P(0)$, $P(1)$, $\ldots$ by proving the implication "If $P(m)$ is true for all nonnegative integers $m$ less than $n$, then $P(n)$ is true." for ...
12
votes
6answers
1k views

Can we disallow finite choice?

When people work with infinite sets, there are some who (with good reason) don't like to use the Axiom of Choice. This is defensible, since the axiom is independent of the other axioms of ZF set ...