All Questions
Tagged with combinatorics or co.combinatorics
11,023 questions
25
votes
6
answers
2k
views
Relations between sums of powers
This question is so naive that it could have been asked before on this site. If so, I'll delete it.
Among beautiful formula, I like a lot this one:
$$\left(\sum_{n=1}^Nn\right)^2=\sum_{n=1}^Nn^3.$$
...
- 52.3k
25
votes
2
answers
2k
views
Who first dubbed them "expander graphs"?
Expander graphs
("sparse graphs that have strong connectivity properties")
burst onto the mathematical scene around the millennium, but I have not
been successful in tracing the origin of
(a) the ...
- 151k
25
votes
3
answers
2k
views
Is the sequence of partition numbers log-concave?
Let $p(n)$ denote the number of partitions of a positive integer $n$. It seems to me that we have for all $n>25$
$$
p(n)^2>p(n-1)p(n+1).
$$
In other words, the sequence $(p(n))_{n\in \mathbb{N}}$...
- 12.1k
25
votes
7
answers
2k
views
Number of collinear ways to fill a grid
A way to fill a finite grid (one box after the other) is called collinear if every newly filled box (the first excepted) is vertically or horizontally collinear with a previously filled box. See the ...
25
votes
1
answer
1k
views
Expected height of a poset?
I am interested in any known results/empirical studies done on the average height of a poset with $N$ elements. Obviously this would depend on how that poset relation was randomly defined, however, at ...
- 662
25
votes
5
answers
3k
views
Sperner Lemma Applications
I was always fascinated with this result. Sperner's lemma is a combinatorial result which can prove some pretty strong facts, as Brouwer fixed point theorem. I know at least another application of ...
25
votes
3
answers
1k
views
The verbs in combinatorics: Enumerating, counting, listing and all that
Two closely related, but different tasks in combinatorics are
determining the number of elements in some set $A$, and
presenting all its elements one by one.
Question: What are some works in ...
- 4,219
25
votes
7
answers
3k
views
Computer package for representation theory of the symmetric group
Is there a computer algebra package in which I can compute the following for representations of a specific symmetric group (e.g. $S_7$):
(1) $V \otimes W$
(2) $S_\lambda V$, where $S_\lambda$ is a ...
25
votes
3
answers
1k
views
what else is in $\prod_{j=1}^n(1+q^j)$?
From time to time, I run into the finite product $\prod_{j=1}^n(1+q^j)$. And, the more it happens, the more fascinated I've become. So, herein, I wish to get help in collecting such results. To give ...
- 43.2k
25
votes
3
answers
2k
views
Some models for random graphs that I am curious about
G(n,p)
We are familiar with the standard notion of random graphs where you fixed the number n of vertices and choose every edge to belong to the graph with probability 1/2 (or p) independently. This ...
- 24.7k
25
votes
2
answers
1k
views
The number of polynomials on a finite group
A function $f:X\to X$ on a group $X$ is called a polynomial if there exist $n\in\mathbb N=\{1,2,3,\dots\}$ and elements $a_0,a_1,\dots,a_n\in X$ such that $f(x)=a_0xa_1x\cdots xa_n$ for all $x\in X$. ...
- 41.8k
25
votes
6
answers
4k
views
undecidable sentences of first-order arithmetic whose truth values are unknown
Godel's undecidable sentences in first-order arithmetic were guaranteed to be true, by construction. But are there examples of specific sentences known to be undecidable in first-order arithmetic ...
- 1,189
25
votes
2
answers
692
views
Convex hull of total orders
Let $n$ be a positive integer and $\prec$ an arbitray total order on $\{1,\dots,n\}$. I associate to this order a vector $v$ with one coordinate for every pair $(i,j)$ s.t. $1\leq i\neq j \leq n$, by ...
- 4,484
25
votes
3
answers
1k
views
Removal of non-isomorphic edges results in the same graph
There exists a (simple unlabeled) graph on 6 nodes with a pair of non-isomorphic edges (i.e., there is no graph automorphism that sends one edge into the other) such that removal of either of them ...
- 34.3k
25
votes
1
answer
2k
views
Polyomino that can tile itself
Find all polyomino $P$ such that we can tile $nP$ with $n^2$ copies of $P$ for all $n\in \mathbb{N}$. ($nP$ is a polynomino similar to $P$ with scale factor $n$)
I conjecture that there are only $4$ ...
- 1,462
25
votes
3
answers
2k
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
...
- 60.5k
25
votes
1
answer
2k
views
A Question on 1, 2 ,3 Conjecture
The 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 ...
- 2,381
25
votes
1
answer
1k
views
Sane bound on number of moves for Maker-Breaker game on $\mathbb R^2$ for $\{0,1,2,3,4\}$
The description below comes from
József Beck. Combinatorial games. Tic-tac-toe theory, Encyclopedia of Mathematics and its Applications, 114. Cambridge University Press, Cambridge, 2008, MR2402857 (...
- 32.5k
25
votes
1
answer
596
views
Doubly periodic 4 color theorem?
Let $G$ be a graph embedded (without crossings) on a torus $T$. It's fairly well known that this implies the chromatic number of $G$ is at most 7. If I lift $G$ to the universal cover of $T$, we get a ...
- 2,242
25
votes
1
answer
1k
views
Disjoint stable sets in tournaments
Let $(V,A)$ be a tournament. A subset of vertices $V'\subseteq V$ is stable if
there exists no $v\in V\setminus V'$ such that $V'\cup${$v$} contains an inclusion-maximal transitive subtournament with ...
- 331
25
votes
3
answers
2k
views
Is the Ford-Fulkerson algorithm a tropical rational function?
The Ford-Fulkerson algorithm
Let me recall the standard scenario of flow optimization (for integer flows at least):
Let $\mathbb{N} = \left\{0,1,2,\ldots\right\}$. Consider a digraph $D$ with vertex ...
- 33.8k
24
votes
5
answers
3k
views
Is Cauchy induction used for proofs other than for AM–GM?
The proof by Cauchy induction of the arithmetic/geometric-mean inequality is well known. I am looking for a further theorem whose proof is much neater by this method than otherwise.
- 2,437
24
votes
1
answer
1k
views
Why 'excedances' of permutations? [closed]
For a permutation $\pi=\pi_1\pi_2\cdots\pi_n$ written in one-line notation, an index $i$ for which $\pi_i > i$ is usually called an 'excedance.' To me, this seems like a mispelling of what should ...
- 24.2k
24
votes
6
answers
2k
views
Factorization of the characteristic polynomial of the adjacency matrix of a graph
Let $G$ be a regular graph of valence $d$ with finitely many vertices, let $A_G$ be its adjacency matrix, and let $$P_G(X)=\det(X-A_G)\in\mathbb{Z}[X]$$ be the adjacency polynomial of $G$, i.e., the ...
- 47.4k
24
votes
6
answers
5k
views
Neutral tic tac toe
I heard this puzzle from Bob Koca. Suppose we play misere tic-tac-toe (a.k.a. noughts and crosses) where both players are X. Who wins?
That particular puzzle is easy to solve, but more generally, ...
- 82.7k
24
votes
4
answers
36k
views
Finding a cycle of fixed length
Is there any result about the time complexity of finding a cycle of fixed length $k$ in a general graph?
All I know is that Alon, Yuster and Zwick use a technique called "color-coding",
which has a ...
- 1,250
24
votes
2
answers
3k
views
A Putnam problem with a twist
This question is motivated by one of the problem set from this year's Putnam Examination. That is,
Problem. Let $S_1, S_2, \dots, S_{2^n-1}$ be the nonempty subsets of $\{1,2,\dots,n\}$ in some ...
- 43.2k
24
votes
2
answers
2k
views
Can one measure the infeasibility of four color proofs?
Terms like "impractical" and "unfeasible" are used to say the Robertson, Sanders, Seymour, and Thomas proof of the four color theorem needs computer assistance. Obviously no precise measure is ...
- 11.1k
24
votes
5
answers
3k
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 ...
- 349
24
votes
4
answers
3k
views
What is the shortest route to Roth's theorem?
Roth first proved that any subset of the integers with positive density contains a three term arithmetic progression in 1953. Since then, many other proofs have emerged (I can think of eight off the ...
- 7,013
24
votes
8
answers
4k
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 ...
- 151k
24
votes
3
answers
4k
views
What upper bounds are known for the diameter of the minimum spanning tree of $n$ uniformly random points in $[0,1]^2$?
Let $P$ be a pointset consisting of $n$ uniformly random elements of $[0,1]^2$. It is known that the diameter (greatest number of edges in any shortest path between two points) of the Delaunay ...
- 4,922
24
votes
1
answer
3k
views
Can an odd number of marbles jump to infinity?
Loosely inspired by the game Abalone, I've encountered the following simple problem I cannot solve.
Suppose that we are given a finite set of marbles on an infinite chessboard.
One move consists of ...
- 18.9k
24
votes
2
answers
2k
views
Spencer's "six standard deviations" theorem - better constants?
This question is about Joel Spencer's famous "six standard deviations" theorem. The theorem says that when
$$
L_i(x_1,\dots,x_n) = a_{i1} x_1 + \dots + a_{in} x_n, \quad 1 \leq i \leq n,
$$
are $n$ ...
- 2,207
24
votes
2
answers
1k
views
Combinatorial meaning of the functional equation for logarithm
If we set $\exp(x)=\sum x^k/k!$, then $\exp(x+y)=\exp(x)\cdot \exp(y)$. In terms of coefficients it means that $(x+y)^n=\sum \frac{n!}{k!(n-k)!} x^ky^{n-k}$, i.e. just binomial expansion.
Now ...
- 109k
24
votes
3
answers
2k
views
Gauss-Bonnet Theorem for Graphs?
One can define the Euler characteristic χ for a graph as the number of vertices minus the number of edges. Thus an $n$-cycle has $\chi = 0$ and $K_4$ has $\chi=-2$.
Is there an analog for the ...
- 151k
24
votes
1
answer
2k
views
A puzzle about finding three points $(x,y)$, $(x,z)$ and $(y,z)$ in a subset of a square.
I was asked (by myself) to give a proof of the following seemingly simple geometric statement, but after thinking a little I now suspect it could be less elementary than I thought (or am I being silly?...
- 60.5k
24
votes
3
answers
865
views
an operation on binary strings
Recently, as part of some joint research, Tom Roby was led to a curious operation on strings of L's and R's which he calls "bounce-reading": We start by reading the string at the left. When the ...
- 19.7k
24
votes
4
answers
2k
views
How many simplicial complexes on n vertices up to homotopy equivalence?
Fix a number $n$, and define $\gamma(n)$ to be the number of simplicial complexes on $n$ unlabeled vertices up to homotopy equivalence. It is unlikely that an explicit formula exists, but what is ...
- 15.5k
24
votes
1
answer
3k
views
What can be tiled by T-tetrominoes?
The T-tetromino is a T-shaped figure made of four unit squares.
An $m\times n$ rectangle can be tiled by T-tetrominoes if and only if both $m$ and $n$ are multiples of 4. This was proved in a 1965 ...
- 32.4k
24
votes
1
answer
593
views
Has the $E_8$-based generating function for squares numbers been proven?
In his 2004 paper Conformal Field Theory and Torsion Elements of the Bloch Group, Nahm explains a physical argument due to Kadem, Klassen, McCoy, and Melzer for the following remarkable identity. Let $...
- 54.6k
24
votes
5
answers
5k
views
Pairwise intersecting sets of fixed size
The Erdős-Ko-Rado theorem talks about how large an intersecting set system (a set of pairwise intersecting sets) can be if the size of the base set is fixed. I'm interested about intersecting set ...
- 1,944
24
votes
2
answers
3k
views
A product approximation to the Taylor series of the exponential
I recently came across the following in something I'm working on, and I'd never seen it before. Consider
\begin{align*}
f_1(x) &= (1+x)^{1/1} \\\
f_2(x) &= (1+x)^{2/1} (1+2x)^{-1/2} \\\
f_3(...
- 27.2k
24
votes
1
answer
622
views
Polytope where each vertex belongs to all but two facets
Let $P$ be a (convex, bounded) polytope with the following property: for every vertex $v$, there are exactly two facets which do not contain $v$. Does it follow that $P$ is (combinatorially) a ...
- 4,653
24
votes
1
answer
1k
views
Combinatorial spin structures
I would like to know how to define spin structures combinatorially, for an oriented smooth manifold equipped with a triangulation. In the case of a 2d manifold, spin structures correspond to ...
- 1,579
24
votes
1
answer
659
views
Rim hook decomposition and volume of moduli spaces
I did some computer experiments, counting the number of rim-hook decompositions (aka border-strip decompositions) of rectangles of shape $2n \times n$, where each strip has size $n$.
Here are 12 of ...
- 15.8k
24
votes
1
answer
615
views
Permutations, stopping times, Bessel functions, hook formula and Robinson-Schensted
For given counting number $n$, consider all permutations $\pi$ of {$1,\ldots,n$}, generate for every $\pi$ its Robinson-Schensted pair of standard tableaux $(P_\pi,Q_\pi)$ and average together all the ...
- 17.6k
24
votes
0
answers
760
views
How much of the plane is 4-colorable?
In 1981, Falconer proved that the measurable chromatic number of the plane is at least 5. That is, there are no measurable sets $A_1,A_2,A_3,A_4\subseteq\mathbb{R}^2$, each avoiding unit distances, ...
- 7,633
24
votes
0
answers
487
views
Is the Poset of Graphs Automorphism-free?
For $n\geq 5$, let $\mathcal {P}_n$ be the set of all isomorphism classes of graphs with n vertices. Give this set the poset structure given by $G \le H$ if and only if $G$ is a subgraph of $H$.
Is ...
23
votes
10
answers
5k
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) ...
- 777