# Tagged Questions

**4**

votes

**1**answer

118 views

### A decomposition of $w_0$ which is similar to the reduced decomposition

Some basic definitions about reduced decomposition:
In the symmetric group $S_n$, let $s_i$ denote the adjacent transposition $(i,i+1),i\in \{1,2,\cdots,n-1\}.$ Since $S_n$ is generated by adjacent ...

**5**

votes

**1**answer

168 views

### Counting the number of permutations of $(1,\ldots,i,\ldots,j,\ldots,m)$, where $i < j$ and number of inversions is $k$

How can I prove the following:
$d^{ij}(m,k) > d^{ji}(m,k)$ for all $k < \frac{1}{2}\binom{m}{2},$
where $d^{ij}(m,k)$ denotes the number of permutations of $(1,\ldots,i,\ldots,j,\ldots,m)$ ...

**5**

votes

**0**answers

125 views

### Complexity of $\mathbb{Z}^n$ tilings

Let $\mathcal{T} \subset \mathbb{Z}^n$ be a finite set. Let $\Lambda \subset \mathbb{Z}^n$ be a full rank lattice.
We say that $\mathcal{T}$ is a $\Lambda$-tile for $\mathbb{Z}^n$ if the following ...

**1**

vote

**2**answers

157 views

### aproximate sum involving binomial coefficients

I have the problem for computing the j-derivative of a logarithm, with $j\gg1$
\begin{equation}
c_j=\left.\frac{\partial^j}{\partial s^j}\log\left(1+Ae^s+Be^{2s}\right)\right|_{s=0},
\end{equation}
...

**9**

votes

**1**answer

451 views

### combinatorics on cyclic sequences

Given $m\geq 1$, let $I=(a_1,\ldots,a_{3m})$ be a sequence such that $I$ contains exactly $m$ zeros, $m$ ones, and $m$ twos.
Given $i=1,2$ and $j\leq 3m,k\leq m$ we can define $$U_{i,j}(k)=\text{...

**0**

votes

**0**answers

45 views

### Approximation to colouring for bounded degree graphs

I have already asked one question on colouring, this question is more specific.
Given a bounded degree graph $G$ with $\Delta(G)=2d$, is there a well know algorithm to achieve an approximation ratio ...

**4**

votes

**0**answers

110 views

### Littlewood-Richardson rule for the complete flag variety: GapP complete?

The cohomology ring of a complete flag variety $X$ has a basis of Schubert classes $S_u$ for permutations $u$. Define the Littlewood-Richardson coefficient $c_{uv}^w$ for permutations $u,v,w$ to be ...

**3**

votes

**0**answers

88 views

### regular triangulations of the product of two simplices

Is description of all regular triangluations of $\Delta^n\times \Delta^k$ known? (Regular triangulations are those which correspond to vertices of Gelfand--Kapranov--Zelevinsky secondary polytope, or, ...

**2**

votes

**0**answers

102 views

### Enumerating the number of degree d curves tangent to a planar conic

This question is based on a special case of the Coparaso Harris formula, as described in Counting curves on rational surfaces - R. Vakil.
Let $E$ be a non-singular planar conic.
Then every degree $d$...

**4**

votes

**1**answer

257 views

### Who first considered constructibility of simplicial complexes?

A simplicial complex of dimension $d$ is called constructible if it is a simplex, or if it is the union of two constructible dimension-$d$ simplicial complexes along a dimension-$(d-1)$ intersection. ...

**7**

votes

**1**answer

419 views

### One more strengthening of Frankl's conjecture

If I'm not wrong, it is easy to prove the following statements :
1° For every natural number $k$, every union-closed family that has at least $2$ members with cardinality $\geq k$ has at least $2$ ...

**1**

vote

**1**answer

76 views

### Graph colouring for bounded degree graphs

I'm fairly new to colourings on bounded degree graphs i'm interested in the following questions,
For planar graphs with bounded degree $4$ is finding the colouring number $NP$-hard? So is ...

**0**

votes

**0**answers

50 views

### normal sets and conjugate generating sets of $S_n$

In this arXiv paper (p. 13), Steinhardt defines a normal set in $S_n$ as follows:
Definition: A split set of more than two cycles generating $S_n$ is said to be normal if any element is adjacent to ...

**7**

votes

**1**answer

141 views

### Can every trace preserving isomorphism of unital self-adjoint matrix algebras be realized as conjugation by a unitary?

In this paper, Friedland shows (in Lemma 3.4) that if $\phi$ is an isomorphism of coherent algebras, then there exists a unitary $U$ such that
$$ \phi(M) = UMU^\dagger$$
for all $M$. I am wondering if ...

**1**

vote

**1**answer

60 views

### Choose uniformly from fixed-length paths in $[0,n]\cap\mathbb{Z}$ with fixed start and end

Let $X_k$ be a symmetric (discrete time) random walk on $\mathbb{Z}$ and let $m,n\in\mathbb{N}$. I want to chose uniformly from the paths of $X_k$, which
start at $0$
stay in $[0,n]\cap\mathbb{Z}$ ...

**1**

vote

**0**answers

84 views

### Sum of products of binomial coefficients

I have been trying to check that two things are equal for a while now, Mathematica appears to say that they are but I can't for the life of me figure out how to show it (without just saying 'computer ...

**1**

vote

**0**answers

22 views

### Frobenius form of the quotient of a partition

Let $\mu$ be a partition of $n \cdot l$ with a trivial $l$-core. To $\mu$ we can associate an $l$-multipartition of $n$ called the $l$-quotient of $\mu$. There are several equivalent descriptions of ...

**8**

votes

**1**answer

145 views

### Non-isomorphic graphs with isomorphic edge vectors

Let $G$ and $H$ be graphs on the vertex set $\{1, \ldots, n\}$ and let $(e_i)$ be the standard basis of $\mathbb{R}^n$. For each edge $\{i,j\}$ define edge vectors $e_i - e_j$ and $e_j - e_i$ in $\...

**4**

votes

**1**answer

156 views

### Sum of skew characters over hooks and “odd” partitions

Let us call a partition odd if all its parts are odd, and let $Odd(n)$ be the set of all odd partitions of $n$, e.g. $Odd(6)=\{(5\,1),(3\, 3),(3\,1^3),(1^6)\}$.
Let $H(n)$ denote the set of all hook ...

**1**

vote

**0**answers

51 views

### if $\Delta$ is pure, then what happens to betti-numbers of $I_{\Delta}$ or $I_{\Delta^v}$

Assume that $\Delta$ is a simplicial complex and $\Delta ^v$ is its Alexander dual.
Let in addition $\Delta$ be pure, then what happens to betti-numbers of $I_{\Delta}$ or $I_{\Delta^v}$?
Is there a ...

**18**

votes

**2**answers

417 views

### Counting problems where unlabeled is easier than labeled

I was encouraged to post this question by Jim Propp during a meeting of the Cambridge Combinatorics and Coffee Club. It is a counterpoint to the MathOverflow question "Counting Problems where Labeled ...

**3**

votes

**0**answers

47 views

### Number of Hamiltonian paths in the Hoffman-Singleton graph/Moore graphs?

Does anyone happen to know how many Hamiltonian paths are in the Hoffman-Singleton graph, or have any idea on how I could count such paths?

**0**

votes

**1**answer

76 views

### Majority colorings

If $X$ is a non-empty set, we say that $M\subseteq X$ is a majority if $|M| > |X\setminus M|$.
Let $G=(V,E)$ be a finite, simple, undirected graph. For $v\in V$ we set $N(v)=\{x\in V: \{x,v\} \in ...

**5**

votes

**0**answers

76 views

### How long does it take for the action of the braid monoids on Laver tables to become trivial?

Let $A_{n}$ denote the classical Laver table of cardinality $2^{n}$.
Let $B_{n}^{*}$ denote the positive (including the identity) braid monoid on $n$ elements generated by $\sigma_{1},...,\sigma_{n}$....

**40**

votes

**1**answer

2k views

### Why is the Frankl conjecture hard?

This is a naive question that could justifiably be quickly closed.
Nevertheless:
Q. Why is
Péter Frankl's
conjecture so difficult?
If any two sets in some family of sets have a union that also ...

**6**

votes

**0**answers

95 views

### Counting nonzero hyperdeterminants over $\mathbb{F}_q$

The hyperdeterminant $D(A)$ is a multidimensional generalization of the
determinant. It is a polynomial in the entries of a $(k_1+1)\times
(k_2+1)\times\cdots \times (k_n+1)$ array $A$. The ...

**8**

votes

**3**answers

286 views

### Combinatorial aspects of continued fractions

Recently, I got interested in the study of the combinatorial aspects of continued fractions. Precisely, I read of the following lemma of Flajolet (see here):
Lemma. It holds
$$\sum_{\omega} \nu(\...

**6**

votes

**4**answers

369 views

### Literature about a property of union closed families?

Trying to solve a problem, I fell on the following statement :
If $k$ and $r$ are natural numbers such that $r \leq k$, if a union closed family of sets ("union closed" means that the union of two ...

**2**

votes

**2**answers

175 views

### Decomposing a graph into n-cycles [closed]

Suppose I have a strongly $k-regular$ graph $G$, of size $v$, where every vertex is $N>0$ $n-cycles$, for $at least$ one value of $n$ that divides $v$. Can we cut edges from $G$ in such a way ...

**0**

votes

**0**answers

60 views

### When does this system of equations has a non-trivial solution?

Let $A$ be a non-negative matrix whose rows and columns are indexed by the elements of $2^M$ - the subsets of some finite set $M$. The subsets of $2^M$ are ordered according to some pre-specified ...

**7**

votes

**0**answers

71 views

### Skew zonal polynomials, skew zonal spherical functions, and combinatorics

Zonal polynomials may be expressed in terms of power sums as $$Z_\lambda=n!\sum_\nu \frac{1}{z_\nu }2^{n-\ell(\nu)}\omega_\lambda(\nu)p_\nu,$$ with usual notation in which $\omega_\lambda(\nu)$ are ...

**1**

vote

**0**answers

57 views

### Characterizing normal vectors of affinely independent subsets of the hypercube

Suppose we are looking at the hypercube in $\mathbb{R}^n$. I tend to the think of the cube with vertex coordinates 0 or 1, but maybe this is easier for the $\pm1$ cube.
Now suppose we have an affine ...

**0**

votes

**1**answer

97 views

### Proof of Stirling number symmetric formulas [closed]

I'm looking for a reference to a proof of formulas 6.26 and 6.27 in Concrete Mathematics:
$\def\sone#1#2{\left[#1\atop #2\right]}
\def\stwo#1#2{\left\{#1\atop #2\right\}}
$
$$\stwo{n}{n-m} = \sum_k \...

**4**

votes

**2**answers

266 views

### k nearest points

Assume $n$ points $P_i \in \mathbb{R}^2, i \in {1,2,...,n}$. For each point there is a $k$ nearest neighbour $(k<n)$, or equivalently for each point $P_i$ there is one circle with center the point $...

**1**

vote

**0**answers

77 views

### Relation to Ehrhart polynomial with Uniqueness

A set of relative prime, positive integers $A = [a_1, \dots, a_d]$ describe the restricted partition function
$$
p_A(n) = \# \{(m_1,\dots,m_d)\in\mathbb{Z}^d: \textrm{ all }m_j \geq 0, \sum_{j=1}^d ...

**1**

vote

**0**answers

38 views

### Invariants of Permutations with Predicate and Equivalency Relation

Has the following kind of problem been investigated previously and, where can I find information about it:
Given
the set $\mathbb{P}_{n_0}$ of all permutations of $n_0$ elements
a ...

**2**

votes

**1**answer

69 views

### Directed edge-colouring

I'm interested to know whether the following problem is NP-complete or if there is an algorithm to solve it.
Suppose we are given a directed graph $G=(V,E^{\rightarrow})$ and we want to colour the ...

**1**

vote

**1**answer

64 views

### Covering designs where $v$ is linear in $k$

A $(v,k,t)$ covering design is a collection of $k$-subsets of $V=\{1,\ldots,v\}$ chosen so that any $t$-subset of $V$ is contained in (or "covered by") at least one $k$-set in the collection. ...

**3**

votes

**0**answers

48 views

### Antichains defining facets of a certain cone

Let $(P,<)$ be a finite poset. Let $V$ be the free $\mathbb{R}$-vector space on $P \times \{0,1\}$; I'll write elements as sums of pairs of the form $(p,0)$ and $(0,q)$, so a general element is $$v ...

**0**

votes

**1**answer

130 views

### Infinite graph with degrees given

Let $\kappa$ be an infinite cardinal and suppose $$n, d: \kappa \to \big((\kappa+1)\setminus \{0\}\big) = \{1, \ldots, \kappa\}$$ are arbitrary functions.
Is there $E \subseteq \big\{\{x,y\}: x\neq y ...

**8**

votes

**1**answer

239 views

### Integer sets with forbidden differences

Given a finite set $S$ of positive integers, and a positive integer $n$, let $F(n,S)$ be the largest possible cardinality of a subset of {$1,2,\dots,n$} no two of whose elements differ by a number in $...

**0**

votes

**0**answers

57 views

### Quick way to compute Ehrhart polynomial of Young diagram posets?

Using the hook formula, it is easy to compute the volume of order polytopes obtained from posets with partition shape, since this is the same as the number of linear extensions.
To my knowledge, ...

**4**

votes

**2**answers

93 views

### sum of squares of Schur polynomials indexed over partition valued functions on a set

Fix a finite set $X$ and two natural numbers $d$ and $n$.
For a partition $\lambda$ and a number $d$ denote by $s_\lambda^d(x_1,\dots,x_d)$ the Schur polynomial in $d$-many variables $x_1,\dots,x_d$. ...

**5**

votes

**1**answer

185 views

### Hyperoctahedral group acting on a special permutation

Let $[n]=\{1,...,n\}$ and $[\hat n]=\{\hat 1,...,\hat n\}$. Realize the hyperoctahedral group $H_n$ as the centralizer of the permutation $(1\hat 1)\cdots (n \hat n)$. It has $2^n n!$ elements.
Let $...

**3**

votes

**2**answers

275 views

### When do such regular set systems exist?

Let '$n$-set' mean 'a set with $n$ elements'.
May we choose $77=\frac16\binom{11}5$ 5-subsets of 11-set $M$ such that any 6-subset $A\subset M$ contains unique chosen subset? Positive answer to ...

**6**

votes

**1**answer

562 views

### Positivity of the alternating sum of indices for boolean interval of finite groups

Let $G$ be a finite group and $H$ a subgroup such that the interval $[H,G]$ is a boolean lattice.
Let $L_1, \dots , L_n$ be the maximal subgroups of $G$ containing $H$.
Let the alternative sum ...

**2**

votes

**0**answers

206 views

### Identity with Ramanujan's generalized continued fraction

Let $F(x,q)=\sum_{n\geq 0}x^n\dfrac{q^{n^2}}{(q)_n}$, where $(q)_n=(1-q)(1-q^2)\dots(1-q^n)$. Then:
$$H(x,q)=\frac{F(-xq,q)}{F(-x,q)}=\dfrac{1}{1-\dfrac{qx}{1-\dfrac{q^2x}{1-\dots}}}$$ is the ...

**1**

vote

**1**answer

233 views

### Good graph theory and combinatorics book

I am looking for a book about graph theory and combinatorics. I am studying the routing problem in communication networks, therefore my interest is on a book with a wide set of problems and examples.
...

**4**

votes

**1**answer

273 views

### What are the 4 convex simplicial 4-polytopes that have 6 vertices?

In Convex polytopes and related complexes by Klee and Kleinschmidt they state the number of $d$-polytopes with $d+2$ vertices is $\lfloor \frac{d^2}{4}\rfloor$.
I was wondering what the four $4$-...

**2**

votes

**1**answer

227 views

### A generalization of Frankl's conjecture?

Would it be reasonable to conjecture what follows : there is a real constant $c > 1/2$ such that, for every natural number $n$, if $X_{1}, \ldots , X_{n}$ is a union-stable family of distinct ...