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)

1
vote
1answer
72 views

Counting tournaments with ties

An improper tournament, or tournament with ties, is a graph in which every pair of nodes is connected by a single uniquely directed edge or by a single undirected edge. There are 1, 2, and 7 improper ...
7
votes
3answers
418 views

Homotopy type of some lattices with top and bottom removed

The only reaction to this question on math.SE was 21 views in 4 days, so I decided to repost it here. I am not changing anything. There was an interesting question on MO which OP removed by some ...
2
votes
3answers
293 views

Discriminants of indefinite integral binary quadratic forms admitting 3 or 6 torsion.

Are there any results known about the discriminants of indefinite integral binary quadratic forms admitting automorphisms of order 3 or 6? It seems reasonable to expect that any permissible ...
3
votes
4answers
1k views

Implementation of the Robinson-Schensted Correspondence

Has the Robinson-Schensted correspondence, as explained by Wikipedia or Richard Stanley, been implemented in any of the standard programming languages. I'm using Python, but I'm open to Java, C++, ...
5
votes
2answers
119 views

Do character tables determine association schemes up to isomorphism?

I am interested in commutative, but not-necessarily-symmetric association schemes. I noticed that the conjugacy class scheme of the dihedral group of order 8 has the same character table as the one ...
4
votes
0answers
111 views

Combinatorial fairness property in division of goods

Given $n$ agents, and $m$ items where $v_i(g) \geq 0$ is the value of item $g$ for agent $i$, does there always exist a partition $A_1, ..., A_n$ of the $m$ items into $n$ sets s.t. for all $i, j \in \...
4
votes
0answers
37 views

Number of classes $\pmod p$ represented by $b_1s^{n-1} + \dots + b_n$ where $ord_p(s) = n$

Let $n \in \mathbb Z$ with $n \ge 3$ and let $p$ be a prime number such that $n|p-1$. Let $a_1,a_2,\dots,a_{2n-1} \in \mathbb Z/p\mathbb Z$. Suppose that the same class is represented by at most $n-1$ ...
8
votes
2answers
173 views

An identity related to partitions into $n$ parts and Schur polynomials

While working with Schur polynomials I found what seems like a nice identity, and I wonder if it has a simple proof. Notation: Suppose $d,n\in\mathbb{N}$, and $\lambda =(\lambda_1,\dots,\lambda_n)$ ...
0
votes
1answer
101 views

Exact formula for computing n-step transition probability of random walks with self-transitions

Consider a semi-infinite random walks $X_n$, $n=0,1,2,\ldots$, whose state space is a set of consecutive integers and whose one-step transition probabilities are $P_{ij}=\mathrm{Pr}\{X_{n+1}=j|X_n=i\}$...
6
votes
2answers
224 views
+150

Seeking very regular $\mathbb Q$-acyclic complexes

This question was raised from a project with Nati Linial and Yuval Peled We are seeking a $3$-dimensional simplicial complex $K$ on $12$ vertices with the following properties a) $K$ has a complete $...
0
votes
0answers
85 views

Sum of unit vectors always has a binary span after constrained permutations

Conjecture: Let $e_1 = (1,0,\ldots,0), \ldots , e_{m_1+m_2} = (0,\ldots,0,1)$ be the unit vectors of the standard basis $E$ of $\mathbb{R}^{m_1+m_2}$. An enumeration $ E \cup -E = \{f_1, \ldots, ...
3
votes
2answers
183 views

Examples of Sets with Positive Upper Density

While reading the statement of Roth's theorem I started asking myself what are examples of sets of positive upper density? It's not hard to come up with a few: Flip a coin with probability $\mathbb{...
8
votes
1answer
589 views

Bipartite Graphs arising from two k-partitions of a given Graph

Let $G$ be an $n$-chromatic connected graph. Let $(V_1, V_2, \cdots, V_n)$ and $(U_1, U_2, \cdots, U_n)$ be two partitions of $V(G)$ corresponding to proper n-colorings of $G$. Consider the bipartite ...
51
votes
6answers
5k views

How to recognise that the polynomial method might work

A couple of days ago I was at a nice seminar given by Christian Reiher, during which he told us about a short proof of the following special case of a theorem of Olson. Theorem. Let $(a_1,b_1),\dots,(...
1
vote
1answer
120 views

Convexity of truncated expectation

Let $k, n$ be two positive integers with $k \leq n$, and let $P = \{ (x_1, \dots, x_n) \in [0, 1]^n : \sum_i x_i = k \}$. Given $x = (x_1, x_2, \dots, x_n) \in P$, let $X_i$ be the random variable ...
4
votes
0answers
91 views

A color interpolation lemma

I need the following "color interpolation lemma". Actually I know a way to prove it, but I'm not very satisfied with that proof. Lemma. Let $G=(V,E)$ be a (properly) colored graph with colors $1, \...
6
votes
1answer
244 views

The current status of the conjecture on algebraic matroids

Can anyone point out some articles for the conjecture: the dual of an algebraic matroid is algebraic? Thank you!
3
votes
2answers
139 views

Combinatorial identity involving number of cycles (of any length) in a permutation

I am going through Phil Hanlon's paper and on page 127, right after the first paragraph, "It is well known that.." which boils down to the following identity: $$ \prod_{i=0}^{n-1}(\beta-i) = \sum_{\...
-1
votes
1answer
135 views

number of partitions from 0 to n^2 [on hold]

You are given the numbers 0 to n^2. You must use n numbers with no number greater than n to form all the partitions of the numbers 0 to n^2. For example with n=4 you want to find the partitions of 7:...
4
votes
1answer
272 views

A variant of bin-and-ball problem

We have $n$ balls, each belonging to a group (e.g, color). There are $g$ groups ($g$ may be large but $g=o(n)$). We sequentially put the balls into $m$ bins in the following way: for each ball, we ...
0
votes
1answer
50 views

Count Functional digraph [on hold]

Given a set of nodes, how can I count the number of different functional digraph containing a specific number of connected components? With a restriction that no node can have an edge point to itself. ...
8
votes
0answers
185 views

A Combinatorial Game: the Snake and the Hunter

The Snake and the Hunter is a game for two players who play in two rounds interchanging the roles of snake and hunter. The game is played in a rectangular grid of points, say $6 \times 6$. In both ...
6
votes
1answer
129 views

q-analog of a combinatorial identity involving binomial coefficients

Using, e.g., properties of iterated finite differences it is easy to show that for any pair of integers $n$ and $m$ with $n>\!>m$ one has the identity $$ \sum_{k=0}^m(-1)^{k-m} {n-k\choose m}{m\...
2
votes
0answers
47 views

Average range of Motzkin path

Motzkin path are paths from (0,0) to (n,0) in $\mathbb{Z}^2$ such that we are allowed to move SE, E and NE. More on this is here https://en.wikipedia.org/wiki/Motzkin_number I would like to know if ...
0
votes
1answer
63 views

On some examples of critical families

I'm reading the book on Injective choice functions by Holz, Podewski and Steffens, and I find it to be at the same time well written and quite difficult. It has almost no examples - and in quite a few ...
7
votes
1answer
130 views

On a result of Frankl and Wilson

In the paper 'Intersection theorems with geometric consequences' (Combinatorica 1981) P. Frankl and R. M. Wilson consider families $\mathcal{F}$ of $k$-subsets of $\{1,\dots,n\}$ with the restriction ...
1
vote
1answer
131 views

Rank 2 complex vector bundles over $S^2\times S^2$

How could people classify all rank $2$ complex vector bundles over $S^2\times S^2$ up to isomorphism? Could you give a rank 2 complex vector bundle which cannot be split as a sum of two line bundles?
3
votes
0answers
100 views

A question about smooth convex lattice polygons

Let $P$ be a smooth convex lattice polygon in $\mathbb{R}^2$ (the lattice being $\mathbb{Z}^2$). Here smooth means that at any vertex of $P$, the two primitive integer vectors (i.e. vectors whose ...
10
votes
3answers
292 views

How to sample a uniform random polyomino?

A polyomino is formed by joining finitely many unit squares edge to edge. It may be regarded as a finite subset of the regular square tiling with a connected interior. In particular, for us, ...
3
votes
0answers
193 views

On weight enumerators of codes

Are there $[n,k]_q$ constant rate $\frac kn$ and constant alphabet linear code families with automorphism group of size $\Omega((n-n^\beta)!)$ that have minimum distance $d=O(n^\alpha)$ and number of ...
2
votes
0answers
191 views

Average minimum number of random k-sparse vectors in $\mathbb{F}_2^n$ to span a specific base vector?

A while back I posted a question in MO about the average minimum number of independent random k-sparse (having at most $k$ non-zero elements) vectors belonging to $\mathbb{F}_2^n$ to span the whole ...
5
votes
0answers
97 views

For which Ramsey type results density versions are wrong?

I look for examples of Ramsey-type statements, for which the density counterparts do not hold. Example: usual Ramsey theorem. If all edges of a complete graph $K_n$ are colored in $c$ colors, there ...
0
votes
0answers
48 views

When are these sums consecutive integers? [closed]

It is possible to construct $\frac{n(n-1)}{2}$ sums which each contain two distinct summands chosen from a set $n$ numbers. For which $n\geq 3$ do there exist a set of $n$ (distinct) integers such ...
8
votes
3answers
579 views

Is there a 2-connected k-regular graph without Hamiltonian path?

In this paper (Construction 2.6 p860) the authors have built examples of connected $k$-regular graph without Hamiltonian path, but with a cut-vertex (i.e. it is not $2$-connected). Question: Is ...
3
votes
1answer
89 views

Generating Uniquely k-Optimal Point Sets

This question is motivated by the observation that finding an optimal tour through a set of points in the Euclidean plane is especially simple, if the points are in convex configuration and, that the ...
2
votes
1answer
172 views

Finding many disjoint sub-trees with many leaves

Let $T$ be a rooted binary tree with $L$ leaves, and let $\ell$ be a natural number smaller than $L$. The question is what is the maximal number of disjoint rooted sub-trees with at least $\ell$ ...
3
votes
0answers
88 views

The number of monotone Boolean functions

In the paper "The number of monotone Boolean functions" A. D. Korshunov calculates an asymptotic number of the number of monotone Boolean functions (see https://en.wikipedia.org/wiki/Dedekind_number)...
3
votes
0answers
65 views

Minimal algebraic degree of symmetric unit distance embedding of Heawood graph

I'm looking at embeddings of the Heawood graph in the plane as unit distance graph. Apparently the first such embedding was given by Gerbracht, 2009 and has algebraic (over the rationals) coordinates ...
4
votes
0answers
76 views

Random polyominoes containing $2\times2$ squares

The construction quoted in the question "How to sample a uniform random polyomino?" claims to produce a "uniform random polyomino". But apart from the mentioned possibility of getting stuck, it also ...
4
votes
2answers
130 views

Neighbourhood of a word and Levenshtein distance

The Levenshtein distance or Edit distance $$ lev(U,V) $$ between two strings $U$ and $V$ over a finite alphabet $\Sigma$ of size $ \left| \Sigma \right| = \sigma ,$ is the minimal number of insertions,...
0
votes
1answer
35 views

What is the shatter coefficient / VC - dimension of some hypothesis set?

Let $H:=\{h:\mathbb{N}_0^n \rightarrow \{0,1\}| h(x_1,\cdots,x_n) = \mathbb{1}_0(\sum_{i\in I}{x_i}-\sum_{j \notin I}{x_j}) \text{ for some } I \subset \{1,\cdots,n\}\}$ where $\mathbb{1}$ is the ...
1
vote
1answer
256 views

Some divisibility constraints in Frobenius coin problem

Let's say that the linear form $ax+by$ represents $n$ if $ax+by=n$ for some positive integer $x$ and $y$. Call a pair $(a,b)\in\Bbb N\times\Bbb N$ with $\mathsf{gcd}(a,b)=1$ excellent if linear form ...
4
votes
1answer
154 views

Sum of Young symmetrisers of a given shape

Preliminaries and notation: Let $n\in \mathbb{Z}_{>0}$ and $\lambda=(\lambda_1,\lambda_2,\dots,\lambda_s)\vdash n$ be a partition. Given a Young diagram of shape $\lambda$, we can associate it ...
0
votes
0answers
71 views

Variation on stones in buckets

This is a spinoff, see Collecting stones in n buckets. Frankly speaking my only motivation is that I became curious: what happens if one redistributes the stones into the same buckets? More ...
1
vote
1answer
47 views

How to generate a Latin square $M'$ in the same main class as $M \in \mathrm{LS}(9)$ which agrees with $L$ in the most cells?

I'm brainstorming an idea for storing a compressed list of main class representatives of Latin squares of order $9$. One way to compress the list would be to store one Latin square $L_1$, and for $i \...
4
votes
1answer
197 views

Collecting stones in n buckets

There are $n$ stones distributed in $n$ buckets (initially one stone in each bucket). At each step the content of each bucket is put in a random bucket, chosen independently out of a set of $n$ new ...
0
votes
0answers
43 views

How many different solutions does this cube puzzle have?

I designed a 4x4x4 soma cube in AutoCad and then built it with wood cubes. Now I want to know how many different solutions there are for it. Similar to the Bedlam Cube, there are twelve pentacube and ...
19
votes
1answer
1k views

Simplest form for sum of Binomial Expressions

How difficult is the problem of reducing the number of terms in a sum of binomial expressions? Formally: Given $a_1, a_2, a_3, … a_n$, and $b_1, b_2, b_3, ... , b_n$, where $a_i, b_i \in \mathbb{Z}$, ...
0
votes
1answer
259 views

How many subsets I of $\{1,\cdots,n\}$ exist?

How many subsets $I$ of $S:=\{1,\cdots,n\}$ exist such that $\sum_{i \in I} x_i \neq \sum_{j \in S-I} x_j$ for all $0 < x_1 < \cdots < x_n$? Let $b_n$ be this number. Then we are ...