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)

4
votes
1answer
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
1answer
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
0answers
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
2answers
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
2answers
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
3answers
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
4answers
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
2answers
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
0answers
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
0answers
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
0answers
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
1answer
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
2answers
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
2answers
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
1answer
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
2answers
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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 ...