# Tagged Questions

**42**

votes

**3**answers

3k views

### Number of elements in the set $\{1,\cdots,n\}\cdot\{1,\cdots,n\}$

Let $A_n=\{a\cdot b : a,b \in \mathbb{N}, a,b\leq n\}$. Are there any estimates for $|A_n|$? Will it be $o(n^2)$?

**25**

votes

**6**answers

3k views

### Generating finite simple groups with $2$ elements

Here is a very natural question:
Q: Is it always possible to generate a finite simple group with only $2$ elements?
In all the examples that I can think of the answer is yes.
If the answer is ...

**9**

votes

**7**answers

6k views

### Lower bound for sum of binomial coefficients?

Hi! I'm new here. It would be awesome if someone knows a good answer.
Is there a good lower bound for the tail of sums of binomial coefficients? I'm particularly interested in the simplest case $\...

**5**

votes

**1**answer

513 views

### Difference Sets

Suppose
$$
P \subseteq \{1,2,\dots,N\},\quad |P| = K
$$
We calculate the differences as: $$d=p_i-p_j\mod N,\quad i\ne j$$
Now let $a_d$ denote the number of occurrence of $d$ (for $d = 1, 2, \dots , N ...

**38**

votes

**11**answers

30k views

### Sum of 'the first k' binomial coefficients for fixed n

I am interested in the function $\sum_{i=0}^{k} {N \choose i}$ for fixed $N$ and $0 \leq k \leq N $. Obviously it equals 1 for $k = 0$ and $2^{N}$ for $k = N$, but are there any other notable ...

**30**

votes

**4**answers

2k views

### Cliques, Paley graphs and quadratic residues

A question I've thought about, on and off for a long time, is how to improve the best bounds that (seem to be) known for the clique numbers of Paley graphs.
If p=1 mod 4 is a prime, we can define the ...

**9**

votes

**2**answers

2k views

### Riemann zeta function at positive integers and an Appell sequence of polynomials related to fractional calculus

I was exploring some raising and lowering operators related to an infinitesimal generator for fractional integro-derivatives and found an Appell sequence of polynomials, i.e., an infinite sequence of ...

**11**

votes

**2**answers

523 views

### The Simultaneous Conjugacy Problem in the symmetric group $S_N$

We are interested in the following notions in the case $G=S_N$, the symmetric group on
$\{1,\dots,N\}$.
Fix a group $G$ and a number $d$. For $(g_1,\dots,g_d)\in G^d$ and $x\in G$, define
$$(g_1,\...

**51**

votes

**6**answers

5k views

### How to recognise that the polynomial method might work

A couple of days ago I was at a nice seminar given by Christian Reiher, during which he told us about a short proof of the following special case of a theorem of Olson.
Theorem. Let $(a_1,b_1),\dots,(...

**14**

votes

**3**answers

3k views

### Number of unique determinants for an NxN (0,1)-matrix.

I'm interested in bounds for the number of unique determinants of NxN (0,1)-matrices. Obviously some of these matrices will be singular and therefore won't have a determinant. While it might also be ...

**35**

votes

**2**answers

2k views

### A question on maps from $\mathbb{Z}/p\mathbb{Z}$ to itself

Let $p\geq 3$ be a prime number, and let $u:\mathbb{Z}/p\mathbb{Z}\to \mathbb{Z}/p\mathbb{Z}$ be a map such that, for all $l\in \mathbb{Z}/p\mathbb{Z}$,$l\neq 0$, the map $k\mapsto u(k+l)-u(k)$ is a ...

**7**

votes

**1**answer

1k views

### Cycling through the Zeta Garden: Zeta functions for graphs, cycle index polynomials, and determinants

Zeta functions abound in mathematics. Audrey Terras describes in Zeta Functions and Chaos three zeta functions--the zeta fct. of a projective non-singular algebraic variety; the Artin-Mazur zeta ...

**17**

votes

**2**answers

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

**10**

votes

**2**answers

935 views

### Number of isomorphism types of finite groups

Are there some good asymptotic estimations for the number $F(n)$ of non-isomorphic finite groups of size smaller than $n$?

**2**

votes

**1**answer

597 views

### The number of pairings between multisets

Given two multisets $A$ and $B$ of the same finite cardinality $n$, how many ways are there of pairing the two sets together?
If both sets consist of distinct elements, the answer is $n!$: there are $...

**12**

votes

**0**answers

450 views

### Possible orders of products of 2 involutions which interchange disjoint residue classes of the integers

Definition / Question
Definition: Let $r(m)$ denote the residue class $r+m\mathbb{Z}$, where
$0 \leq r < m$.
Given disjoint residue classes $r_1(m_1)$ and $r_2(m_2)$, let the class transposition
$...

**2**

votes

**3**answers

2k views

### Estimating a partial sum of weighted binomial coefficients

There is a well-known estimate for the sum of all binomial coefficients $\binom{n}{k}$ satisfying $k \leq \alpha n$ for some $\alpha$ satisfying $0 < \alpha \leq 1/2$:
$$ \sum_{k=0}^{\alpha n}\...

**4**

votes

**1**answer

780 views

### The property of Kendall-Mann numbers

The sequence A000140 is studied
http://oeis.org/A000140
(Kendall-Mann numbers: the maximum number of permutations on n letters having the same number of inversions )
and I am looking for a proof ...

**75**

votes

**51**answers

12k views

### Important formulas in Combinatorics

Motivation:
The poster for the conference celebrating Noga Alon's 60th birthday, fifteen formulas describing some of Alon's work are presented. (See this post, for the poster, and cash prizes offered ...

**65**

votes

**10**answers

9k views

### Why do Bernoulli numbers arise everywhere?

I have seen Bernoulli numbers many times, and sometimes very surprisingly. They appear in my textbook on complex analysis, in algebraic topology, and of course, number theory. Things like the criteria ...

**33**

votes

**17**answers

8k views

### Linear Algebra Proofs in Combinatorics?

Simple linear algebra methods are a surprisingly powerful tool to prove combinatorial results. Some examples of combinatorial theorems with linear algebra proofs are the (weak) perfect graph theorem, ...

**60**

votes

**6**answers

3k views

### Does every polyomino tile R^n for some n?

This is a question posed by Adam Chalcraft. I am posting it here because I think it deserves wider circulation, and because maybe someone already knows the answer.
A polyomino is usually defined to ...

**88**

votes

**7**answers

5k views

### Is the set $ AA+A $ always at least as large as $ A+A $?

Let $A$ be a finite set of real numbers. Is it always the case that $|AA+A| \geq |A+A|$?
My first instinct is that this is obviously true, and there is a one-line proof which I am foolishly ...

**42**

votes

**2**answers

6k views

### Walsh Fourier Transform of the Möbius function

This question is related to this previous question where I asked about ordinary Fourier coefficients.
Special case: is Möbius nearly Orthogonal to Morse
!
Harold Calvin Marston Morse (24 March ...

**36**

votes

**4**answers

3k views

### Integer-valued factorial ratios

This historical question recalls
Pafnuty Chebyshev's estimates for the prime distribution function. In his derivation
Chebyshev used the factorial ratio sequence
$$
u_n=\frac{(30n)!n!}{(15n)!(10n)!(6n)...

**30**

votes

**18**answers

11k views

### Interesting and Accessible Topics in Graph Theory

This summer, I will be teaching an introductory course in graph theory to talented high school seniors. The intent of the course is not to establish proficiency in graph theory, per se. Rather, I hope ...

**33**

votes

**20**answers

4k views

### Generalizations of Planar Graphs

This is a follow up to Harrison's question: why planar graphs are so exceptional. I would like to ask about (and collect answers to) various notions, in graph theory and beyond graph theory (topology; ...

**20**

votes

**6**answers

6k views

### A balls-and-colours problem

A box contains n balls coloured 1 to n. Each time you pick two balls from the bin - the first ball and the second ball, both uniformly at random and you paint the second ball with the colour of the ...

**34**

votes

**5**answers

3k views

### Groups, quantum groups and (fill in the blank)

In the study of special functions there are three levels of objects, classical, basic and elliptic. These correspond to classical hypergeometric functions, basic (q-) hypergeometric functions, and ...

**22**

votes

**1**answer

717 views

### Two conjectures about zero inner products and dissociated sets

The following problems come from something I worked on (with my coauthors) related to proving a new time lower bound for streaming problems. Having worked on these problems for some time with little ...

**42**

votes

**12**answers

5k views

### Generalizations of the Four-Color theorem

The four color theorem asserts that every planar graph can be properly colored by four colors.
The purpose of this question is to collect generalizations, variations, and strengthenings of the four ...

**19**

votes

**4**answers

2k views

### Number of vectors so that no two subset sums are equal

Consider all $10$-tuple vectors each element of which is either $1$ or $0$. It is very easy to select a set $v_1,\dots,v_{10}= S$ of $10$ such vectors so that no two distinct subsets of vectors $S_1 \...

**39**

votes

**0**answers

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

**36**

votes

**6**answers

2k views

### Placing numbers $1,2,\ldots,n^3$ in a cube so that numbers of any two adjacent unit subcube are coprime

This is a question first I asked in SE but since there was no suggestion or solution, I decide to put it here.
Consider an $n\times n \times n$ Cube containing $n^3$ unit cubes. Is it possible to ...

**16**

votes

**10**answers

3k views

### Applications of infinite Ramsey's Theorem (on N)?

Finite Ramsey's theorem is a very important combinatorial tool that is often used in mathematics. The infinite version of Ramsey's theorem (Ramsey's theorem for colorings of tuples of natural numbers) ...

**25**

votes

**2**answers

1k views

### Is there a finite family of functions such that the max of any two functions can be dominated by a third?

Is it true that for every $t$ there is an $n$ and there exists a finite function
family, $\cal F$, whose members are from $[n] \to \mathbb N$ (taking all different
values) and for any $f_1, \ldots, ...

**47**

votes

**4**answers

5k views

### Connectivity of the Erdős–Rényi random graph

It is well-known that if $\omega=\omega(n)$ is any function such that $\omega \to \infty$ as $n \to \infty$, and if $p \ge (\log{n}+\omega) / n$ then the Erdős–Rényi random graph $G(n,p)$ is ...

**12**

votes

**2**answers

1k views

### Combinatorics of the Stasheff polytopes

First a little background for those unaware. The Stasheff polytopes (or associahedra) are certain convex polytopes that arise in the theory of $A_\infty$-algebras. There is one polytope for each $n\...

**30**

votes

**1**answer

1k views

### How hard is reconstructing a permutation from its differences sequence?

My interest in combinatorially motivated computational problems led me to search for simple problems that turn out to be computationally hard. In this pursuit, I came up with a problem which I hope is ...

**14**

votes

**5**answers

1k views

### A general formula for the number of conjugacy classes of $\mathbb{S}_n \times \mathbb{S}_n$ acted on by $ \mathbb{S}_n$

$\def\S{\mathbb{S}}$ Dear all,
So I have $\S_n$ acting on $\S_n \times \S_n$ via conjugacy. That is:
for $g \in \S_n, (x,y) \in \S_n \times \S_n$: $g(x,y) = (gxg^{-1},gyg^{-1}).$
Is there a general ...

**34**

votes

**2**answers

847 views

### How close can one get to the missing finite projective planes?

This question can be interpreted as an instance of the Zarankiewicz problem. Suppose we have an $n\times n$ matrix with entries in $\{0,1\}$ with no $\begin{pmatrix}1 & 1\\ 1& 1\end{pmatrix} $ ...

**19**

votes

**2**answers

1k views

### Calculating Mayer-Vietoris efficiently

This is a question whose motivation and framing seem to involve a lot of topology, but which I suspect comes down to some simple and standard combinatorics that's probably recorded in a book somewhere....

**21**

votes

**3**answers

2k views

### How many different numbers can be obtained as product of first $n$ natural numbers?

Let m and n be natural numbers, and consider the set of all possible products of m (not necessarily distinct) elements from the set $\{1,2,\ldots,n\}$, that is consider the set
$\{1^{a_1} \cdot 2^{...

**18**

votes

**1**answer

500 views

### Rearrangements that never change the value of a sum

I posted this question on math.stackexchange.com and so far the only answer posted (also mentioned in the comments under the question) shows that one of my rash initial guesses about the bottom-line ...

**19**

votes

**3**answers

2k views

### Does subgroup structure of a finite group characterize isomorphism type?

Question
Suppose there is a bijection between the underlying sets of two finite groups $G, H$, such that every subgroup of $G$ corresponds to a subgroup of $H$, and that every subgroup of $H$ ...

**18**

votes

**1**answer

1k views

### A geometric series equalling a power of an integer

The following problem cropped up whilst considering generalised quadrangles with a product structure, and it boils down to a simple number theoretic problem. Let $s$ be an integer greater than 2 and ...

**10**

votes

**2**answers

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

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

**16**

votes

**1**answer

540 views

### Reference request: a conjecture of Rota on positive functions of a random variable

Rota and Shen's On the Combinatorics of Cumulants ends with a conjecture which I'll restate as follows:
Let $p \in \mathbb{R}[x_1, x_2, ...]$ be a polynomial such that, for any sequence $X_1, X_2,...

**15**

votes

**5**answers

607 views

### The smallest disk containing all sides of an $n$-gon

Start with a regular $n$-gon of side 1 and consider its sides as open segments that can be moved around in the plane, allowing only translations. Two segments may not intersect.
What is the ...