Questions tagged [co.combinatorics]
Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.
2,483
questions with no upvoted or accepted answers
50
votes
0
answers
2k
views
On the first sequence without triple in arithmetic progression
In this Numberphile video (from 3:36 to 7:41), Neil Sloane explains an amazing sequence:
It is the lexicographically first among the sequences of positive integers without triple in arithmetic ...
- 23.1k
47
votes
0
answers
2k
views
Does every triangle-free graph with maximum degree at most 6 have a 5-colouring?
A very specific case of Reed's Conjecture
Reed's $\omega$,$\Delta$, $\chi$ conjecture proposes that every graph has $\chi \leq \lceil \tfrac 12(\Delta+1+\omega)\rceil$. Here $\chi$ is the chromatic ...
- 1,754
38
votes
0
answers
1k
views
Is there anything to the obvious analogy between Joyal's combinatorial species and Goodwillie calculus?
Combinatorial species and calculus of functors both take the viewpoint that many interesting functors can be expanded in a kind of Taylor series. Many operations familiar from actual calculus can be ...
- 49.6k
35
votes
0
answers
1k
views
3-colorings of the unit distance graph of $\Bbb R^3$
Let $\Gamma$ be the unit distance graph of $\Bbb R^3$: points $(x,y)$ form an edge if $|x,y|=1$.
Let $(A,B,C,D)$ be a unit side rhombus in the plane, with a transcendental diagonal, e.g. $A = (\alpha,...
- 15.3k
32
votes
0
answers
2k
views
The easily bored sequence
If we want to compare the repetitiveness of two finite words, it looks reasonable, first of all, to consider more repetitive the word repeating more times one of its factors, and secondarily to ...
- 3,227
32
votes
0
answers
2k
views
Vertex coloring inherited from perfect matchings (motivated by quantum physics)
Added (19.01.2021): Dustin Mixon wrote a blog post about the question where he reformulated and generalized the question.
Added (25.12.2020): I made a youtube video to explain the question in detail.
...
- 575
32
votes
0
answers
2k
views
A Combinatorial Abstraction for The "Polynomial Hirsch Conjecture"
Consider $t$ disjoint families of subsets of {1,2,…,n}, ${\cal F}_1,{\cal F_2},\dots {\cal F_t}$ .
Suppose that
(*)
For every $i \lt j \lt k$
and every $R \in {\cal F}_i$, and $T \in {\cal F}_k$,
...
- 23.5k
31
votes
0
answers
1k
views
How to prove the identity $L(2,(\frac{\cdot}3))=\frac2{15}\sum\limits_{k=1}^\infty\frac{48^k}{k(2k-1)\binom{4k}{2k}\binom{2k}k}$?
For the Dirichlet character $\chi(a)=(\frac a3)$ (which is the Legendre symbol), we have
$$L(2,\chi)=\sum_{n=1}^\infty\frac{(\frac n3)}{n^2}=0.781302412896486296867187429624\ldots.$$
Note that this ...
- 13k
29
votes
0
answers
982
views
Minimal number of intersections in a convex $n$-gon?
For a convex polygon $P$, draw all the diagonals of $P$ and consider the intersection points made by those diagonals. Let $f(n)$ be the minimal number of such intersections where $P$ ranges over all ...
- 1,399
28
votes
0
answers
1k
views
Linking formulas by Euler, Pólya, Nekrasov-Okounkov
Consider the formal product
$$F(t,x,z):=\prod_{j=0}^{\infty}(1-tx^j)^{z-1}.$$
(a) If $z=2$ then on the one hand we get Euler's
$$F(t,x,2)=\sum_{n\geq0}\frac{(-1)^nx^{\binom{n}2}}{(x;x)_n}t^n,$$
on the ...
- 38.3k
27
votes
0
answers
380
views
Does any set of dominoes tile some common figure?
Let $D_1,\dots,D_n \subset \mathbb{Z}^2$ be two-point sets, i.e. 'dominoes' (unlike common dominoes, these are not necessarily connected, but I couldn't come up with a better name).
Does there always ...
- 602
25
votes
0
answers
840
views
A question on simultaneous conjugation of permutations
Given $a,b\in S_n$ such that their commutator has at least $n-4$ fixed points, is there an element $z\in S_n$ such that $a^z=a^{-1}$, and $b^z=b^{-1}$? Here $a^z:=z^{-1}az$.
Magma says that the ...
- 251
25
votes
0
answers
839
views
Which sets of roots of unity give a polynomial with nonnegative coefficients?
The question in brief: When does a subset $S$ of the complex $n$th roots of unity have the property that
$$\prod_{\alpha\, \in \,S} (z-\alpha)$$
gives a polynomial in $\mathbb R[z]$ with ...
- 1,493
25
votes
0
answers
3k
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 ...
24
votes
0
answers
701
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,243
24
votes
0
answers
1k
views
Do all possible trees arise as orbit trees of some permutation groups?
I.Motivation from descriptive set theory
(Contains some quotes from Maciej Malicki's paper.)
The classical theorem of Birkhoff-Kakutani implies that every metrizable topological group G admits a ...
- 191
23
votes
0
answers
462
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 ...
22
votes
0
answers
516
views
Zero curves of Tutte Polynomials?
There is an extensive theory of the real and complex roots of the chromatic polynomial of a graph, a substantial fraction of this being due to the connections between the chromatic polynomial and a ...
- 10.8k
22
votes
0
answers
781
views
Combinatorics of Quantum Schubert Polynomials
Let $S_n$ be the symmetric group. Let $s_i$ denote the adjacent transposition $(i \ i+1)$. For any permutation $w\in S_n$, an expression $w=s_{i_1}s_{i_2}\cdots s_{i_p}$ of minimal possible length is ...
- 4,812
21
votes
0
answers
523
views
Coloring a Ferrers diagram
I've shopped the problem below around a bit and it seems like it might be known, or not that hard to resolve, but so far I've come up empty-handed.
Say that a coloring of the dots of a Ferrers ...
- 64.9k
21
votes
0
answers
2k
views
The Fourier Transform of taking Eigenvalues
The purpose of this question is to ask about the Fourier transform of the map which associate to an $n$ by $n$ matrix its $n$ eigenvalues, or some function of the $n$ eigenvalues. The main motivation ...
- 23.5k
21
votes
0
answers
864
views
Cauchy matrices with elementary symmetric polynomials
$\newcommand{\vx}{\mathbf{x}}$
Let $e_k(\vx)$ denote the elementary symmetric polynomial, defined for $k=0,1,\ldots,n$ over a vector $\vx=(x_1,\ldots,x_n)$ by
\begin{equation*}
e_k(\vx) := \sum_{1 \...
- 27.8k
21
votes
0
answers
3k
views
Origins of the Nerve Theorem
Recently, I've read two papers which have cited the Nerve Theorem, one crediting Borsuk with the result and another Leray. Here is the question:
Who was the first to prove the Nerve Theorem?
- 14.7k
21
votes
0
answers
2k
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 numbers:...
- 13.2k
20
votes
0
answers
393
views
Straight-line drawing of regular polyhedra
Find the minimum number of straight lines needed to cover a crossing-free straight-line drawing of the icosahedron $(13\dots 15)$ and of the dodecahedron $(9\dots 10)$ (in the plane).
For example, ...
- 4,013
20
votes
0
answers
529
views
Hall's Marriage Theorem and intervals
In Hall's Marriage Theorem, we have a set $B$ of brides and $G$ of
grooms, where each bride $b$ has an acceptable set $A_b \subseteq G$
of grooms. A matching $m:B\to G$ is an injection such that $m(b)
...
- 26.8k
19
votes
0
answers
534
views
Simpler proofs of certain Ramsey numbers
The reason for the gorgeous simplicity of the classic proofs of $R(3,3)$, $R(4,4)$, $R(3,4)$ and $R(3,5)$ is that essentially all you need is the trivial bound and a picture.
But for bigger Ramsey ...
- 17k
19
votes
0
answers
738
views
A Linear Order from AP Calculus
In teaching my calculus students about limits and function domination, we ran into the class of functions
$$\Theta=\{x^\alpha (\ln{x})^\beta\}_{(\alpha,\beta)\in\mathbb{R}^2}$$
Suppose we say that $...
- 423
19
votes
0
answers
1k
views
coloring ${\mathbb Z}^k$
This question is related to but seems to be simpler than this one, so perhaps somebody can solve it.
Question. Is there $k\ge 1$ and a coloring of vertices of the lattice ${\mathbb Z}^k$ in $k$ ...
user6976
18
votes
0
answers
399
views
An algebraic strengthening of the Saturation Conjecture
The Saturation Conjecture (proved by Knutson-Tao) asserts that
$c_{n\mu,n\nu}^{n\lambda}\neq 0\Rightarrow c_{\mu,\nu}^{\lambda} \neq
0$, where $c$ denotes a Littlewood-Richardson coefficient and $n$ ...
- 43.8k
18
votes
0
answers
341
views
Deforming a basis of a polynomial ring
The ring $Symm$ of symmetric functions in infinitely many variables is well-known to be a polynomial ring in the elementary symmetric functions, and has a $\mathbb Z$-basis of Schur functions $\{S_\...
- 26.8k
17
votes
0
answers
440
views
Does the Ackermann function count something?
Let $\mathrm{FinSet}$ be the category of finite sets.
A finite set structure is a faithful functor $F\colon C\to \mathrm{FinSet}$ such that, for any $n\geq 1$, there are only finitely many isomorphism ...
- 171
17
votes
0
answers
501
views
Finite version special case Jacobi triple product formula
In this paper, Shanks uses the following formula:
$$ \sum_{s=0}^{n-1}q^{s(2n+1)} \times \left( \prod_{k=s+1}^{n} \dfrac{1-q^{2k}}{1-q^{2k-1}}\right) = \sum_{s=1}^{2n} q^{\frac{s(s-1)}{2}}$$
to get a ...
- 6,183
17
votes
0
answers
989
views
Almost monochromatic point sets
There are many sort of equivalent theorems about monochromatic configurations in finite colorings, such as Van der Waerden, Hales-Jewett or Gallai's theorem, the latter of which states that in a ...
- 17.2k
17
votes
0
answers
731
views
Ramsey's theorem for the first uncountable ordinal
Sierpiński proved that a version of Ramsey's theorem for colourings of pairs of countable ordinals fails miserably by comparing the ordering of $\omega_1$ with the linear ordering of (a subset of) the ...
- 10.9k
17
votes
0
answers
517
views
Question about combinatorics on words
Let $\{a_1,a_2,...,a_n\}$ be an alphabet and let $\{u_1,...,u_n\}$ be words in this alphabet, and $a_i\mapsto u_i$ be a substitution $\phi$.
Question: Is there an algorithm to check if for some $m,k$...
user6976
17
votes
0
answers
424
views
Need explicit formula for certain "$q$-numbers" involving gcd's
The question is motivated by yet another possible approach to a combinatorial problem formulated previously in "Special" meanders. I'm not giving details of the connection as I believe the ...
- 16.2k
17
votes
0
answers
787
views
What's the big deal about $M_{13}$?
$M_{13}$ is the Mathieu groupoid defined by Conway in
Conway, J. H. $M_{13}$. Surveys in combinatorics, 1997 (London), 1–11,
London Math. Soc. Lecture Note Ser., 241, Cambridge Univ. Press, ...
- 10.8k
17
votes
0
answers
478
views
Maximum automorphism group for a 3-connected cubic graph
The following arose as a side issue in a project on graph reconstruction.
Problem: Let $a(n)$ be the greatest order of the automorphism group of a 3-connected cubic graph with $n$ vertices. Find a ...
- 34k
17
votes
0
answers
750
views
Is there a n/2 version of the Erdős-Hanani conjecture?
This question comes out of REU research from this past summer. Unfortunately weeks of thought led to only trivial observations and the conclusion that the problem is quite hard.
Fix $k,t$. Let $F$ be ...
- 18.9k
17
votes
0
answers
875
views
Combinatorial identity involving the Coxeter numbers of root systems
The setup is:
$R$ = irreducible (reduced) root system;
$D$ = connected Dynkin diagram of $R$, with nodes numbered $1,2,...,r$;
$\hat D$ = extended Dynkin diagram, nodes numbered $0,1,2,...,r$;
$\...
- 2,369
16
votes
0
answers
302
views
Row of the character table of symmetric group with most negative entries
The row of the character table of $S_n$ corresponding to the trivial representation has all entries positive, and by orthogonality clearly it is the only one like this.
Is it true that for $n\gg 0$, ...
- 18.9k
16
votes
0
answers
497
views
Identity involving Schur polynomials, binomial coefficients and contents of partition
Let $C_{\lambda,\mu}$ be the coefficients defined as
$$ s_\lambda\left(\frac{x_1}{1-x_1},...,\frac{x_N}{1-x_N}\right)=\sum_{\mu\supset \lambda}C_{\lambda\mu}s_\mu(x_1,...,x_N),$$
where $s$ are the ...
- 2,400
16
votes
1
answer
711
views
Tiling rectangle with trominoes - an invariant
There are two types of trominoes, straight shapes and L-shaped. Suppose a rectangle $R$ admits at least one tiling using trominoes, with an even number of L-trominoes.
EDIT: we do not admit ALL ...
- 14.5k
16
votes
0
answers
350
views
Combinatorial characterization of intersecting intervals in the plane
Consider $n$ points $A=\{A_1,\dotsc,A_n\}$, and another set of points, $B=\{B_1,\dotsc,B_n\}$ in the plane. We can assume they are all disjoint.
For each permutation $\pi$, consider the collection of ...
- 14.5k
16
votes
0
answers
954
views
What to do with results you found but cannot prove(outside your research area)?
Not sure if MathOverflow is still a place to discuss such things, but I'll give it a try. Tell me an alternative site, in case it is wrong here. I translated a representation-theory/combinatorial ...
- 22.2k
16
votes
0
answers
403
views
Do the coefficients of these irreducible polynomials always become periodic?
Fix $n\in\mathbb N$ and a starting polynomial (or seed) $p_n=a_0+a_1x+\dots+a_nx^n$ with $a_k\in\mathbb Z\ \forall k$ and $a_0a_n\ne0$.
Define $p_{n+1},p_{n+2},\dots$ recursively by $p_r = p_{r-1}+...
- 12.6k
16
votes
0
answers
443
views
A Product Related to Unrestricted Partitions
Start with the product for unrestricted partitions:
$(1+x+x^2+...)(1+x^2+x^4+...)(1+x^3+x^6+...)...$
Now replace some of the plus signs with minus signs and expand the product into a series. Is it ...
- 2,133
16
votes
0
answers
734
views
How to explain the picturesque patterns in François Brunault's matrix?
How to explain the patterns in the matrix defined in François Brunault's
answer to the question Freeness of a Z[x] module depicted below? --
Choosing colors according to the highest power of 2 which ...
- 18k
16
votes
0
answers
538
views
Catalan objects associated to a univariate polynomial
Given a monic degree $n$ polynomial $f(z)$ with no double roots, and a phase $0\leq \theta < \pi$, there are natural constructions which associate to this data:
a noncrossing matching on $2n$ ...
- 5,883