# Tagged Questions

**7**

votes

**3**answers

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

**5**

votes

**2**answers

95 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

**1**answer

105 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

**0**answers

30 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

**2**answers

162 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

**1**answer

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

**2**answers

215 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

**0**answers

77 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

**2**answers

182 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

**1**answer

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

**6**answers

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

**1**answer

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

**0**answers

89 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

**1**answer

243 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!

**2**

votes

**2**answers

136 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

**1**answer

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

**1**answer

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

**1**answer

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

**7**

votes

**0**answers

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

**4**

votes

**4**answers

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++, ...

**-2**

votes

**0**answers

23 views

### weighted restricted integer compositions and extended binomial coefficients [on hold]

proof of
d_{S,f}(n,k) = \binom{k}{n}{(f(s)){s\in S}}

**6**

votes

**1**answer

128 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

**0**answers

46 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

**1**answer

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

**1**answer

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

**1**answer

130 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

**0**answers

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

**3**answers

291 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

**0**answers

192 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

**0**answers

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

**0**answers

96 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

**0**answers

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

**3**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**0**answers

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

**0**answers

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

**2**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**3**

votes

**1**answer

129 views

### Choosing $K$ “centers” from the space of permutations

Let $\Pi$ denote the space of all permutations of $\{1,\dots,n\}$, and let $d(\cdot,\cdot)$ be a metric on $\Pi$. Suppose I am given a large integer $K$ and I have to select $K$ permutations $\pi_1,\...

**5**

votes

**0**answers

197 views

### Partitions of $\mathbb{F}_2^n$ related to perfect $1$-error correcting binary codes

Edit. After a computer search found an example for $n=8$, I've rephrased my original question as a conjecture.
This question is motivated by the existence of perfect $1$-error correcting binary codes,...