**6**

votes

**0**answers

86 views

### By replacing the Laver tables with nearly distributive fake Laver tables, can one produce algebras where the period of 1 grows fast?

I am now generalizing the notion of the classical Laver table and the fake Laver table to a larger class of algebras. A sequence of algebras $(\{1,...,2^{n}\},*_{n})_{n\in\omega}$ is said to be a ...

**6**

votes

**0**answers

113 views

### How distributive are the fake Laver tables?

The Laver table $A_{n}$ is the unique algebra $(\{1,...,2^{n}\},*)$ such that $x*1=x+1$ for $1\leq x<2^{n}$, $2^{n}*1=1$, and $x*(y*z)=(x*y)*(x*z)$.
Let's now replace the Laver table $A_{n}$ with ...

**5**

votes

**1**answer

166 views

### Is this subset-sum-type problem discussed in the literature?

Let $y \in \mathbb{Z}_+^n$, with $y_1 < \dots < y_n$. I am interested in finding a 0-1 matrix $A$ and $x \in \mathbb{Z}_+^m$ s.t. $m$ is minimal and $Ax = y$, where I am guaranteed that at least ...

**3**

votes

**0**answers

116 views

### How to prove $\prod_{\lambda\vdash n}\prod_im_i(\lambda)!=\prod_{\lambda\vdash n}1^{m_1(\lambda)}2^{m_2(\lambda)}\cdots$

Let $\lambda$ be a partition of an positive integer $n$, it can be presented as $\lambda=(\lambda_{1},\lambda_2,\cdots,\lambda_l)$ such that $\lambda_1\geq\lambda_2\geq\cdots\geq\lambda_l>0$, or ...

**3**

votes

**0**answers

46 views

### How to prove that $\sum_{i=0}^n\frac{(a;q)_i}{(q;q)_i}\frac{(b;q)_{n-i}}{(q;q)_{n-i}}a^{n-i}=\frac{(ab;q)_n}{(q;q)_n}$?

By Cauchy identity, $${}_1\phi_0(a;—;q,z)=\sum_{n\geq0}\frac{(a;q)_n}{(q;q)_n}z^n=\frac{(az;q)_{\infty}}{(z;q)_\infty},\quad|z|<1,|q|<1,$$
we can obtain the $q-$analogue of ...

**5**

votes

**0**answers

93 views

### (Double) Crystal reflection operators on SSYTs

I am not that familiar with the language of crystals, but this is what I know:
Let $SSYT(\lambda, \mu)$ be the set of semi-standard Young tableaux with shape $\lambda$ and weight $\mu$.
There are ...

**6**

votes

**2**answers

307 views

### Sums of reciprocals of products of factorials

Let $d,m, r$ be positive integers, and define
$$
S = \left\{ (i_1, i_2, \dots, i_m) \in {\bf Z}_{+}^{m} \left | \sum_j i_j = d; \& \forall j, i_j \leq r \right. \right\};
$$
Here ${\bf Z}_+$ ...

**8**

votes

**0**answers

91 views

### Product of Partial Orders

Define the transpose product of a partial order $P$ over a set $S$ in the following way. The direct product of a partial order $P \subseteq S \times S$ and its converse, $P^{op}$, gives a partial ...

**7**

votes

**2**answers

131 views

### $f$-vector of simple convex polytope via directions of facets

Let $P$ be a simple convex polytope in $\mathbb{R}^d$ (that is, any vertex belongs to exactly $d+1$ facets). Given the collection of outer normals to facets of $P$, combinatorics of $P$ may be ...

**1**

vote

**1**answer

67 views

### Probability of paths to the boundary of a tree

Let $G_n$ be the $4$-regular tree of depth $n$, that is to say the finite graph given by the ball of radius $n$ in the Cayley graph of the free group on two generators. By the root I mean the vertex ...

**5**

votes

**1**answer

152 views

### Intersection of rotating regular polygons

This question has a recreational flavor, but may not be
entirely uninteresting.
Let $P_k$ be a unit-radius regular polygon of $k$ sides,
and $P_n$ a unit-radius regular polygon of $n \ge k$ sides.
...

**11**

votes

**2**answers

811 views

### On Hamkins' answer to a problem by Michael Hardy

Based on a post by Michael Hardy and Hamkins' answer to it Andreas Blass, Will Brian, Joel Hamkins, Michael Hardy and Paul Larson introduced a new cardinal characteristic of the continuum ...

**7**

votes

**3**answers

675 views

### Sum of inverse of multinomial coefficients

Find an asymptotically tight estimate for the sum
$$
A_n^{k}(\lambda)= \sum_{
\substack{a_i\geq \lambda_i
\\
a_1+a_2+\dots a_k=n
}} \prod_{i=1}^k a_i!
$$
Is the leading term going to be
...

**4**

votes

**1**answer

209 views

### Lexicographic order on increasing $k$-tuples

Let $L(n,k)$ be the increasing $k$-tuples from $\{1,\dots,n\}$, listed in lexicographic order.
Eg, for $n=9$, $k=3$, the sequence $L(n,k)$ would be:
$$(1,2,3), (1, 2, 4), (1, 2, 5),\dots,(7, 8, ...

**2**

votes

**1**answer

98 views

### VLSI circuit embeddings

In the following paper by Valiant
http://www.computer.org/csdl/trans/tc/1981/02/06312176.pdf
He shows under theorem 2 (at the bottom of the second page) that any planar graph $G$ of degree 3 or 4 ...

**6**

votes

**1**answer

285 views

### Graphs in which any two odd cycle have a common vertex

Let $G$ be a graph in which any two odd cycles have a common vertex. It is easy to see that $\chi(G)\leq 5$ (choose minimal odd cycle $C$, use two colors for $G\setminus C$ and three colors for $C$). ...

**0**

votes

**0**answers

102 views

### Is there any result on the homomorphic images of hypercube graphs?

Let $Q_n$ be a hypercube graph and $\phi: Q_n\to G$ a surjective simplicial graph morphism i.e. if $u,v$ are adjacent vertices in $Q_n$ then either $\phi(u)=\phi(v)$ or $\phi(u),\phi(v)$ are adjacent. ...

**3**

votes

**1**answer

186 views

### Planarity of infinite graphs

Let $G$ be a graph with disjoint copies of $K_{1,3}$. Prove that if there are uncountably many copies of $K_{1,3}$ in $G$, then $G$ is not planar.
I have a proof of this statement by ...

**2**

votes

**1**answer

165 views

### Asymptotic of a sum involving binomial coefficients

Good evening, I'm trying to find an asymptotic of this sum:
$$\sum_{j=0}^n (-1)^j {n \choose j} (n - j)^n = n^n - {n \choose 1} (n - 1)^n + {n \choose 2} (n - 2)^n + ... + (-1)^n {n \choose n} (n - ...

**7**

votes

**1**answer

264 views

### Chromatic numbers of nowhere dense graphs

Given $c\in (0,1)$ and a graph $G=(V,E)$ such that any subset $U\subset V$ contains an independent subset of cardinality at least $c|U|$. Does it allow to bound the chromatic number $\chi(G)$ by the ...

**7**

votes

**1**answer

181 views

### Constructing a generating function using a series with all negative and positive powers of a variable

Trying to count certain combinatorial structures, I arrived at a construction of their generating function through a very inconvenient procedure.
I realize that anybody who will read this has right ...

**1**

vote

**0**answers

57 views

### Characterization of certain families of functions

For $R$ equal $\mathbb{R}$ or $\mathbb{Z}$, let $D^+_R:=\{(x,y)\in R^2\colon x<y\}$. For each natural $n$, let $F_{n,R}$ denote the set of all Borel-measurable functions $f\colon ...

**14**

votes

**1**answer

311 views

### Why does $\sum_{p=1}^n \exp\left(\frac{i\pi p l}{2m}\right)/\prod_{k=1,k\neq p}^n\sin\left(\frac{\pi (k-p)}{2m}\right)$ vanish?

While trying to prove some identities for generating functions, I ended up needing to show that
$$\sum_{p=1}^n \exp\left(\frac{i\pi p l}{2m}\right)\prod_{\substack{k=1\\k\neq ...

**16**

votes

**0**answers

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

**1**

vote

**2**answers

97 views

### A combinatorial optimization problem [closed]

A seller wants to sell $N$ goods to $M$ buyers. To that end, the seller collects the prices offered by each buyer $m$ on each good $i$ ($m=1,\cdots,M$, $i=1,\cdots,N$) $p_{mi}$. Given $\{p_{mi}\}$, I ...

**4**

votes

**0**answers

75 views

### Finding closest set of K disjoint hyperspheres to a point in $\mathbb{R}^n$ with uniform radius

I am interested in the following problem: in $\mathbb{R}^n$, we have $N$ overlapping hyperspheres all with the same radius. Given a point $p$ in $\mathbb{R}^n$, the objective is to find the $K$ non ...

**7**

votes

**1**answer

215 views

### State of the art in the expected length of the Longest Increasing Subsequence of a random permutation

I have been reading about the topic motivated by a problem I read that asked for the first three digits of the sum of the LIS lengths in all permutations of length $n$. It is easy to see that we are ...

**3**

votes

**0**answers

129 views

### Which Dihedral Groups are $\text{CI}$-Groups?

Let $D_{n}$ denotes the dihedral group of order $2n$. Firstly, for self-referencing of the question, I give some definitions which are standard.
Let $G$ be a finite group. A subset $S$ of group $G$ ...

**7**

votes

**2**answers

212 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)$ ...

**5**

votes

**1**answer

147 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

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

**9**

votes

**1**answer

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

**5**

votes

**0**answers

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

**8**

votes

**0**answers

128 views

### Edge-colorings of plane graphs: do you know references where the following questions are studied?

Let $G$ be a plane graph (or more generally, a graph embedded on a surface) with a proper edge-coloring of $G$ with $k$ colors $\{1,\ldots,k\}$. I am interested in studying the cyclic permutations of ...

**7**

votes

**1**answer

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

**7**

votes

**0**answers

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

**14**

votes

**1**answer

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

**12**

votes

**1**answer

263 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

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

**3**

votes

**1**answer

178 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

105 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

182 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

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

**7**

votes

**0**answers

115 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

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

**11**

votes

**2**answers

408 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

**2**answers

190 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

101 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

74 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

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