The tag has no wiki summary.

learn more… | top users | synonyms

34
votes
6answers
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
5answers
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 ...
20
votes
5answers
640 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
1answer
263 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
2answers
741 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 ...
15
votes
8answers
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
1answer
644 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 ...
13
votes
4answers
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
3answers
786 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
1answer
451 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
1answer
240 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
5answers
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
1answer
320 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 \mod 3$, we place, with equal probability, one of these six patterns:       The result ...
11
votes
0answers
269 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 ...
9
votes
12answers
966 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
5answers
500 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 ...
8
votes
2answers
473 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
2answers
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
1answer
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
2answers
282 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
3answers
974 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
6answers
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
9answers
437 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
2answers
364 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
1answer
213 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
1answer
347 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
3answers
505 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
3answers
611 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
1answer
647 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
1answer
259 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
1answer
527 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
0answers
171 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
0answers
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
0answers
731 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
2answers
248 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
1answer
233 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
1answer
640 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
0answers
434 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
0answers
695 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
1answer
225 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
2answers
350 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
2answers
323 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
0answers
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
2answers
345 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
1answer
676 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
2answers
265 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
2answers
342 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 ...
3
votes
2answers
212 views

Designing a tree to match a distribution

I want to design a tree to approximate a given sequence of numbers, in the following sense. Let $X=(x_1,\ldots,x_n)$ be $n$ numbers, with $0 < x_i \le 1$ and $\sum_i x_1 = 1$. For a rooted tree ...
3
votes
1answer
261 views

Sequences with integral variances

This is a companion to my earlier question, Sequences with integral means. This new question is, frankly, not as interesting, but it feels necessary to complete the thought. Let $V(n)$ be the ...
3
votes
1answer
138 views

what's an upper bound on the size of the largest biclique in random bipartite graph?

I am not an expert in random graph but I need the following result and I couldn't find any reference on this. Let $G(X \cup Y,p)$ be a random bipartite graph where the set of edges is $X \cup Y$, $X$ ...