The discrete-mathematics tag has no wiki summary.

**34**

votes

**6**answers

3k views

### Is it easy to produce hard-to-color graphs?

This question arises from my recent visit to my daughter's second-grade class, where I led some discussion and activities on graph coloring (see Math for seven-year-olds). In one such activity, each ...

**24**

votes

**5**answers

2k views

### How many binary operations are associative?

Let $X$ be a finite set of $n$ elements, and consider a binary operation $\odot: X \times X \rightarrow X$. There are $n^{n^2}$ such binary operations, as the $n \times n$ table entries can each
be ...

**21**

votes

**5**answers

832 views

### Sequences with integral means

Let $S(n)$ be the sequence whose first element is $n$, and from then onward,
the next element is the smallest natural number ${\ge}1$ that ensures that the
mean of all the numbers in the sequence is ...

**19**

votes

**1**answer

269 views

### Hidden points in polygons

Let $h(n)$ be the largest number of mutually invisible points that can be located in a
polygon $P$ of $n$ vertices. Two points $x$ and $y$ are mutually invisible if the segment
$xy$ contains a point ...

**17**

votes

**2**answers

748 views

### Is there a discrete Cerf theory?

Towards the end of the 1990's, Robin Forman developed a discrete version of Morse theory, which concerns maps from a simplicial complex to $\mathbb{R}$ satisfying a combinatorial analogue to the ...

**16**

votes

**1**answer

449 views

### Longest of random worm-like paths in $\mathbb{Z}^2$

Imagine at each lattice point of $\mathbb{Z}^2$ within $[1,3n]^2$,
with coordinates
$\equiv 2 \bmod 3$,
we place, with equal probability, one of these six patterns:
The result ...

**15**

votes

**8**answers

1k views

### Two questions from combinatorics on words

Question 1. Assume that an infinite word $u\in\{0,1\}^{\mathbb Z}$ is not balanced. Is it true that there exists a finite 0-1 word $w$ such that $0w01w1$ or $1w10w0$ is a factor of $u$? Is it true ...

**14**

votes

**1**answer

648 views

### Is every graph the center of some other graph?

The center of a graph $G$ is the set of vertices that minimize the largest
distance to vertices in $G$, e.g., in the graph below, that radius is $4$:
Define the ...

**14**

votes

**3**answers

791 views

### Partitioning the integers $1$ through $n$ so that the product of the elements in one set is equal to the sum of the elements in the other

I asked this question at math.SE a couple of months ago and only got a partial answer, so I thought I would try here.
It is known that, for $n \geq 5$, it is possible to partition the integers ...

**13**

votes

**4**answers

2k views

### Has any attempt been made to classify finite groupoids?

I recently stumbled upon the Mathieu groupoid and I found them fascinating.
It appears as a subset of $S_{13}$ which is not closed under multiplication, but it turns out to be a groupoid with 13 ...

**13**

votes

**1**answer

453 views

### Does erosion mix faster than a riffle shuffle?

It is a famous result of Aldous and Diaconis1 that
seven shuffles are necessary and suffice to approximately
randomize 52 cards.2
Here the shuffles are the standard riffle shuffle, where the ...

**13**

votes

**1**answer

259 views

### Is there an unambiguous CFL whose complement is not context-free?

I'm doing a little bit of research about context-free languages. A question that's popped up is whether or not there exists an unambiguous context-free language whose complement is not a context-free ...

**12**

votes

**5**answers

2k views

### Special arithmetic progressions involving perfect squares

Some time ago the following rather easy problem appeared in an online publication called "Problems in Elementary NT" by Hojoo Lee:
Prove that there are infinitely many positive integers $a$, $b$, $c$ ...

**11**

votes

**0**answers

284 views

### Generating random finite groups

I would like a method to efficiently generate a random finite group of a given order $n$.
If there are $g(n)$ non-isomorphic groups of order $n$,
ideally each group would occur with probability ...

**10**

votes

**12**answers

977 views

### Continuous notions with compelling discrete analogues

Following up on the previous MO question "Are there any important mathematical concepts without discrete analogue?", I'd like to ask the opposite: what are examples of notions in math that were not ...

**9**

votes

**5**answers

504 views

### Minimal blocking objects with shadows like a cube

This is a more geometric version of the previous question,
"Lattice-cube minimal blocking sets". I will first specialize to $\mathbb{R}^3$, $d=3$.
View an $n \times n \times n$ cube $C_3(n)$ as ...

**9**

votes

**1**answer

136 views

### Optimal shape for stabbing balls in $\mathbb{R}^3$

I have radius $r < \frac{1}{2}$ congruent balls with centers randomly distributed uniformly within a region,
say, within a unit-radius sphere $S$.
I shoot a ray/path through $S$, hoping to ...

**8**

votes

**2**answers

475 views

### Three half circles on the plane may not meet nicely

Let $H$ denote the union of the northen hemisphere of the unit circle $S^{1}$ with the interval $[-1,1]$ on the $x$-axis. That is, $H=\{(x,\sqrt{1-x^{2}}):-1\le x\le 1\}\cup\{(x,0):-1\le x\le 1\}$
...

**8**

votes

**2**answers

1k views

### palindromic subsequences

I'd like any insight or references to the following two conjectures (see the glossary below for definitions):
Conjecture 1: For any string $x$, there exists a longest common subsequence of $x$ and ...

**8**

votes

**1**answer

367 views

### Die-rolling Hamiltonian cycles

Let $R$ be a rectangular region of the integer lattice $\mathbb{Z}^2$,
each of whose unit squares is labeled with a number
in $\lbrace 1, 2, 3, 4, 5, 6 \rbrace$.
Say that such a labeled $R$ is ...

**7**

votes

**2**answers

285 views

### Iteration of a 2D map involving absolute value: phase transition?

I was looking at this map: $f(x,y) \mapsto (|x-y|,x)$, starting from some point
with coordinates $(x,y) \in [0,1]^2$, and iterating:
$(x,y),\, f(x,y), \, f^2(x,y), \,f^3(x,y), \ldots$.
It displays ...

**7**

votes

**3**answers

983 views

### How to characterize a Self-avoiding path.

I cannot find any answer to that apparently simple problem :
On a square lattice, a path is given by a sequence of relative moves in {"move forward", "turn right" and "turn left"}.
Is there a rule ...

**7**

votes

**6**answers

2k views

### Discrete Mathematics textbooks for undergraduates

For the first time, I will be teaching a course on Discrete Mathematics for electrical and computer undergraduates students.
I intend to focus on practical applications.
I would be grateful if ...

**7**

votes

**9**answers

441 views

### What are some early examples of creation of lists / catalogues of (particularly) combinatorial objects?

A lot of effort in discrete maths / combinatorics is expended in the construction of lists, catalogues or census [sic] of combinatorial objects such as groups, graphs, designs etc. These catalogues ...

**7**

votes

**2**answers

384 views

### A continuous function for defining unique values to a 1024x1024 image with a 24 bit 3 color channel image

I need to generate a color map which I am not sure exist. I have a 1024x1024 image which would contain 2^20 pixels. I have 3 color channels which each have 8 bits which would leave us with 2^24 ...

**7**

votes

**1**answer

229 views

### Number of median graphs?

What is the number of $n$-vertex median graphs? These graphs generalize hypercubes and trees, and have many applications. It seems unlikely that a closed form expression is known, so I would also be ...

**7**

votes

**1**answer

352 views

### Is this a new formula? $\Delta^d x^n/d! = \sum_k \left[ x \atop k\right]{ k+n \brace x + d}(-1)^{x+k}$

$$\frac{\Delta^d x^n}{d!} = \sum_k \left[ x \atop k\right]{ k+n \brace x + d}(-1)^{x+k}$$
Where $x$, $n$ and $d$ are non-negative integers, $\Delta^d$ is the $d$-th difference with respect to ...

**6**

votes

**3**answers

514 views

### Cylinders dividing $\mathbb{R}^{3}$

Consider $n$ affine copies of a compact cylinder, say $S^{1}\times [-3,3]$ with top and botom, sitting inside $\mathbb{R}^{3}$.
For each $n$ we may ask ourselves how to arrange the $n$ cylinders so ...

**6**

votes

**3**answers

667 views

### References on techniques for solving equations with discontinuous functions such as floor and ceiling?

Here I describe the sort of reference I'm after with a motivating example. I am not seeking solutions to my equations on this forum; I'm quite happy to do that myself. Rather, I'm asking for some good ...

**6**

votes

**1**answer

669 views

### Integer solution to special system of linear equations

This problem appear in my research, but I am unable to solve it.
There should be an easy argument, but I have not yet found it.
Informal version
An integer $k\geq 2$ is fixed.
We are given a matrix ...

**6**

votes

**1**answer

262 views

### A variation on Bulgarian solitare

It appears that a variation on Bulgarian solitare has a fixed point regardless
of the starting $n$.
For example, let $n=69$, and consider this partition:
$$
(8,8,7,7,5,5,5,5,5,4,3,3,2,2)
$$
In ...

**6**

votes

**1**answer

531 views

### Calculating a specific joint probability involving sums of binomial distributions

The following might look like a simple problem - but the question has been unanswered for more than a week on math.stackexchange.com, and I have asked quite a few of the Ph.d. students at our ...

**6**

votes

**0**answers

176 views

### Minimal “basis” in $n$ dimensional unit cube

Let's
$$
B^n=\{\bar\alpha=(\alpha_1,\alpha_2,\ldots,\alpha_n)|\alpha_i\in \{0,1\}\};~~~~n=1,2,\ldots
$$
and let's
$$
C\subseteq B^n,
$$
$$
S(C)=\{\bar\alpha\oplus\bar\beta\ | \bar\alpha,\bar\beta\in ...

**6**

votes

**0**answers

89 views

### Checking if a multiplication table represents a group [duplicate]

Given an $n \times n$ multiplication table,
can one check if it represents a group in $o(n^3)$ time?
All properties can be checked by mindless try-all possibilities loops:
Whether there is an ...

**6**

votes

**0**answers

732 views

### How many 2L-bit numbers are the product of two L-bit numbers?

If I multiply two integers $x, y $ in $[0,2^L)$, I get an integer in $[0,2^{2L})$. Clearly, this map from $[0,2^L) \times [0,2^L) \to [0,2^{2L})$ is not bijective.
I am interested in the size of ...

**5**

votes

**2**answers

254 views

### Lattice-cube minimal blocking sets

Let $C_d(n)$ be the lattice cube consisting of the $n^d$ points with
each of its $d$ coorindates in $\lbrace 1,2,\ldots,n \rbrace$.
Define a blocking set for a lattice cube to be a set of points
in ...

**5**

votes

**1**answer

234 views

### Reference sought for Conways observation on stable matchings.

Looking for a reference on the observation that the set of stable matchings form a distributive lattice. This is attributed to Conway by Knuth in "Marriages Stables" but I would like an explicit ...

**5**

votes

**1**answer

658 views

### Bounding the entropy of a convolution

Say we have a function $f:\mathbb{Z}_2^n \to \mathbb{R}$, such that $\sum _{x\in \mathbb{Z}_2^n} f(x)^2 = 1$ (so we can think of $\{ f(x)^2\} _{x\in \mathbb{Z}_2^n}$ as a distribution). It is natural ...

**5**

votes

**0**answers

456 views

### Optimal Gear Trains

Suppose you need to slow down a turning motor so that a gear turns at
an angular velocity $\frac{a}{b}$ of that of the motor shaft, where $a$ and
$b$ are natural numbers. For example, this set of ...

**5**

votes

**0**answers

717 views

### On “The Average Height of Planted Plane Trees” by Knuth, de Bruijn and Rice (1972)

I am trying to derive the classic paper in the title only by elementary means (no generating functions, no complex analysis, no Fourier analysis) although with much less precision. In short, I "only" ...

**4**

votes

**1**answer

246 views

### Best upper bound on rate for q-ary codes

Among the many upper bounds for families of codes in $\mathbb F _2 ^n$, the best known bound is the one by McEliece, Rodemich, Rumsey and Welch which states that the rate $R(\delta)$ corresponding to ...

**4**

votes

**2**answers

374 views

### Looking for construction related to Erdos-Szekeres theorem

The Erdos-Szekeres theorem says that every $n$-permutation $p(1), p(2), \ldots, p(n)$ has either an increasing run or a decreasing run of length $\sqrt n$, where an increasing run is
$p(i_1) < ...

**4**

votes

**1**answer

187 views

### Prime labelling of graphs

A prime labeling of a graph is an injective function $f: V(G) \to \{1, 2, ..., |V(G)|\}$
such that for every pair of adjacent vertices $u$ and $v$, $\text{gcd}(f(u), f(v)) = 1$ (labels of any two ...

**4**

votes

**2**answers

327 views

### Computer platforms for combinatorial search problems/mathematical music theory?

I'm finding programming various combinatorial searches
(connected to mathematical music theory) in a general purpose computer
language tedious, so I'd like pointers to computer platforms/environment ...

**4**

votes

**0**answers

212 views

### Domination in Nice Lattices

Let an integer vector be nice when it has only two nonzero components, which sum to zero. So (0, 0, 3, 0, -3) and (-1, 0, 1, 0, 0) are examples of nice vectors in $n=5$ dimensions.
Call a lattice ...

**3**

votes

**1**answer

254 views

### Number of semi-standard tableau

What is the number of semi-standard tableau (weakly increasing on rows and strictly increasing on columns) for the partition $2n=n+n$ with entries $\{1,2, \cdots ,n\}$ such that each $i$ appears ...

**3**

votes

**2**answers

346 views

### The cycle structure of twisted wires, connected

Suppose you have $n$ (blue) wires linearly arrayed at junction box $A$,
connected to a remote junction box $B$, where the wires are now
arrayed
along a line in a randomly permuted order, i.e.,
each ...

**3**

votes

**1**answer

702 views

### Decomposition of a complete graph into maximal matching subgraphs

Is there a general way to decompose a complete graph $K_n$ into an union of maximal matching subgraphs such that no two subgraphs share an edge?
For example, consider $K_4$ with vertices ...

**3**

votes

**2**answers

283 views

### Cardinality of intersection of a random subset with a fixed subset

How can I simply prove the following fact:
Let $A := \{1, \dots n \}$ and $B := \{1, \dots, \lfloor \frac{n}{4} \rfloor \}$. Let $d \in (0,1)$ and let $R$ be a randomly choosen (with uniform ...

**3**

votes

**2**answers

343 views

### anyone help me with this inequality

I'm have some difficulties in bounding the following inequality:
I want to find a c as small as possible s.t.
$$\sum_{i=1}^nx_i^4\sum_{i=1}^nx_i^2 -\sum_{i=1}^nx_i^6 \leq ...