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)

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
156 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
448 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 ...
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
107 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
85 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
101 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 ...
4
votes
1answer
254 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
49 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
138 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
59 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
83 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
21 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
143 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
154 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
48 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
414 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
75 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 ...
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
93 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
282 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} ...
6
votes
4answers
366 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
173 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
58 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
70 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
56 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
88 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
265 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
76 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
63 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
46 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
237 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
56 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
89 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
182 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
544 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
205 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
229 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 ...
2
votes
1answer
225 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 ...
0
votes
1answer
72 views

Vertex cover of regular graph

(1.) How small can set $S$ of vertices in any regular undirected graph $G$ on $n$ vertices with degree $\Omega(n^\alpha)$ where $\alpha\in(0,1)$ can be such that every edge in the graph is incident on ...
26
votes
1answer
520 views

Why do the adjoint representations of three exceptional groups have the same first eight moments?

For a representation of a compact Lie group, the $n$th moment of the trace of that representation against the Haar measure is the dimension of the invariant subspace of the $n$th tensor power. The ...