**0**

votes

**0**answers

32 views

### Schur polynomial, change of variable

Let $k=(k_1,k_2,k_3,k_4)\in \mathbb{N}^4$ and let $s_k(x_1,x_2,x_3,x_4)$ be the Schur polynomial on $GL_4$.
Question 1: If I replace $x_3$ with $x_1$ and $x_4$ with $x_2$, can $s_k(x_1,x_2,x_1,x_2)$ ...

**4**

votes

**1**answer

112 views

### $n$ groups of $n$ queens on a toroidal chessboard

An interesting question came up in the Puzzling Stack Exchange a few days ago about "queen-connected sets". When trying to solve this problem, I came across an arrangement of five colours of queens ...

**1**

vote

**1**answer

106 views

### limit and combinatorics

Given $x \in (0,\frac{1}{2})$ and $y \in (0,\frac{1}{2}]$, what is the value of the following limit:
$\lim_{n\rightarrow \infty}\sum_{k=0}^{n}{n \choose k}|x^{n-k}(1-x)^{k}-y^{n-k}(1-y)^{k}|?$
When ...

**8**

votes

**0**answers

95 views

### Reduction formula for Schubert polynomials

In my endless fiddling with formulas I discovered one that fills in the blanks in a generic formula I saw in a paper, but I'm wondering if maybe it's already known and the paper was just mentioning ...

**4**

votes

**0**answers

55 views

### Is there a decomposition strengthening of the Sauer-Shelah Lemma?

Let $S \subset \{-1,1\}^n$. For a subset $A \subset [n]$ let $P_A$ denote the coordinate projection operator on S; in other words let $P_A(S)$ be the coordinate projection of $S$ onto the coordinates ...

**7**

votes

**1**answer

83 views

### Weighted Permutation Sum

I am trying to find out a closed-form formula (or a generating function at least) for the number of permutations $\sigma$ that satisfy $$ S = \sum_{i = 1}^{n} i\sigma(i)$$ for a given value of $S$. We ...

**6**

votes

**0**answers

54 views

### Ideals in strong Bruhat order

Recall that a (lower) ideal in a poset $(P, \le)$ is a subset $I\subset P$ such that $x\in I \Rightarrow y\in I$ for all $y\le x$. In am interested in ideals in finite Coxeter groups $W$ equipped ...

**12**

votes

**1**answer

174 views

### separating points in $\mathbb{R}^d$ by minimal number of planes

Given $n$ points of general position in $\mathbb{R}^d$ (say, $n>d$ and no $d+1$ lie in a hyperplane.) We want to draw $k$ hyperplanes not passing through those points so that they all are in ...

**11**

votes

**1**answer

229 views

### Generating function of the Thue-Morse sequence

Let $T$ be the generating function of the Thue-Morse sequence; thus,
$T(x)=x+x^2+x^4+x^7+\dotsb$. It is known that $T$ satisfies the nice
congruence
$$ (1+x)^3 T^2(x) + (1+x)^2 T(x) + x \equiv 0 ...

**6**

votes

**1**answer

140 views

### Young-Fibonacci lattice and purely periodic continued fractions

The Fibonacci lattice $\mathcal{F}$ is the poset of all finite words consisting of 1's and 2's where a word $v$ covers a word $u$ if $v$ is obtained from $v$ by either (a) inserting a 1 in $u$ prior ...

**1**

vote

**0**answers

69 views

### Minimal Birthdays

In combinatorial game theory: The birthday of a game is defined recursively as 1 plus the maximal birthday of its options, with the zero game having birthday 0.
Suppose we define the quasi-birthday ...

**5**

votes

**1**answer

98 views

### An equivalent definition for the adiamond lattices

A lattice is called adiamond if it admits no sublattice equivalent to the diamond lattice $M_3$ below:
The top interval of a lattice is the interval between the meet of all the maximal elements and ...

**6**

votes

**1**answer

172 views

### Given k, what is the minimum n such that n choose n/2 is greater than k? [closed]

I'm not an expert in combinatorics, but it sometimes comes up in my research with students in computer science (which is already pretty far away from my speciality of abstract homotopy theory). I just ...

**7**

votes

**0**answers

103 views

### De Bruijn sequence inside De Bruijn sequence

A binary De Bruijn sequence of index $n$ is a circular sequence $S=a_1a_2\ldots a_{2^n}$, with $a_i∈\{0,1\}$, and such that each of the $2^n$ binary $n$-tuples occurs exactly once in $S$.
What is ...

**6**

votes

**0**answers

105 views

### Families of subsets with pairwise symmetric differences of cardinality at most $k$

Let $X$ be an $n$-element set and $\mathcal{F} \subseteq P(X)$ such that for all $A, B \in \mathcal{F}$, $|A△B| \leq k$ where $A△B$ denotes the symmetric difference of $A$ and $B$. Suppose ...

**7**

votes

**1**answer

377 views

### Another formula for Bell numbers

Here is an observation (thanks to OEIS):
$$\sum_{i=0}^\infty \frac{i^k}{i!}= B_k e,$$ where $B_k$ is the $k$-th Bell number. I might be having reading comprehension issues, but I don't see this ...

**8**

votes

**1**answer

264 views

### Embedding Z into Z^2 with large distortion

Is it possible to find a 2-way infinite (self-avoiding) path $\{x_i\}_{i\in \mathbb Z}$ in the standard Cayley graph of $\mathbb Z^2$, i.e. the square grid, such that the distance between $x_i$ and ...

**5**

votes

**1**answer

124 views

### How can I prove that these two graph coloring problems are polynomial time equivalent?

Given a graph $G(V,E)$. The standard $k$-coloring problem consists in finding a feasible coloring (no two adjacent nodes share the same color) of the nodes with $k$ colors. Let this problem be $P_1$.
...

**3**

votes

**0**answers

96 views

### Synonyms for “labeling” of a graph

In Preprint 1 we write numerical labels 0 or 1 at each vertex of a Dynkin diagram $D$. We call it a labeling of the graph (Dynkin diagram) $D$.
In Preprint 2 we consider an extended (affine) Dynkin ...

**3**

votes

**0**answers

54 views

### The degree/diameter problem for even girth graphs starting with upper bound

I posted this on stackexchange but due to a lack of response there I am posting here.
Let $G$ be a graph with girth $g$, minimal degree $\delta$, maximal degree $\Delta$, and diameter $D$. Define ...

**3**

votes

**1**answer

72 views

### Construction of planar embedding

I'm reading the following paper on universality considerations in VLSI circuits
http://www.computer.org/csdl/trans/tc/1981/02/06312176.pdf
In Theorem 2 On the second page it states there exists ...

**21**

votes

**3**answers

776 views

### On determinants formed by binomial coefficients

Let $q$ be a number. Let us consider the $q^2-1$-th line of the Pascal triangle (i.e. numbers ${{q^2-1} \choose i}$, $i=0,1,...q^2-1$). We have $q^2$ numbers.
Let us form naively a $q \times q$ ...

**7**

votes

**3**answers

197 views

### Embedding planar graphs into the grid

I've seen the following lemma in a paper. The result is by Valiant.
A planar graph $G$ with maximum degree $4$ can be embedded in the plane using $O(|V|)$ area in such a way that its vertices are at ...

**2**

votes

**0**answers

104 views

### How hard is recognizing a permutation that is a square for the shift product?

This is a continuation of my attempts to generate simple combinatorial computational problems that turn out to be computationally hard (NP-complete). In this pursuit, I came up with a permutation ...

**20**

votes

**1**answer

373 views

### Why does McMahon formula look like the inclusion-exclusion principle?

The McMahon formula for the number of tilings of an $a \times b \times c$ hexagon by lozenges:
$$ \Big[H(a)H(b)H(c)\Big] \Big[H(a+b)H(b+c)H(c+a)\Big]^{-1} \Big[H(a+b+c)\Big]$$
looks oddly like the ...

**6**

votes

**1**answer

116 views

### Refinement of Dirac's theorem on Hamiltonian graphs

Dirac's theorem states that if degree of each vertex of a graph $G=(V,E)$ is not less than $|V|/2$, then it has Hamiltonian cycle. It is less known, but still known and not so hard to prove (though I ...

**1**

vote

**1**answer

71 views

### Given Sequence of Numbers find number of combinations [closed]

I have the sequence of numbers $1,2,4,8,16,\ldots$. This is an infinite sequence. So my problem is that if I have any positive integer value, $x$, what are the possible ways that I can write $x$ as ...

**4**

votes

**1**answer

150 views

### Integers in Boxes Problem

Given positive integers $k$, $m$, $n$, with $m,n >> k$, suppose we have
$n$ boxes each containing $k$ randomly (uniformly) selected positive integers $x$ satisfying $1 \leq x \leq m$ (duplicates ...

**1**

vote

**0**answers

27 views

### Bounds on quasi-intersecting set families

Fix $c\in (0,1]$ and $r\in\mathbb{N}$. For $n\geq 2r$, define
$$f_{r,c}(n):=\max{|\Omega_{n,c,r}|}$$ where $\Omega_{n,c,r}$ is a family of subsets of size $r$ of $(1,2,\ldots ,n)$, such that for every ...

**5**

votes

**1**answer

69 views

### New base of matroid from olds

Let M be a matroid of rank 3 and $E_1, E_2, E_3$ 3 basis of M. Let $e_{i,j}$ be the ith element of base $E_j$.
Is it true that you can always find a permutation s: {1,2,3} -> {1,2,3} such that ...

**2**

votes

**0**answers

71 views

### Number of self avoiding paths which are not ``tie together''

Consider the lattice $\mathbb{Z}^d$. Let $A_{n}$ be the set of returning self-avoiding paths (from $0$ to $0$) having length $n$. For any path $\omega \in A_{n}$, let $f(\omega)$ be the number of ...

**3**

votes

**0**answers

103 views

### Generating function of a sequence involving reciprocals of binomial coefficients

Question: Is there a closed-form expression for the following sum
$$
F(z,k,r)=\sum_{n=0}^{r} \frac{z^n}{{n+k} \choose {k}}\label{sum}\tag{1}
$$
where $z\in\mathbb{C}$, and $r$, $k$ are non-negative ...

**18**

votes

**1**answer

275 views

### Bounding Schur symmetric polynomials on the unit circle

Recall the Schur polynomial in $n$ variables, indexed by the partition $\lambda$, with $\ell(\lambda) \leq n$, is given by
\begin{equation}
s_\lambda(x_1,\ldots, x_n) = a_{\lambda + \delta}(x_1, ...

**7**

votes

**4**answers

548 views

### fixed points of permutation groups

As is well-known (see, for example, a nice exposition by our own Qiaochu: https://qchu.wordpress.com/2012/11/07/fixed-points-of-random-permutations/) that the distribution of the number of fixed ...

**2**

votes

**1**answer

212 views

### Connections to physics, geometry, geometric probability theory of Euler's beta integral (function)

Euler"s integral for the beta function $B(s,\alpha) = $ (with $x = 1$)
$$ \frac{(s-1)!(\alpha-1)!}{(s+\alpha-1)!} x^{s+\alpha-1} = \int_0^\infty t^{s-1}\; H(x-t) \; (x-t)^{\alpha-1} dt = \int_0^x ...

**5**

votes

**1**answer

149 views

### q-Integer-valued polynomials

For $n \in \mathbb{Z}_{\geq 0}$, let $[n]_q := (1-q^n)/(1-q) = (1+q+...+q^{n-1})$ as is customary, with $[0]_q=0$.
Let $R$ be the subring of $\mathbb{Q}(q)[x]$ consisting of all $f$ such that ...

**4**

votes

**2**answers

183 views

### Maximum difference between heads and tails in absolute value

I toss a fair coin $n$ times. Some notation:
$S_i=$ difference between #heads and #number of tails after the first $i$ tosses, $1\leq i\leq n$.
$M_n=\max(S_1,S_2,\dots,S_n)$,
...

**2**

votes

**1**answer

71 views

### A natural Lascoux-Schützenberger involutions on plane partitions

The Lascoux-Schützenberger involutions, $s_i$, that permute the weight of semi-standard Young tableaux are fairly known.
They satisfy some nice Coxeter relations, for example, if $v$ and $w$ are ...

**2**

votes

**0**answers

51 views

### Will the following construction leads to an counterexample of strong mapping conjecture on realizable oriented matroids?

The strong map conjecture asserts that any strong map $\mathcal{M}_1\rightarrow\mathcal{M}_2$ admit a factorization into an extension followed by a contraction. For which the counterexample has been ...

**5**

votes

**1**answer

154 views

### Determinant of symmetric Latin square

Let $n=2m$ be an even number. Let us construct $n\times n$ symmetric matrices $S_n$ in the following way. The entries are indeterminates $X_1,\ldots,X_{n-1}$. We choose a $1$-factorization of the ...

**2**

votes

**1**answer

92 views

### Combinatorics-the maximum number of subsets with a given property

Let $X$ be a set with $n$ elements. I would like to know the maximum number of subsets of $X$ such that the number of elements in the symmetric difference between any two of these subsets is at most ...

**2**

votes

**0**answers

67 views

### actions of the hyperoctahedral group

I am looking for actions (i.e., permutation representations) of the hyperoctahedral group $H_n$ studied in the literature, i.e., homomorphisms from $H_n$ to $\mathfrak S_X$, the set of bijections from ...

**1**

vote

**0**answers

65 views

### Computing the Edge Chromatic Polynomial of a graph

Is there a recursive formulae to compute the edge chromatic polynomial of a graph?
The following formulae is known for the vertex chromatic polynomial of a grapg $G$
$P(G,x)=P(G-uv, x)- P(G/uv,x)$ ...

**9**

votes

**0**answers

145 views

### Embedding $\beta\mathbb{N}$ into a product of Cantor sets

Let us consider $\beta\mathbb{N}$, the Stone-Czech compactification of the natural numbers (where we do not take $0$ to be a natural number, so the only idempotent elements are nonprincipal ...

**4**

votes

**1**answer

167 views

### Counting trees according to endpoints

Question: Is there a nice (or any) formula for the generating function
$$T(x,y) = \sum_{m,n} t_{m,n} x^my^n,$$
where $t_{m,n}$ is the number of trees with $m$ vertices and $n$ endpoints?
...

**4**

votes

**1**answer

73 views

### distinct multiple points in a space with at least one point lying in a subspace

Let $X$ be a topological space and $A$ a subspace of $X$. Given $k\geq 2$, let the unordered configuration space be
$$
B(X,k)=\{(x_1,x_2,\cdots,x_k)\in X^k\mid x_i\neq x_j \text{ for any } i\neq j\}
...

**5**

votes

**1**answer

147 views

### “Database” of simplicial polytopes/spheres

Reading through various papers on polytopes I have come across really interesting examples of simplical polytopes and non-shellable (or non-PL) simplicial spheres but sometimes it is hard to keep ...

**2**

votes

**0**answers

49 views

### Is there a distance function on Dyck/Tamari words of arbitrary length?

Consider sequences of well-formed parentheses (or up/down sequences) of the type counted by the Catalan numbers. See http://www-math.mit.edu/~rstan/ec/catalan.pdf
These are sometimes called Dyck ...

**6**

votes

**2**answers

240 views

### Is this algebra isomorphic to an incidence algebra?

This question is motivated by trying to establish a converse to Theorem 7.8 of our paper.
I have a finite poset $P$ with the following properties:
$P$ has binary meets (and hence a least element).
...

**-2**

votes

**1**answer

247 views

### Calculating a sum including large numbers [closed]

Let
$\theta(x)=\begin{cases}
0 & \text{ if } x<0 \\
1 & \text{ if } x\ge 0
\end{cases}$
Do you know any way to calculate this number:
...