Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.

learn more… | top users | synonyms (1)

51
votes
1answer
3k views

What is the amplituhedron?

The paper ”Scattering Amplitudes and the Positive Grassmannian” by Nima Arkani-Hamed, Jacob L. Bourjaily, Freddy Cachazo, Alexander B. Goncharov, Alexander Postnikov, and Jaroslav Trnka, introduces ...
5
votes
1answer
435 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 ...
37
votes
2answers
5k 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 ...
25
votes
2answers
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, ...
22
votes
3answers
1k 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 ...
6
votes
2answers
1k 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 ...
5
votes
1answer
823 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 ...
20
votes
2answers
1k views

Number of elements in the set $\{1,\cdots,n\}\times\{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)$?
15
votes
2answers
730 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 ...
11
votes
3answers
883 views

A problem on a specific integer partition

Let $n$ be a positive integer, we consider partitions of the following form : $$n = d^{2}_{1} + d^{2}_{2} + ... + d^{2}_{r}$$ such that : $d_{i}\vert n$ $1=d_{1}<d_{2} \le d_{3} \le ... \le ...
8
votes
7answers
3k 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 ...
7
votes
1answer
235 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 ...
6
votes
2answers
364 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$?
5
votes
2answers
202 views

Anticoncentration of the convolution of two characteristic functions

Edit: This is a question related to my other post, stated in a much more concrete way I think. I am interested in anything (ideas, references) related to the following problem: Suppose that $A ...
4
votes
4answers
1k views

Mean minimum distance for N random points on a unit square (plane)

A previously posted question "mean minimum distance for N random points on a one-dimensional line" produced an elegant answer: for a line of length L, the expected minimum distance (between random ...
6
votes
1answer
175 views

The time to drift a binary string from one state to another via deterministic selection of two possible random bit mutation procedures

I have some length $L$ binary string consisting of an ordered array of bits: $(b_1, b_2, ..., b_{L})$, where all bit values $b_i$ are originally set to zero. I'd like a particular set of $n$ bits to ...
4
votes
1answer
171 views

Graphs with constant edge imbalance

The imbalance of an edge $(u,v) \in E(G)$ of a graph $G$ is defined as $|d(u)-d(v)|$ ($d$ being, as usual the degree). (This concept was introduced by Albertson in 1997) I'm interested in the set of ...
8
votes
2answers
673 views

Sperner's lemma and Tucker's lemma

In their article "A Borsuk-Ulam Equivalent that Directly Implies Sperner's Lemma" (American Mathematical Monthly, April 2013), Nyman and Su write "[W]e are unaware of a direct proof that Tucker's ...
3
votes
1answer
112 views

Reference for partial Hadamard matrices

Definition. An $m\times n$ matrix is said to be a partial Hadamard matrix (let's say PHM) if its entries are chosen from $\lbrace -1, 1 \rbrace$ such that the dot product of each pair of row vectors ...
2
votes
1answer
270 views

Automorphism groups of indefinite non-unimodular integer lattices

Does anyone know of any papers in which structural aspects of the orthogonal group of some indefinite non-unimodular integral lattice are calculated? The exact lattice isn't so important and they ...
2
votes
3answers
989 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 ...
55
votes
17answers
34k views

Google question: In a country in which people only want boys [closed]

Hi all! Google published recently questions that are asked to candidates on interviews. One of them caused very very hot debates in our company and we're unsure where the truth is. The question is: ...
35
votes
6answers
3k 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 ...
29
votes
6answers
2k views

Why do Littlewood-Richardson coefficients describe the cohomology of the Grassmannian?

I'm looking for a "conceptual" explanation to the question in the title. The standard proofs that I've seen go as follows: use the Schubert cell decomposition to get a basis for cohomology and show ...
37
votes
2answers
1k views

Numbers that are generic w.r.t. exponentiation

This is a follow-up to my old question Number of distinct values taken by $x\hat{\phantom{\hat{}}}x\hat{\phantom{\hat{}}}\dots\hat{\phantom{\hat{}}}x$ with parentheses inserted in all possible ways. ...
31
votes
4answers
2k 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 $$ ...
26
votes
3answers
4k views

Why are planar graphs so exceptional?

As compared to classes of graphs embeddable in other surfaces. Some ways in which they're exceptional: Mac Lane's and Whitney's criteria are algebraic characterizations of planar graphs. (Well, ...
21
votes
5answers
4k views

Erdos Conjecture on arithmetic progressions

Introduction: Let A be a subset of the naturals such that $\sum_{n\in A}\frac{1}{n}=\infty$. The Erdos Conjecture states that A must have arithmetic progressions of arbitrary length. Question: I ...
22
votes
18answers
5k 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 ...
30
votes
4answers
2k views

“Circular” domination in ${\mathbb R}^4$

The following problem is related to (and motivated by) the first open case of this MO question. It is difficult to believe that this is a hard problem; and yet, I do not have a solution. For two ...
29
votes
4answers
2k 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 ...
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 ...
29
votes
20answers
3k 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; ...
18
votes
0answers
2k views

Why do polytopes pop up in Lagrange inversion?

I'd be interested in hearing people's viewpoints on this. Looking for an intuitive perspective. See Wikipedia for descriptions of polytopes and the Lagrange inversion theorem/formula (LIF) for ...
18
votes
0answers
1k views

Trigonometry related to Rogers--Ramanujan identities

For integers $n\ge2$ and $k\ge2$, fix the notation $$ [m]=\sin\frac{\pi m}{nk+1} \quad\text{and}\quad [m]!=[1][2]\dots[m], \qquad m\in\mathbb Z_{>0}. $$ Consider the following trigonometric ...
19
votes
6answers
5k 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 ...
18
votes
1answer
1k views

Number of distinct values taken by x^x^…^x with parentheses inserted in all possible ways

For what positive x's the number of distinct values taken by x^x^...^x with parentheses inserted in all possible ways is not represented by the sequence A000081? Is it exactly the set of positive ...
33
votes
3answers
2k views

the following inequality is true,but I can't prove it

The inequality is \begin{equation*} \sum_{k=1}^{2d}\left(1-\frac{1}{2d+2-k}\right)\frac{d^k}{k!}>e^d\left(1-\frac{1}{d}\right) \end{equation*} for all integer $d\geq 1$. I use computer to verify ...
30
votes
4answers
2k views

Verifying the correctness of a Sudoku solution

A Sudoku is solved correctly, if all columns, all rows and all 9 subsquares are filled with the numbers 1 to 9 without repetition. Hence, in order to verify if a (correct) solution is correct, one has ...
23
votes
4answers
1k views

Asymptotic growth of a certain integer sequence

Some time ago, while putting my nose in the Sloane's Online Encyclopedia of Integer Sequences, I came over the sequence A019568 defined as follows: $a(n):=$ the smallest positive integer $k$ such ...
19
votes
8answers
1k views

Higher-dimensional Catalan numbers?

One could imagine defining various notions of higher-dimensional Catalan numbers, by generalizing objects they count. For example, because the Catalan numbers count the triangulations of convex ...
15
votes
5answers
2k views

Complete graph invariants?

Obviously, graph invariants are wonderful things, but the usual ones (the Tutte polynomial, the spectrum, whatever) can't always distinguish between nonisomorphic graphs. Actually, I think that even a ...
12
votes
5answers
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 ...
12
votes
3answers
2k 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 ...
17
votes
3answers
2k views

Need help proving that $\sum\limits_{j=0}^{k-1}(-1)^{j+1}(k-j)^{2k-2} \binom{2k+1}{j} \ge 0$

Hello. I have been trying very hard to show that $\sum\limits_{j=0}^{k-1}(-1)^{j+1}(k-j)^{2k-2} \binom{2k+1}{j} \ge 0$ and could not quite get anywhere. This inequality has been verified by computer ...
24
votes
2answers
613 views

Is there any superstable configuration in the game of life?

This question spins off of Gil Kalai's recent question on Conway's game of life for a random initial configuration. There are numerous configurations in the game of life that are known to be ...
22
votes
8answers
13k 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 ...
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 ...
13
votes
2answers
1k views

roots of permutations

Consider equation $x^2=x_0$ in symmetric group $S_n$, where $x_0\in S_n$ is fixed. Is it true that for each integer $n\geq 1$, the maximal number of solutions (square roots) has identity permutation? ...
12
votes
11answers
2k views

Applications of Measure, Integration and Banach Spaces to Combinatorics

I'm going to be teaching a Master's level analysis course(measure theory, Lebesgue integration, Banach and Hilbert spaces, and if there's time, some spectral or PDE stuff) in the fall. My problem is ...