# Questions tagged [co.combinatorics]

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

795 questions
2k views

747 views

1k views

### maximum size of intersecting set families

Suppose $n$ is a big number and $k\geq 2$. How many sets $S_1,\dots,S_m\subset [n]$ can we find such that (1) $|S_i| = k$ for all $i$, (2) $|S_i\cap S_j| \leq 1$ for all $i\ne j$. What's the maximum ...
319 views

### Inversion, Koszul duality, combinatorics and geometry

According to this MO answer Koszul duality is related to operations on generating series; 1) multiplicative inversion for quadratic algebras, 2) compositional inversion for quadratic operads, 3) ...
193 views

### Partition of 4-tuples

Some $4$-tuples of positive real numbers $(a_1,b_1,c_1,d_1),\dots,(a_n,b_n,c_n,d_n)$ are given, with all $a_i,b_i,c_i,d_i\leq 1$. Can we always partition $\{1,2,\dots,n\}$ into two subsets $X,Y$ so ...
232 views

### Spectrum of orthogonality graph (2)

The orthogonality graph, $\Omega(n)$, has vertex set the set of $\pm 1$ vectors of length $n$, with orthogonal vectors being adjacent. I am only interested when $4|n$, since otherwise $\Omega(n)$ is ...
1k views

### What is the largest number of k-element subsets of a given n-element set S such that…

Given a set S of n elements. What is the largest number of k-element subsets of S such that every pair of these subsets has at most one common element?
1k views

### Is every positive integer the permanent of some 0-1 matrix?

In the course of discussing another MO question we realized that we did not know the answer to a more basic question, namely: Is it true that for every positive integer $k$ there exists a balanced ...
30k views

### Notation for the all-ones vector [closed]

What's the most common way of writing the all-ones vector, that is, the vector, when projected onto each standard basis vector of a given vector space, having length one? The zero vector is frequently ...
3k views

### Status of the Hadamard Circulant conjecture

The following feels like a community wiki question, so I do it here: Recently we have heard of a new proof of the Circulant Hadamard conjecture of Ryser (a long standing difficult conjecture): ...
558 views

### Graphs with many edges avoided by Hamiltonian cycles

Let $G$ be a $3$-connected Hamiltonian graph with at least one edge that belongs to each H-cycle of $G$. Some authors (e.g. in the link given here) call such an edge an a-edge and an edge that belongs ...
385 views

### A Schur positivity conjecture related to row and column permutations

The problem Counting cycles after permuting within rows and columns reminds me of the following unpublished conjecture of mine. Let $D$ be any finite planar diagram (in the sense of Young diagram, ...
430 views

### Primes arising from permutations

Recently, Paul Bradley proved in arXiv:1809.01012 that for any positive integer $n$ there is a permutation $\pi_n$ of $\{1,\ldots,n\}$ such that $k+\pi_n(k)$ is prime for every $k=1,\ldots,n$ (cf. ...
252 views

### Counting some binary trees with lots of extra stucture

While working on some computations on Hilbert schemes, I came across the following combinatorial problem. Let $D(k,n)$ be the weighted number of binary trees (children are left/right) with $n$ ...
180 views

### Eigenvectors of a matrix with entries involving combinatorics

In the question Eigenvalues of a matrix with entries involving combinatorics No_way asked about eigenvectors of $n\times n$ matrix $M$ with entries \begin{eqnarray*} M_{ij}=(-1)^{i+j}F(n, l, i, j), \...
480 views

### Grassmann-Plücker relations for permanents

Let $K$ be a field, $1 \leq d \leq n$ integers and $V$ an $n$-dimensional vector space. The Grassmann-Plücker relations are quadratic forms on $\wedge^d V$ whose zero set is exactly the set of ...
586 views

### Known decomposition of $\bigwedge^k Sym^d \mathbb C^n$ in special cases?

Let $V = \mathbb C^n$. Consider the plethysm $\bigwedge^k Sym^d V$ as a representation of $GL(V)$. In what special cases (e.g., for what $k$, $d$, and $n$) is this representation's decomposition into ...