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.

3,009 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
55 votes
1 answer
3k 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 ...
Sebastien Palcoux's user avatar
51 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 ...
Andrew D. King's user avatar
45 votes
0 answers
3k views

A = B (but not quite); 3-d arrays with multiple recurrences

Many years ago, I discovered the remarkable array (apparently originally discovered by Ramanujan) 1 1 3 2 10 15 6 40 105 105 24 196 700 1260 945 ...
Peter Shor's user avatar
  • 6,272
40 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 ...
Tim Campion's user avatar
  • 60.6k
36 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,...
Igor Pak's user avatar
  • 16.3k
35 votes
0 answers
905 views

Orthogonal vectors with entries from $\{-1,0,1\}$

Let $\mathbf{1}$ be the all-ones vector, and suppose $\mathbf{1}, \mathbf{v_1}, \mathbf{v_2}, \ldots, \mathbf{v_{n-1}} \in \{-1,0,1\}^n$ are mutually orthogonal non-zero vectors. Does it follow that $...
Nathaniel Johnston's user avatar
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 ...
Alessandro Della Corte's user avatar
32 votes
0 answers
3k 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. ...
Mario Krenn's user avatar
32 votes
0 answers
1k 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 ...
Dongryul Kim's user avatar
  • 1,429
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$, ...
Gil Kalai's user avatar
  • 24.2k
29 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 ...
T. Amdeberhan's user avatar
29 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 ...
27 votes
0 answers
876 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 ...
Danny Neftin's user avatar
26 votes
0 answers
899 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 ...
Louis Deaett's user avatar
  • 1,513
25 votes
0 answers
540 views

A conjecture about inclusion–exclusion

$\newcommand\calF{\mathcal{F}} \def\cupdot {\stackrel{\bullet}{\cup}} \def\minusdot {\stackrel{\bullet}{\setminus}}$This post presents a conjecture that we have with some colleagues. It is about ...
M.Monet's user avatar
  • 351
24 votes
0 answers
744 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, ...
Dustin G. Mixon's user avatar
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 ...
Mingzhi Xuan's user avatar
23 votes
0 answers
482 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 ...
Wade Hann-Caruthers's user avatar
22 votes
0 answers
539 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 ...
Gordon Royle's user avatar
  • 12.3k
22 votes
0 answers
800 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 ...
Alex R.'s user avatar
  • 4,902
21 votes
0 answers
425 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, ...
Lviv Scottish Book's user avatar
21 votes
0 answers
572 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 ...
Timothy Chow's user avatar
  • 78.1k
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 ...
Gil Kalai's user avatar
  • 24.2k
21 votes
0 answers
896 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 \...
Suvrit's user avatar
  • 28.4k
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?
Vidit Nanda's user avatar
  • 15.4k
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:...
Wadim Zudilin's user avatar
20 votes
1 answer
1k 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 ...
Per Alexandersson's user avatar
20 votes
0 answers
553 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) ...
Allen Knutson's user avatar
19 votes
0 answers
544 views

Large values of characters of the symmetric group

For $g$ an element of a group and $\chi$ an irreducible character, there are two easy bounds for the character value $\chi(g)$: First, the bound $|\chi(g)|\leq \chi(1)$ by the dimension of the ...
Will Sawin's user avatar
  • 135k
19 votes
0 answers
606 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 ...
Myshkin's user avatar
  • 17.4k
19 votes
0 answers
765 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 $...
Dmitry V's user avatar
  • 433
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$ ...
user avatar
18 votes
0 answers
562 views

What is the geometric intuition behind Wilf-Zeilberger theory?

This problem is somehow inspired by a bunch of impressive posts of combinatorial identities by T. Amdeberhan. Earlier this month I learnt from computer scientists that they have a generic algorithmic ...
Henry.L's user avatar
  • 7,951
18 votes
0 answers
421 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$ ...
Richard Stanley's user avatar
18 votes
0 answers
375 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_\...
Allen Knutson's user avatar
17 votes
0 answers
343 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$, ...
Sam Hopkins's user avatar
  • 22.7k
17 votes
0 answers
481 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 ...
catlyn's user avatar
  • 171
17 votes
0 answers
568 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 ...
Libli's user avatar
  • 7,210
17 votes
0 answers
1k 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 ...
domotorp's user avatar
  • 18.3k
17 votes
0 answers
830 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 ...
Tomasz Kania's user avatar
  • 11.3k
17 votes
0 answers
971 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 ...
Mare's user avatar
  • 25.8k
17 votes
0 answers
530 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$...
user avatar
17 votes
0 answers
430 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 ...
მამუკა ჯიბლაძე's user avatar
17 votes
0 answers
812 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, ...
Nick Gill's user avatar
  • 11.2k
17 votes
0 answers
417 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}+...
Wolfgang's user avatar
  • 13.2k
17 votes
0 answers
498 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 ...
Brendan McKay's user avatar
17 votes
0 answers
827 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 ...
Sam Hopkins's user avatar
  • 22.7k
17 votes
0 answers
903 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$; $\...
Jeffrey Adams's user avatar
16 votes
0 answers
545 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 ...
Marcel's user avatar
  • 2,510
16 votes
0 answers
360 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 ...
Per Alexandersson's user avatar

1
2 3 4 5
61