# Tag Info

Accepted

### Commutation classes of reduced decompositions of the longest element of the Weyl group with one element

The reduced words that are in their own commutation classes are: $s = [123\cdots(n-2)(n-1)(n-2)\cdots321][23\cdots(n-3)(n-2)(n-3)\cdots32][3\cdots(n-4)(n-3)(n-4)\cdots3]\cdots$ the reversal of $s$ (...

### Commutation classes of reduced decompositions of the longest element of the Weyl group with one element

I believe that for $n \geq 4$ there will be exactly $4$ such reduced words. One such word, call it $R_n$ can be constructed by starting with $s_{n-1}s_{n-2} \cdots s_2s_1s_2 \cdots s_{n-2}s_{n-1}$ and ...
• 2,623

### Counting number of linear transformation from a given subspace to another subspace of same dimension

Are you asking for linear transformations $F_2^n\to F_2^n$ that take $U$ to $W$, or just surjective linear transformations $U\to W$? If the latter, the number is $(q^k-1)(q^k-q)\cdots (q^k-q^{k-1})$: ...
• 45.8k

### Counting number of linear transformation from a given subspace to another subspace of same dimension

Recall that we can define a linear map by just defining where we send the basis vectors. So, to find how many surjective linear maps there are, we need to see how many ways can we take the basis ...
• 101
Accepted

### Why are these graphs coming from 9-dimensional alternating trilinear forms so symmetric?

The structure of the graph comes from a group structure on the set of rank-4 points! Apparently you can associate an Abelian surface to alternating trilinear forms in dimension 9, e.g., see The ...
1 vote
Accepted

• 4,933

### 'Trivial' lower bounds for pattern complexity of aperiodic subshifts

I'll try to do three dimensions for simplicity. I am on the bus and have to be very quick. Theorem. Suppose $X \subset A^{\mathbb{Z}^3}$ is a subshift, such that $\liminf_n \frac{P(n)}{n^2} = 0$. ...
• 5,376
Accepted

### Do all graphs with $n$ vertices and $m$ edges have a special property?

For $n=53$ and $m=113$, you can't even get close in general. Take 7 copies of $K_5$ and 3 copies of $K_6$, all disjoint. Remove any two edges; now you have 53 vertices and 113 edges. No complete ...
• 34.7k
1 vote

### Do all graphs with $n$ vertices and $m$ edges have a special property?

Let $\psi(n)\approx\sqrt{n}$ denote the positive solution to $x^2+2x=n$. Note that if $|V_1||V_2|+|V_1|+|V_2|>n$, then either $|V_1|\geq \psi(n)$ or $|V_2|\geq \psi(n)$. This implies that all ...
• 11

### How many ways to pick k integers with fixed sum and product

Let $B_k({\cal S},{\cal P},{\cal X})$ be a bound for the number of solutions for any $S\leq {\cal S}$, $P\leq {\cal P}$ and ${\cal X} \leq x_1 \leq x_2 \leq \dots \leq x_k$. Using Iverson's bracket ...
• 27.4k
Accepted

### Counting numerical semigroups by largest element of minimal generating set

A key observation is that two sets of generators $g, g'\subseteq [n]$ produce the same semigroup if and only if $\langle g\rangle \cap [n] = \langle g'\rangle \cap [n]$. Hence, the number of different ...
• 27.4k

### Derivative formula

Extensions of the Leibnitz rule to fractional calculus were investigated by Osler in the 1970s. See, e.g., "Fractional derivatives and special functions" by Lavoie, Osler, and Tremblay. One ...
• 8,531
1 vote
Accepted

### Number of sets of columns "connecting" top to bottom of a matrix

Quite similarly to my answer to your other question, we have $$c(h,n) \geq \binom{4n-h}m - h\binom{2n-h}m.$$ I'm not sure how good is this bound.
• 27.4k
1 vote
Accepted

### Number of couples of columns "connecting" top to bottom of a matrix

We can view (unordered) pairs of zeros in each row as covering the pairs of columns (and thus eliminating them from being counted by $c$). Since we want to minimize $c$, the more pairs are covered the ...
• 27.4k
Accepted

### One question on circulant $(-1,1)$-matrices

This is a question about a sequence $a(t)\in \{\pm 1\}$ of period $n$ with 2 level periodic autocorrelations, with the nontrivial autocorrelations identically equal to 1. All these problems have a ...
• 8,981

### Not very transitive actions

Generally any projective group $\mathrm{PGL}(2,\mathbb{F}_q)$ acting on the $q+1$ points of the projective line over $\mathbb{F}_q$ is sharply $3$-transitive. This gives infinitely many $3$-...
• 10.5k

• 90.8k
1 vote
Accepted

### The quantity of poset with a given number of pairs of incomparable elements

Yes. This is true. We shall prove this result by induction on $n$. Suppose that $n>0$. and $0\leq m\leq\binom{n}{2}$. If $m\leq\binom{n-1}{2}$, then there is some poset $X$ with $|X|=n-1$ and where ...
• 24.6k

### Existence of an infinite word with a predetermined asymptotic for the word complexity

Your function $n_w$ is usually called the word complexity function. There are several works on these possible asymptotics, though the question seems quite difficult and surprisingly little is known. ...
• 1,469
Accepted

• 1,165

### Two questions on infinite hypergraphs

To your second question, the answer is no, see problem 18.19 in P. Komjáth, V. Totik: Problems and Theorems in Classical Set Theory where they cite G. Elekes, G. Hoffmann: On the chromatic number of ...
• 17.6k
Accepted

### Representation of $\mathrm{AGL}(V)$ on the homology of the poset of affine subspaces of $V$

I suspect that Solomon, Louis The affine group. I. Bruhat decomposition. proves what you are looking for. Let $A_n(q)$ denote the poset of proper affine subspaces of $\mathbf{F}_q^n$. The only non-...
Accepted

### A linearly distributed version of the balls into bins problem

From the referenced paper, I am writing in terms of their variables, $k$ is the number of bins or type of coupons: Let $n_1$ be the time where the last of the missing events is observed. Let $n_2$ ...
• 8,981