New answers tagged

9 votes
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$ (...
7 votes

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

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})$: ...
0 votes

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
8 votes
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

Graphs with $n$ vertices and $m$ edges and more probable property

There is a $C_4$-free bipartite graph $B$ with 19 vertices on one side, 20 vertices on the other side, and 92 edges. Its vertices have degree 4 or 5, so it is easy to find a path $P$ of 21 edges in $...
2 votes
Accepted

Recombining set elements with no duplicated pairing of elements

Let $\Sigma$ be an set of cardinality $e$. Then this problem is equivalent to selecting $se$ vectors from $\Sigma^s$ such that the minimum Hamming distance is $s−1$. (To see this, take $S_i = \{i\} \...
  • 4,933
4 votes

'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
3 votes
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 ...
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
3 votes

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 ...
3 votes
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 ...
0 votes

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.
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 ...
5 votes
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
9 votes

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
0 votes

A question on the Laurent phenomenon

This is a simpler example than my previous answer. Define two integer sequences with initial values $\;u_1 = -2,\; v_1 = 1\;$ and joint recursions $$ u_{n+1} = - u_n^2 + 3u_nv_n - v_n^2, \qquad v_{...
  • 2,044
11 votes
Accepted

Not very transitive actions

According to Theorem 4.11 of Peter Cameron's book `Permutation Groups' it follows from the classification of finite simple groups that the only finite 6-transitive groups are (some of the) symmetric ...
  • 2,929
1 vote

Determinant with factorials is not 0?

A direct proof of T. Amdeberhan's identity (1) is as follows: we have $(i+j+t)!=(i+t)! f_j(i)$, where $f_j(x)=(x+1)(x+2)\ldots (x+j)$. Thus $$ \det ((i+j+t)!)_{0\leqslant i,j\leqslant n-1}=\prod_{i=0}^...
  • 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 ...
3 votes

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. ...
2 votes
Accepted

Density of “diagonal sets” in amenable groups

The answer to your question as stated is "no", but a variant of it is true (see the proposition below). Proof that the answer is "no": Let $(F_n)$ be the Følner sequence in $\...
1 vote
Accepted

Computational complexity and commuting functions, examples and conjectures

This is not a proper answer. I will give a construction of a pair of functions $f,g$ assuming the access to some cryptographic function $e$ that probably should form a counterexample for Proposition ...
10 votes
Accepted

Which finite projective planes can have a symmetric incidence matrix?

The key word here is "polarity". A polarity of a projective plane with point set $P$ and line set $L$ is a map $\pi$ from $P \cup L$ to itself mapping points to lines and lines to points, ...
  • 5,479
14 votes
Accepted

When the Littlewood-Richardson rule gives only irreducibles?

The answer is Yes, but this requires some elaboration. Knutson-Tao-Woodward prove Fulton's conjecture in $\S$6.1. In principle, you can follow the approach by De Loera-McAllister or Mulmuley-...
  • 16k
1 vote
Accepted

Algorithm for finding a minimum weight circuit in a weighted binary matroid

The problem is NP-hard (even in the unweighted case) via a well-known connection to coding theory. Namely, if $A$ is the parity check matrix of a binary linear code $C$, then the distance of $C$ is ...
  • 29.2k
-2 votes

What is the best lower bound for 3-sunflowers?

This is the same construction as the above comment. But with an attempt at more detail at each step for anyone who may need. Let F be an arbitrary 3 sunflower free set. Expand each element of its ...
  • 1
5 votes
Accepted

Two questions on infinite hypergraphs

The answer to the first question is also no, by a minor modification of the proof of the Elekes-Hoffmann result cited in the answer to the second question. In fact, we get the following: Theorem There ...
5 votes
Accepted

Computational complexity and commuting functions

There is a counterexample to Proposition 1 iff $\mathsf{P}\ne\mathsf{PSPACE}$. The idea is to make a pair $f,g$ such that on certain inputs iterations of them individually are trivial, but their ...
2 votes
Accepted

How to find an example of a union-closed family with two given properties

Not a good example, but it might hint for a better one. Take two integers $N=2k+1,M$. Let the basis sets be $\{x,x+1,...,x+k\},1\leq x\leq N$, taken modulo $N$ (identify $N\equiv 0$) and $\{1,2,...,N,...
5 votes

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
2 votes
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-...
4 votes
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
6 votes

Status of Barany's conjecture?

2022 update Bárány's conjecture seems to have been answered in the affirmative by Joshua Hinman in a rather short paper of only 8 pages: Joshua Hinman. "A Positive Answer to Bárány's Question on ...
  • 11k
1 vote

If $X = X_1 \cup \cdots \cup X_n$ is shellable, then is $(X_1 \cup \cdots \cup X_k)\cap X_{k+1}$ shellable?

The answer is yes, as indicated in the comments. Thanks to WlodAA!

Top 50 recent answers are included