# Tagged Questions

**4**

votes

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**4**answers

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

**1**answer

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

**2**answers

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

**4**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**6**answers

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

**1**answer

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

**2**answers

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

**1**answer

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

**4**answers

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

**5**answers

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

**2**answers

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

**1**answer

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

**2**answers

765 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

**6**answers

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

**2**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**3**answers

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

**2**answers

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

**1**answer

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

**2**answers

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

**7**answers

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

**2**answers

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

**1**answer

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

**4**answers

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

**3**answers

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

**1**answer

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

**15**answers

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

**6**answers

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 ...