# Tagged Questions

**30**

votes

**0**answers

1k views

### Fourier transform on the discrete cube

Notation: identify an element of $\{-1,1\}^n$ with the set $S \subseteq \{1, \ldots, n\}$ on which it takes the value $-1$.
The following is an asymptotic question. "Close to one" means "more than ...

**30**

votes

**0**answers

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

**28**

votes

**0**answers

800 views

### (Approximately) bijective proof of $\zeta(2)=\pi^2/6$ ?

Given $A,B\in {\Bbb Z}^2$, write $A \leftrightarrows B$ if the
interior of the line segment AB misses
${\Bbb Z}^2$.
For $r>0$, define
$S_r:=\{ \{A, B\} | A,B\in {\Bbb Z}^2,||A||<r,||B||<r, ...

**27**

votes

**0**answers

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

**26**

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$, ...

**25**

votes

**0**answers

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

**21**

votes

**0**answers

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

**20**

votes

**0**answers

1k views

### Permutations of $(Z/pZ)^*$

Let $p$ be a prime integer, and let $(\mathbb Z/p\mathbb Z)^*$ be the set of non-zero elements of $\mathbb Z/p \mathbb Z$.
Denote by $S((\mathbb Z/p \mathbb Z)^*)$ the group of permutations of ...

**19**

votes

**0**answers

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

**19**

votes

**0**answers

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

**18**

votes

**0**answers

824 views

### Red-blue alternating paths

Suppose we have two simple graphs on the same vertex set. We will call one of them red, the other blue. Suppose that for $i=1,..,k$ we have $deg (v_i)\ge i$ in both graphs, where ...

**17**

votes

**0**answers

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

**17**

votes

**0**answers

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

**0**answers

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

**16**

votes

**0**answers

146 views

### A small unavoidable collection of subgraphs

What is the smallest number S(k,n) of unlabeled graphs on k vertices such that every simple graph on n vertices contains at least one of these as an induced subgraph?
I'd like to avoid exhaustive ...

**16**

votes

**0**answers

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

**16**

votes

**0**answers

457 views

### Monomer-Dimer tatami tilings need better relationships with other math. Summary of results.

A monomer-dimer tiling of a rectangular grid with $r$ rows and $c$ columns satisfies the \emph{tatami} condition if no four tiles meet at any point. (or you can think of it as the removal of a ...

**15**

votes

**0**answers

307 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

**0**answers

216 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$.
...

**15**

votes

**0**answers

328 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)
...

**15**

votes

**0**answers

332 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

**0**answers

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

**15**

votes

**0**answers

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

**15**

votes

**0**answers

965 views

### How big is the sum of smallest multinomial coefficients?

Given positive integers $n$ and $d$, let $S$ indicate the list of all $d$-tuples of non-negative integers $(c_1,\ldots,c_d)$ such that $c_1+\cdots+c_d=n$. Let $v_i$ be the value of the multinomial ...

**15**

votes

**0**answers

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

**0**answers

744 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

**0**answers

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

**14**

votes

**0**answers

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

**14**

votes

**0**answers

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

**13**

votes

**0**answers

427 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, ...

**13**

votes

**0**answers

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

**13**

votes

**0**answers

494 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

**0**answers

825 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?

**13**

votes

**0**answers

504 views

### A bijection between sets of Young tableaux of two kinds

Assuming that the problem of exhibiting a bijection is not considerd a frivolous pursuit, allow me to ask a question troubling me for some time now.
Let $\lambda \vdash n$ denote the fact that ...

**13**

votes

**0**answers

462 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

**0**answers

1k 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?

**12**

votes

**0**answers

127 views

### realization spaces of 3-dimensional polytopes

It is a well-know result (Steinitz, 1922) that the realization space of 3-dimensional convex polytopes with fixed combinatorics is contractible.
A proof of this theorem can be found for instance in ...

**12**

votes

**0**answers

498 views

### Random Walk on $\mathbb{R}$ with Uniformly Distributed Steps and “Reflective” Boundary at Origin

A particle lies on the real number line at the origin. For each step taken, the particle moves from its current position a distance (and direction) chosen equi-probably from range $[-1,r]$. However, ...

**12**

votes

**0**answers

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

**12**

votes

**0**answers

242 views

### Are the zeros of Tutte polynomials dense in $\mathbb C^2$?

For the chromatic polynomials of graphs we have two nice theorems which describe the behavior of their zeros: Thomassen proved that the set of real zeros of all chromatic polynomials is the union of ...

**12**

votes

**0**answers

305 views

### Best known constant for parallel sorting

I recently found myself talking about Szemerédi's mathematics, and briefly discussed his famous sorting network, discovered with Ajtai and Komlós. Apparently their algorithm is not practical because ...

**12**

votes

**0**answers

378 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$ ...

**12**

votes

**0**answers

637 views

### Sums of Partitions and Stirling's formula

Stirling's formula $$N! \sim \sqrt{2 \pi}\ N^{N+ \frac{1}{2}} e^{-N}$$ follows easily from Laplace's method in light of the famous integral representation $$N! = \int_0^{\infty} e^{-z} z^N dz.$$ ...

**12**

votes

**0**answers

860 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$ ...

**12**

votes

**0**answers

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

**12**

votes

**0**answers

421 views

### A commutative monoid associated with a finite abelian group

Let $M$ be a finite abelian group, and denote by $e_m$, for $m \in M$, the canonical basis of $\mathbb{Z}^M$. For $m, n \in M$ define elements $v_{m,n} \in \mathbb{Z}^M/\langle e_0\rangle$ as
$$
...

**12**

votes

**0**answers

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

**11**

votes

**0**answers

296 views

### Splay trees and Thompson's group $F$

( I apologize for only indicating some easy to find references, but new users are not allowed to link more than five). This is very speculative, but:
Question: Is there a reformulation of the Dynamic ...

**11**

votes

**0**answers

395 views

### Possible orders of products of 2 involutions which interchange disjoint residue classes of the integers

Definition / Question
Definition: Let $r(m)$ denote the residue class $r+m\mathbb{Z}$, where
$0 \leq r < m$.
Given disjoint residue classes $r_1(m_1)$ and $r_2(m_2)$, let the class transposition
...

**11**

votes

**0**answers

331 views

### Drawings of complete graphs with $Z(n)$ crossings

Hill conjectured that the minimum number of crossings in a drawing of the complete graph $K_n$ in the plane is exactly
$$Z(n) = \frac{1}{4} \bigg\lfloor\frac{n}{2}\bigg\rfloor ...