**0**

votes

**0**answers

25 views

### “The Two Sheriffs” puzzle -2: threshold for security

I've already asked a question “The Two Sheriffs” puzzle with wrong assumption. Yoav Kallus in his amazing answer using Fano plane showed that the problem has a solution in the case of seven suspects.
...

**1**

vote

**0**answers

46 views

### Matchings in countably infinite geometric lattices of finite height

Let $L$ be a countably infinite geometric lattice of finite height $r\ge3$. (A geometric lattice of height $r$ is an atomistic semimodular lattice such that every maximal chain has $r+1$ elements.)
...

**19**

votes

**1**answer

717 views

### “The Two Sheriffs” puzzle

This puzzle is taken from the book Mathematical puzzles: a connoisseur's collection by P. Winkler.
Two sheriffs in neighboring towns are on the track of a killer, in a
case involving eight ...

**5**

votes

**0**answers

235 views

### Have topographs been studied before?

This is my first post on MO so I hope this question is suitable. I have quite a few definitions which I will need to state before my questions at the end of this post. Please let me know if anything ...

**7**

votes

**2**answers

144 views

### Decomposition of a cross-polytope into simplices

Consider the standard embedded $n$-cross polytope $P_n$ with vertices $\pm e_i \in \mathbb R^n$. Let us consider decompositions of this polytope into $2^{n-1}$ simplices, such that these simplices ...

**7**

votes

**1**answer

105 views

### Is there a Degenerate Dependency Local Lemma?

The Lovasz Local Lemma has several generalizations, with names usually starting with L, such as Lopsided or Lefthanded.
Here I ask whether another possible generalization (for which I could not yet ...

**1**

vote

**1**answer

104 views

### Hamming graph and independent sets

I'm defining the Hamming graph $H(d,q)$ in the usual way, so we have a set $S$ of $q$ elements, the hamming graph $H(d,q)$ has vertex set $S^{d}$ (the set of all ordered $d$-tuples of elements of $S$) ...

**3**

votes

**0**answers

173 views

### adding a boundary to the finite upper half-plane

Let $\Bbb{F}_q$ be a finite field, let $\delta \in \Bbb{F}_q$ be a non-square, let $\Bbb{F}_{q^2} = \Bbb{F}_q\big( \sqrt{\delta} \big)$ be the corresponding quadratic extension,
and let ...

**4**

votes

**2**answers

112 views

### How many simple cycles can a graph with $n$ vertices and $m$ edges have?

I am mainly interested in the smallest number of simple cycles a graph with $n$ vertices and $m$ edges must have.
For example, if $m\le n-1$, this number is $0$, then if $n\le m \le 3(n-1)/2$, it is ...

**24**

votes

**3**answers

460 views

### Ordering subsets of the cyclic group to give distinct partial sums

Suppose that you are given a set $S$ of $k$ nonzero elements from $\mathbb{Z}_n$. Is it always possible to order the elements of $S$, say $a_1,a_2,\dots,a_k$ in such a way that the partial sums ...

**1**

vote

**1**answer

76 views

### Generating function for $t$-residues of partitions using Heisenberg + $\hat{sl_t}$ representation theory

Recall that for $t\geq2$, a partition is a $t$-core if none of its hooklengths is divisible by $t$. It is known that the $t$-cores are parametrized by ${\mathbb Z}^{t-1}$. More precisely, let ...

**4**

votes

**1**answer

179 views

### Young tableau with no i in row i, name that derangement

This question has its genesis in a group assignment: $k$ students are to be given oral exams. Each student will be asked one distinct question from $n$ questions given to them earlier, no two students ...

**6**

votes

**2**answers

85 views

### Reference request: monochromatic paths in edge-colored complete graphs

Given $k,c \in \mathbb{N}$, let $P(k,c)$ be the minimum $n$ such that no matter how we color the edges of the complete graph $K_n$ with $c$ colors, there is always a monochromatic path of length $k$.
...

**3**

votes

**1**answer

66 views

### congruence for Stirling numbers of the first kind

Suppose we write $s(n,k)$ for the Stirling numbers of the first kind. When $p$ is a prime number, I'm interested in knowing when $s(p^a, k)$ is divisible by $p^a$. So:
What is known about ...

**3**

votes

**1**answer

111 views

### Identify ring of polynomials symmetric under forgetting variables

I came across the following ring $A$, which appears as a Chow ring. I am wondering if it has been studied before; in particular, I am looking for a reference where this object might have been ...

**2**

votes

**2**answers

566 views

### inverted factorial and trailing zeros problem

First than anything a big Hello for all math fans like me.
I've found a problem that is pretty interesting and I can't find the answer.
As all of you must know, to counting the trailing zeros of $n$ ...

**2**

votes

**3**answers

372 views

### Characterizing Posets by Functions Into Natural Numbers

Let $P$ be a poset and denote by $Hom(P, \mathbb N)$ the set of all monotone functions from $P$ to natural numbers $\mathbb N$. Under what conditions on $P$ Is it possible to recover the order on $P$ ...

**0**

votes

**0**answers

31 views

### Number of ways you can form pairs with a group of people when certain people cannot be paired with each other [migrated]

Let's say you have a group of eight people and you want to form them into pairs for group projects.
There are
8!/(4!*2!)
ways to do it. (8! Is the total ...

**19**

votes

**0**answers

255 views

### 3-colorings of the unit distance graph of $\Bbb R^3$

Let $\Gamma$ be the unit distance graph of $\Bbb R^3$: points $(x,y)$ form an edge if $|x,y|=1$.
Let $(A,B,C,D)$ be a unit side rhombus in the plane, with a transcendental diagonal, e.g. $A = ...

**2**

votes

**0**answers

45 views

### Bounds on number of distinct substrings

I have a table with $r$ rows of length $\ell$, with each cell containing a letter from an alphabet $A$ of length $a$. I'm trying to determine the expected number of distinct strings of length $k$ ...

**5**

votes

**6**answers

668 views

### Faa di Bruno's formula for inverse functions ?

It is easy to get a expression for the nth-derivative of an inverse fuction ; starting from $(f^{-1})'=\frac{1}{f'\circ f^{-1}}$, one gets things like $(f^{-1})^{(n)}=\frac{\sum a_k\prod ...

**17**

votes

**4**answers

1k views

### What is the minimum N for which there exist N points in the plane that cannot be covered by any number of non-overlapping closed unit discs?

This problem was posed in March 2010 at G4G9 in a talk by the Japanese mathematician Hirokazu "Iwahiro" Iwasawa. He claims there is a simple proof that N > 10, though he did not share it with the ...

**1**

vote

**1**answer

155 views

### Regular unimodular triangulation for a certain simplex

Consider an $n$-simplex with vertices given by
$(0,0,\dots,r_i,r_{i+1},\dots,r_n)$ where $r_1,\dots,r_n$ are given natural numbers,
and $i=0,1,\dots,n+1$.
Does this simplex admit a regular, ...

**3**

votes

**2**answers

128 views

### The Hadwiger number of $L(K_n)$

For $n\in\mathbb{N}$ we consider the set $\{1,\ldots,n\}$ and define the line graph $L(K_n)$ of the complete graph $K_n$ as follows:
$V(L(K_n)) = \big\{\{a,b\}: a,b\in \{1,\ldots, n\}, a\neq b ...

**7**

votes

**0**answers

126 views

### Combinatorics of palindromic decompositions

This is sort of a companion to my question Number of trivializations of a trivial word in the free group (which in turn is motivated by my earlier question here). It turns out that that question may ...

**4**

votes

**1**answer

105 views

### Segments on a family of parallel lines

Let $\{l_i:i\in I\}$ be a family of parallel lines on the plane $\mathbb{R}^2$. Suppose for each $i\in I$ there is a closed segment $s_i\subset l_i$. Moreover, for each triple $i_1,i_2,i_3$ there ...

**0**

votes

**1**answer

125 views

### Number of squares in a grid under certain conditions

Consider an $(n+1)\times (n+1)$ grid of lattice points in the plane.
$A(n):$ # of squares with vertices on the grid.
It's relatively well-known that $A(n)=\frac{n(n+1)^2(n+2)}{12}$. Now, $A(n) = ...

**14**

votes

**10**answers

1k views

### Combinatorial Databases

At one point, I remember being excited by seeing the website Encyclopedia of Combinatorial Structures as an extension of Sloane's Online Integer Sequence Database site. Unfortunately, the site (ECS) ...

**37**

votes

**0**answers

955 views

### Intersecting Family of Triangulations

Let $\cal T_n$ be the family of all triangulations on an $n$-gon using $(n-3)$ non-intersecting diagonals. The number of triangulations in $\cal T_n$ is $C_{n-2}$ the $(n-2)$th Catalan number. Let ...

**3**

votes

**3**answers

327 views

### When few simple conditions yield a unique intricate structure

If people were asked to do a brainstorming related to the title, everyone would probably come up with dozens of examples. Those could include things as different as
the Mandelbrot set, Julia sets ...

**2**

votes

**1**answer

297 views

### Error term in formula for products of necklaces

Let us consider the $\lim_{n\to \infty}\prod_{p=1}^n N(p,a)$, where the number of fixed necklaces of length n composed of a types of beads $N(n,a)$ can be calculated via totient function: ...

**0**

votes

**1**answer

663 views

### A generalized urn-ball matching problem; Complicated combinatoric/probabilistic limit

I'm looking for a generalization to the urn-ball matching problem. As a reminder of what I've got in mind, here's the simple version:
Randomly assign (with replacement) $N$ balls to $M$ urns. ...

**9**

votes

**1**answer

396 views

### Continuous functions and 2-bushy trees

The following problem was asked by Joe Miller in the fall of 2010 at a bar in Madison.
A subtree $T \subseteq 4^{< \omega}$ is $2$-bushy if for some node $\sigma \in T$, every node above $\sigma$ ...

**5**

votes

**1**answer

304 views

### Cospectrality and dimension of graphs

Firstly, I apologize if the question is long. I appreciate any helpful answers and ideas.
In the following all graphs are simple and connected.
Let $G$ be graph with vertex set ...

**5**

votes

**4**answers

295 views

### Is there a non-explicit characterization of the Specht modules?

It is a basic fact about the symmetric group $S_n$ that its irreducible representations are indexed by partitions of $n$.
My question is, can the association between partitions and irreps be ...

**19**

votes

**5**answers

751 views

### Three-halves-free words (analogous to square-free)

A square-free word
is a string of symbols (a "word") that avoids the pattern $XX$, where $X$ is any
consecutive sequence of symbols in the string.
For alphabets of two symbols, the longest square-free ...

**1**

vote

**1**answer

112 views

### Is the number of vertices bounded for fixed max degree and fixed diameter?

Are there positive integers $\Delta, d$ such that the following statement is true?
For every $n\in \mathbb{N}$ there is a graph $G = (V,E)$ such that $|V| = n$,
$\Delta(G) \leq \Delta$ ...

**11**

votes

**0**answers

276 views

### Transitivity of balanced mass transport in Z

Given two atomic measures $\mu$ and $\nu$ on $\mathbb{Z}$, write $\mu \sim \nu$ iff there exist countable decompositions $\mu = \mu_1 + \mu_2 + \cdots$ and $\nu = \nu_1 + \nu_2 + \cdots$ along with ...

**4**

votes

**0**answers

104 views

### Pattern avoidance in Young diagrams

There has been lots of studies on pattern-avoiding permutations. There is also some work done on permutations whose permutation matrix fit in a diagram shape, and then do pattern avoidance on this ...

**0**

votes

**1**answer

58 views

### Edge-disjoint cycles in graphs

Given a graph $G=(V,E)$ and a fixed integer $k$ are there any algorithms known which would find the maximum number of edge-disjoint cycles of length $k$ in $G$? If not is there a proof that this ...

**8**

votes

**1**answer

278 views

### Transitive closure of balanced mass transport in Z (move to close)

Given two atomic measures $\mu$ and $\nu$ on $\mathbb{Z}$, write $\mu \sim \nu$ iff there exist countable decompositions $\mu = \mu_1 + \mu_2 + \cdots$ and $\nu = \nu_1 + \nu_2 + \cdots$ along with ...

**16**

votes

**2**answers

787 views

### Random Walk on $\mathbb{R}$ with Uniformly Distributed Steps and “Reflective” Boundary at Origin

A particle lies on the real number line at the origin. For each step taken, the particle moves from its current position a distance (and direction) chosen equi-probably from range $[-1,r]$. However, ...

**3**

votes

**1**answer

190 views

### Combinatorics problem involving counting the number of certain substrings

I'm not sure if this question is suited for MO, but it does seem quite challenging to me, and is required for a research problem in chemistry I'm working on. I did try getting help from elsewhere ...

**41**

votes

**2**answers

3k views

### Collapsible group words

What is the length $f(n)$ of the shortest nontrivial group word $w_n$ in $x_1,\ldots,x_n$ that collapses to $1$ when we substitute $x_i=1$ for any $i$?
For example, $f(2)=4$, with the commutator ...

**4**

votes

**1**answer

106 views

### Estimating the distribution of minimal hamming distances within a set of strings?

Is their an efficient mathematical way to estimate the distribution of minimal hamming distances for a set of random strings of length 8 over a 4-letter alphabet? E.g. given a set of 100-10,000 ...

**5**

votes

**1**answer

108 views

### Time to generate a filled-in sub-checkered board

Take an $m \times n$ checkered board and one-at-a-time add a piece to an empty square. At what point are you guaranteed to have an $s \times t$ sub-board where all of its squares are filled?
Here I ...

**2**

votes

**1**answer

245 views

### Name search for special Linear Integer Program

I am looking for a name for the following question in literature!
(and if you know it, then it would be great)
I couldn't find it and due to wide audience here, presumably you know more. Thank you
...

**2**

votes

**0**answers

34 views

### Is the size of maximum matching in vertex transitive 3-uniform hyper-graph on $n$ vertices always $\Omega(n)$?

What is the best known lower bound on the size of the maximum matching in a vertex transitive $3$-uniform hyper-graph?

**3**

votes

**0**answers

100 views

### ``Occasional'' Laurent phenomenon

This question is motivated by Richard Stanley's A question on the Laurent phenomenon (motivated by his answer to the question what is the probability that a scissor became the champion?).
He asked ...

**4**

votes

**1**answer

137 views

### Orthogonal basis for the multilinear polynomials with zero “trace”

We say that a multilinear polynomial $P(x_1,\ldots,x_n)$ in $n$ commuting variables over $\mathbb{R}$ has zero trace if
$$ \frac{d}{dt} P(t,\ldots,t) = 0. $$
Equivalently,
$$ \left(\sum_{i=1}^n ...