# Tagged Questions

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

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$ ...
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 ...
354 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 ...
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)$ ...
136 views

182 views

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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, ...
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 ...
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 ...
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 ...
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 ...
105 views

114 views

### Singular Locus of a Schubert variety

I am trying to compute the singular locus of the schubert variety $X_w$ in $G_{2,7}$ where $w=(4,7) \in I_{2,7}$. Following the notation in the book "The Grassmannian Variety: Geometric and ...
215 views
+150

A covering of a non-empty set $X$ is a collection ${\cal U} \subseteq ({\cal P}(X)\setminus\{\emptyset\})$ such that $\bigcup {\cal U} = X$. If ${\cal U}$ is a covering of $X$ then a function $f:{\cal ... 1answer 148 views ### Does an expander remain an expander after removing few vertices and edges? Consider a sequence of expander graphs ($G_n$); say$G_n$has$n$vertices. Remove$o(n)$vertices (and the edges emanating from these vertices) and cut$o(n)$edges. Call$G'_n$the largest connected ... 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 ... 1answer 148 views ### How many edges can be added to two circles before the graph becomes Hamiltonian? Start with two$n$-circles$(v_1\cdots v_n)$and$(w_1\cdots w_n)$of vertice sets$V$and$W$, where$n\ge 5$. Add a number of vertex-disjoint edges between$V$and$W$(thus no chords) in a way ... 1answer 382 views ### Three dimensional representations of Alternating group The alternating group$A_5$has$2$irreducible representation of degree$3$. The characters for these representations have irrational values. I guess the ring of invariants of these representations ... 1answer 182 views ### An extremal problem on matrices Is it possible to determine (or give bounds for) the following extremal problem: Let$k,m,r$be positive integers such that$k,m \geq r$. What is the least number$n$such that for any$r \times n$... 1answer 83 views ### Probability of collision of some family of hash functions Given$x$and$y$in$\mathbb{R}$, and let$\mathcal{H} = \{ h \mid \mathbb{R} \to \mathbb{N} \}$be a family of hash functions where$ h(x) = \left\lfloor x + \sum^C_{i=1} U_i \right\rfloor$for some ... 1answer 84 views ### Critical coverings of$\omega$A covering of a non-empty set$X$is a collection${\cal U} \subseteq ({\cal P}(X)\setminus\{\emptyset\})$such that$\bigcup {\cal U} = X$. If${\cal U}$is a covering of$X$then a function$f:{\cal ...
Given any natural number $N = a_{n}a_{n-1}\ldots a_{1}$, we're going to define its digits-partition as the next set $D_{N} = \bigcup_{j=1}^{n}\bigcup_{k=1}^{p(a_{j})}\{(P_{k},j)\}$, where each pair \$(...