3
votes
1answer
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
0answers
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
2answers
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
1answer
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
2answers
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
1answer
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
1answer
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
4answers
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
1answer
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
2answers
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
2answers
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
1answer
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
0answers
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
1answer
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
1answer
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
2answers
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
2answers
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
0answers
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
2answers
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
8answers
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
3answers
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
6answers
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
2answers
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
3answers
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
4answers
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
2answers
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
0answers
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
0answers
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
6answers
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
3answers
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
7answers
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
5answers
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
4answers
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
1answer
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
2answers
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
1answer
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 ...