## New answers tagged co.combinatorics

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

- 106

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

- 2,623

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

- 45.8k

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

- 291

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

- 34.7k

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

- 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

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

- 27.4k

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

- 27.4k

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.

- 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

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

- 24.6k

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

- 1,469

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

- 198

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

- 4,468

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

- 1,493

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

- 4,468

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

- 1,165

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

- 361

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!

Community wiki

Top 50 recent answers are included

#### Related Tags

co.combinatorics × 9704graph-theory × 2018

nt.number-theory × 1059

reference-request × 913

pr.probability × 729

discrete-geometry × 521

rt.representation-theory × 462

linear-algebra × 452

gr.group-theory × 416

enumerative-combinatorics × 320

algorithms × 303

graph-colorings × 303

permutations × 298

additive-combinatorics × 272

sequences-and-series × 268

ag.algebraic-geometry × 253

partitions × 240

polynomials × 237

binomial-coefficients × 234

mg.metric-geometry × 224

matrices × 220

convex-polytopes × 220

computational-complexity × 217

generating-functions × 174

finite-groups × 170