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

1,814 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
3k views

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$, ...
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 ...
756 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 ...
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 ...
725 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 ...
681 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 ...
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 ...
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 ...
605 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, ...
454 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 ...
1k views

### What is the best lower bound for 3-sunflowers?

A collection of $t$ sets $A_i$ is called a t-sunflower if $A_i \cap A_j = Z$ for all $i \neq j$ for some fixed $Z$. A well-known conjecture of Erdos and Rado says that there is a constant $C_t$ such ...
730 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 ...
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 ...
433 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 ...
410 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 ...
488 views

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]!=\dots[m], \qquad m\in\mathbb Z_{>0}.$$ Consider the following trigonometric numbers:...
570 views

### To find a longer path with fixed endvertices in a graph satisfies the following property

Suppose that $G=(V,E)$ is a simple graph and $P=(V_1,E_1)$ is a path in $G$ where $$V_1=\{v_0,v_1,\cdots,v_n\},\ E_1=\{v_0v_1,v_1v_2,\cdots,v_{n-1}v_n\}.$$ I found that if the path $P$ satisfies: ...
344 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, ...
306 views

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$ ...
848 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 ...
584 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 ...
476 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$...
414 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 ...
612 views

### Probability of many overlapping zero inner products on a circle

[Question edited and changed a little on June 14 2015] Consider an $n$-dimensional vector $v$ with $v_i \in \{-1,1\}$. Now consider an $n$-dimensional vector $w$ with $w_i \in \{-1,0,1\}$. The ...
746 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, ...
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 ...