# Tagged Questions

Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.

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

85 views

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 ...
5k views

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!
139 views

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 ...
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 ...
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 ...
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?
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 ...
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, ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$ ...
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)...
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 ...
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 ...
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,...
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 ...
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 ...
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 ...