# Tagged Questions

**3**

votes

**1**answer

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

**19**

votes

**0**answers

230 views

### Which region in the plane with a given area has the most domino tilings?

I just finished teaching a class in combinatorics in which I included a fairly easy upper bound on the number of domino tilings of a region in the plane as a function of its area. So this led to ...

**24**

votes

**2**answers

841 views

### A group-theoretic perspective on Frankl's union closed problem

Here is a group theoretic phrasing of a special case of the union closed conjecture:
Question: Given a finite group $G$, is there an element of prime power order which is contained in at most half ...

**16**

votes

**1**answer

570 views

### A Question on 1, 2 ,3 Conjecture

1, 2, 3 conjecture is well-known:
If $G$ is a simple graph which is not $K_2$ then one can assign a number among $1, 2, 3$ to every edge such that if we label each vertex with the sum of the numbers ...

**9**

votes

**2**answers

378 views

### Is the Steiner ratio Gilbertâ€“Pollak conjecture still open?

Gilbert-Pollak conjecture on the Steiner ratio: Consider a set $P$ of $n$ points on the euclidean plane. A shortest
network interconnecting $P$ must be a tree, which is called a Steiner minimum ...

**11**

votes

**1**answer

487 views

### Tiling the square with rectangles of small diagonals

For a given integer $k\ge3$, tile the unit square with $k$ rectangles so that the longest of the rectangles' diagonals be as short as possible. Call such a tiling optimal. The solutions are obvious in ...

**13**

votes

**1**answer

513 views

### Randomly switching street lights, in a square city

This is a combinatorics-probability question, best stated however in "recreational" terms. Imagine a $N\times N$ city, meaning that we have $N$ horizontal streets, and $N$ vertical streets. At each ...

**9**

votes

**4**answers

1k views

### What are the major open problems in design theory nowaday?

I gather that the question whether the Bruck-Chowla-Ryser condition was sufficient used to top the list, but now that that's settled - what is considered the most interesting open question?

**8**

votes

**1**answer

254 views

### Maximal class of simple graphs of order $n$ with mutually distinct numbers of spanning trees

This problem in some ways related to this post.
Let $A_n$ be the set of all integers $x$ such that there exist a connected simple graph of order $n$ having precisely $x$ spanning trees. Study the ...

**45**

votes

**2**answers

2k views

### vector balancing problem

I believe the solution posted to the arXiv on June 17 by Marcus, Spielman, and Srivastava is correct.
This problem may be hard, so I don't expect an off-the-cuff solution. But can anyone suggest ...

**15**

votes

**2**answers

731 views

### Minimal graphs with a prescribed number of spanning trees

As its long ago since Erdős died and mathoverflow is the second best alternative to him (for discussing personal problems), I'd like to start a fruitful discussion about the following problem ...

**4**

votes

**1**answer

481 views

### What is the degree of a symmetric boolean function?

(previous title " Zero sum of binomials coefficients - a stronger version ")
This is a stronger version of another question.
Is there an $N\in \mathbb N$ and a sequence of non-constant functions $ ...

**10**

votes

**0**answers

480 views

### Once differentiable, piecewise degree three polynomials on triangulated planar domains

Here is an easily described, but very difficult, problem that I
(and a number of other people) really would like to see solved during
our life times. The basic problem is to compute the dimension of ...

**4**

votes

**1**answer

352 views

### A question concerning products of finite cyclic groups

Let $m_1,\ldots, m_n$ be pairwise coprime natural numbers $\geq 1$. We consider the product $$G(m_1,\ldots,m_n) := \prod_{i=1}^{n} \mathbb{Z} / m_i \mathbb{Z}.$$ We define $M(n)$ as the set $n$-tuple ...

**5**

votes

**1**answer

829 views

### A Game of Knights and Queens

Let $m,n,u,v \in \mathbb{N}$ be parameters with $m,n \geq 3$. Suppose two players play a game on a $m \times n$ chess board and we denote the squares of the board by the set of points $ (i,j) $ such ...

**30**

votes

**2**answers

2k views

### Difficult examples for Frankl's union-closed conjecture

Frankl's well-known union-closed conjecture states that if F is a finite family of sets that is closed under taking unions (that is, if A and B belong to the family then so does $A\cup B$), then there ...

**19**

votes

**2**answers

2k views

### Is there a 7-regular graph on 50 vertices with girth 5? What about 57-regular on 3250 vertices?

The following problem is homework of a sort -- but homework I can't do!
The following problem is in Problem 1.F in Van Lint and Wilson:
Let $G$ be a graph where every vertex
has degree $d$. ...

**26**

votes

**0**answers

1k views

### A Combinatorial Abstraction for The “Polynomial Hirsch Conjecture”

Consider $t$ disjoint families of subsets of {1,2,â€¦,n}, ${\cal F}_1,{\cal F_2},\dots {\cal F_t}$ .
Suppose that
(*)
For every $i \lt j \lt k$
and every $R \in {\cal F}_i$, and $T \in {\cal F}_k$, ...

**22**

votes

**2**answers

2k views

### Projective Plane of Order 12

I asked this question on the new Theoretical Computer Science "overflow" site, and commenters suggested I ask it here. That question is here, and it contains additional links, which I doubt I can ...

**47**

votes

**8**answers

6k views

### The “sensitivity” of 2-colorings of the d-dimensional integer lattice

Consider the $d$-dimensional integer lattice, $Z^d$. Call two points in $Z^d$ "neighbors" if their Euclidean distance is 1 (i.e., if they differ by 1 on exactly one coordinate).
Let $C$ be a ...

**36**

votes

**3**answers

5k views

### Do there exist chess positions that require exponentially many moves to reach?

By "chess" here I mean chess played on an $n\times n$ board with an unbounded number of (non-king) pieces. Some care is needed if you want to generalize some of the subtler rules of chess to an ...

**27**

votes

**6**answers

2k views

### Can we color Z^+ with n colors such that a, 2a, …, na all have different colors for all a?

For example for n=2 coloring odd numbers red, numbers of the form 4k+2 blue and so on works.
This problem was posed in the KoMaL for n+1 prime, if I know well by Geza Kos. I verified it for all ...

**17**

votes

**2**answers

696 views

### Ramsey multiplicity

Given a positive integer $a$, the Ramsey number $R(a)$ is the least $n$ such that whenever the edges of the complete graph $K_n$ are colored using only two colors, we necessarily have a copy of $K_a$ ...

**16**

votes

**3**answers

1k views

### Cutting convex sets

Any bounded convex set of the Euclidean plane can be cut into two convex pieces of equal area and circumference.
Can one cut every bounded convex set of the Euclidean plane into an arbitrary number ...

**29**

votes

**4**answers

2k views

### Factorials in Pascals Triangle

Hi,
I asked this question of Keith Conrad, and he suggested that I try posting here. One of my students observed that the only instances of factorials in the interior of Pascal's triangle are ...

**18**

votes

**2**answers

689 views

### Deligne-Simpson problem in the symmetric group

Question.
Let $C_1,\dots,C_k$ be conjugacy classes in the symmetric group $S_n$. (More explicitly,
each $C_i$ is given by a partition of $n$; $C_i$ consists of permutations whose cycles
have the ...

**15**

votes

**0**answers

730 views

### Optimal Monotone Families for the Discrete Isoperimetric Inequality

Background: the Discrete Isoperimetric Inequality
Start with a set X={1,2,...,n} of n elements and the family $2^X$ of all subsets of X.
For a real number p between zero and one, we consider a ...

**6**

votes

**0**answers

267 views

### Enumerating (generalized) de Bruijn tori

Given a cyclic word $w$ of length $N$ over a $q$-ary alphabet and $k \in \mathbb{Z}_+$, consider the directed multigraph $G_k(w) = (V,E)$ with $V \subset$ {$1,\dots,q$}$^k$ given by the $k$-lets ...

**11**

votes

**6**answers

3k views

### Solving NP problems in (usually) Polynomial time?

Just because a problem is NP-complete doesn't mean it can't be usually solved quickly.
The best example of this is probably the traveling salesman problem, for which extraordinarily large instances ...

**12**

votes

**3**answers

975 views

### distance regular metric spaces

A metric space (V,d) will be called distance regular if for every distances a>0, b, c a nonnegative integer p(a,b,c) is defined, so that whenever d(B,C)=a, there are precisely p(a,b,c) points A ...

**32**

votes

**7**answers

2k views

### The shortest path in first passage percolation

Consider a square planar grid. (The vertices are pair of points in the plane with integer coordinates and two vertices are adjacent if they agree in one coordinate and differ by one in the other.)
...

**14**

votes

**5**answers

2k views

### Number of valid topologies on a finite set of n elements

I've heard that the problem of counting topologies is hard, but I couldn't really find anything about it on the rest of the internet. Has this problem been solved? If not, is there some feature that ...

**16**

votes

**4**answers

1k views

### Irreducible polynomials with constrained coefficients

Over at the Cafe, after reading about TWF 285, I asked more-or-less
About how many polynomials with coefficients in $\{\pm 1\}$ and of degree $d$ are irreducible?
and that's what I want to ask ...

**9**

votes

**1**answer

647 views

### Is every matching of the hypercube graph extensible to a Hamiltonian cycle

Given that $Q_d$ is the hypercube graph of dimension $d$ then it is a known fact (not so trivial to prove though) that given a perfect matching $M$ of $Q_d$ ($d\geq 2$) it is possible to find another ...

**13**

votes

**2**answers

1k views

### The Sylvester Gallai Theorem and Sections of Varieties with “Simple Topology”.

The Sylvester-Gallai theorem asserts that for every collection of points in the plane, not all on a line, there is a line containing exactly two of the points.
One high dimensional extension ...

**29**

votes

**1**answer

2k views

### Is the set of primes “translation-finite”?

The definition in the title probably needs explaining. I should say that the question itself was an idea I had for someone else's undergraduate research project, but we decided early on it would be ...