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)

42
votes
0answers
1k views

Intersecting Family of Triangulations

Let $\cal T_n$ be the family of all triangulations on an $n$-gon using $(n-3)$ non-intersecting diagonals. The number of triangulations in $\cal T_n$ is $C_{n-2}$ the $(n-2)$th Catalan number. Let ...
36
votes
0answers
649 views

Which region in the plane with a given area has the most domino tilings?

I just finished teaching a class in combinatorics in which I included a fairly easy upper bound on the number of domino tilings of a region in the plane as a function of its area. So this led to ...
32
votes
0answers
1k 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 ...
30
votes
0answers
1k views

Curious $q$-analogues

Consider the Fibonacci polynomials $$F_n (x) = \sum_{j = 0}^{\left\lfloor {n/2} \right\rfloor }\binom{n-j}{j} x^{n - 2j} $$ and the Lucas polynomials $$L_n (x) = \sum_{j = 0}^{\left\lfloor {n/2} ...
29
votes
0answers
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$, ...
28
votes
0answers
686 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 = ...
23
votes
0answers
966 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 ...
22
votes
0answers
453 views

probability of zero subset sum

Almost 17 years ago, I asked the following question on USENET, motivated by a method in numerology (I kid you not). Pick integers $n \ge 2$, $k \ge 1$. Toss $n$ $k$-sided dice. The sides of each die ...
22
votes
0answers
731 views

tiling a rectangle with the smallest number of squares

This is based on another thread. For $m,n\in \mathbb N$, let $f(m,n)$ be the minimum number of squares with integer sides needed to tile a $m\times n$ rectangle. Recently, a table of values for $n\le ...
20
votes
0answers
315 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 ...
20
votes
0answers
555 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 ...
20
votes
0answers
581 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 ...
20
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
0answers
307 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 ...
19
votes
0answers
564 views

Time for Langton's ant to cover a “square” torus

Langton's ant is a cellular automaton running as follows: Squares on a plane are colored variously either black or white. We arbitrarily identify one square as the "ant". The ant can travel ...
19
votes
0answers
298 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$. ...
18
votes
0answers
571 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 ...
18
votes
0answers
485 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 ...
18
votes
0answers
259 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 ...
18
votes
0answers
1k 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 ...
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 ...
17
votes
0answers
372 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 ...
17
votes
0answers
886 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 ...
17
votes
0answers
381 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) ...
17
votes
0answers
1k 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?
16
votes
0answers
265 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 ...
16
votes
0answers
262 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 ...
16
votes
0answers
540 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 ...
15
votes
0answers
436 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$ ...
15
votes
0answers
311 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 ...
15
votes
0answers
1k views

Covers of $Z^k$

This is a question related to covers of $Z^\infty$. Is it possible to cover $Z^k$, $k>1$, with the $l_1$-metric by a constant (not depending on $k$) number of collections of subsets $U^0,...,U^c$ ...
15
votes
0answers
855 views

Is every k-edge-connected graph also k-trail-ordered?

This is an old question of Aradhana Narula-Tam and Philip Lin that I think deserves wider circulation. It appeared in Discrete Math. 257 (2002), page 613, but not many people have looked at it and it ...
15
votes
0answers
783 views

Optimal Monotone Families for the Discrete Isoperimetric Inequality

Background: the Discrete Isoperimetric Inequality Start with a set X={1,2,...,n} of n elements and the family $2^X$ of all subsets of X. For a real number p between zero and one, we consider a ...
14
votes
0answers
282 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$ ...
14
votes
0answers
457 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 ...
14
votes
0answers
574 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, ...
14
votes
0answers
304 views

Monotone embedding of complete binary tree in hypercube

Embedding different graphs, especially binary trees, in the hypercube has a huge literature. However, I could not find anything if we restrict the embedding to be monotone. So I would like to ...
14
votes
0answers
643 views

A Conjecture About Directed Graphs that are the Union of Two Trees

Let D=(V,E) be a directed graph that is the union of two edge-disjoint directed spanning trees. Suppose that There no subset X of vertices so that there is precisely one directed edge from X ...
13
votes
0answers
303 views

Grothendieck on polyhedra over finite fields

In Grothendieck's Sketch of a Programme he spends a few pages discussing polyhedra over arbitrary rings and concludes with some intriguing remarks on specializing polyhedra over their "most singular ...
13
votes
0answers
424 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$ ...
13
votes
0answers
506 views

$\epsilon$-nets with respect to the cut norm

The cut norm $||A||\_C$ of a real matrix $A = (a_{i,j}) \in \mathcal{R}^{n\times n}$ is the maximum over all $I \subseteq [n], J \subseteq [n]$ of the quantity $\left|\sum_{i \in I, j \in ...
13
votes
0answers
2k views

Minimum tiling of a rectangle by squares

Given the $n\times m$ rectangle, I want to compute the minimum number of integer-sided squares needed to tile it (possibly of different sizes). Is there an efficient way to calculate this?
13
votes
0answers
359 views

How much must deleting a spanning tree reduce edge-connectivity?

Suppose you have a 100-edge connected graph (e.g. an infrastructure network). You want to delete the edges of a spanning tree, any spanning tree you choose (e.g. to sell a connected subnetwork). What ...
13
votes
0answers
691 views

Polynomials with presumably positive coefficients

After seeing that some positivity problems get their solutions on MO, I am quite enthusiastic of posing my (and not only) problem of positive flavour. In order to state it, I have to introduce the ...
13
votes
0answers
446 views

Where do stable Kronecker coefficients live “in nature”?

Background: For a partition $\lambda$, let $\lambda[N] = (N - |\lambda|, \lambda_1, \lambda_2, \lambda_3, \dots)$, also let $\chi_\lambda$ be the corresponding irreducible character of the symmetric ...
12
votes
0answers
176 views

How does a permutation $P$ affect the singular value $\sigma_{\text{max}}(Q^\top P^\top Q)$ for orthogonal $Q$?

Let $q_i$ for $i=1,\ldots,m$ be the columns of the matrix $Q\in\mathbb{R}^{n\times m}$, $n\geq 2m$, which are pairwise orthonormal ( i.e. $q_i^\top q_j = \begin{cases} 1 & \text{if}\quad i=j \\ 0 ...
12
votes
0answers
140 views

Coefficients of universal Schubert polynomials

Let $e_i^j$ be the elementary symmetric polynomial in $x_1,x_2,\ldots,x_j$. Then the ordinary Schubert polynomial has an expansion of the form ...
12
votes
0answers
159 views

Do the Laver tables converge to the Sierpinski triangle with a line segment sticking out in the hyperspace topology?

Let $(\{1,...,2^{n}\},*_{n})$ denote the $n$-th Laver table. Let $$C_{n}=\{(\frac{x}{2^{n}},\frac{x*_{n}y}{2^{n}})|x,y\in\{1,2,3,...,2^{n}\}\}$$ for all $n\in\mathbb{N}$. Then since $C_{n}$ is a ...
12
votes
0answers
326 views

Word complexity of primes mod 4

For an infinite binary word $w$, the word complexity $f_w(n)$ is defined as the number of different subwords of length $n$. The asymptotic behavior of this function is an important parameter of the ...
12
votes
0answers
174 views

Polytopes with few vertices and few facets

I recently realized that, for fixed $\alpha$ and $\beta$, the number of (combinatorial types of) $d$-polytopes with $\leq d+1+\alpha$ vertices and $\leq d+1+\beta$ facets is bounded by a constant that ...