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

7,207 questions
Filter by
Sorted by
Tagged with
53 views

### Differences of elements of a set of natural numbers (reference request)

Let $A$ be a subset of $[n] = \{1,2,\dots,n\}$. Define $\overline A = \{(i,j) : i, j \in A \text{ and } i > j \}$ and define $(i_1,j_1) \sim (i_2,j_2)$ if $i_1 - j_1 = i_2 - j_2$. This is ...
118 views

155 views

### Non-nesting matchings and Catalan numbers

It is well-known that the number of non-nesting perfect matchings on $2n$ points is given by the Catalan number $C_n$; see part (a) of the figure below. This is item e^5 in Stanley's list (http://www-...
80 views

97 views

### Asymptotics of the Steenrod algebra / $s$-partitions?

Recall that an $s$-partition is a partition of a natural number $n$ such that each part is of the form $2^r-1$. By a fundamental theorem of Milnor, the number $p_s(n)$ of $s$-partitions of $n$ counts ...
154 views

### Bilinear recurrence relation between even Bernoulli numbers

Throughout this question $n$ is a positive integer greater than 1. Consider the following well-known identity by Euler, $$\sum_{k=1}^{n-1} \binom{2n}{2k}B_{2k}B_{2n-2k}=-(2n+1)B_{2n}.$$ Rather ...
58 views

### Singular values and the chromatic number

What relation, if any, is there between the singular values of the adjacency matrix ( or possibly incidence matrix) of a simple graph and its chromatic number. Typically, do we have Hoffmann type, or ...
126 views

### Map on class of all finite posets coming from maximal sized antichains

Let $P$ be a finite poset. Let $\mathcal{A}$ denote the set of antichains of $P$. Equip $\mathcal{A}$ with a partial order $\preceq$ whereby $X \preceq Y$ means for all $x \in X$ there exists $y \in Y$...
71 views

### Arzela-Ascoli-analogue statement over a given cardinality of discrete space

(I think there would be better title for my question. If there is a good idea on the title, please let me know.) Consider the following statement: Let $A$ be a set (with the discrete topology, if ...
164 views

### Cartan determinants of subsets

Let $n \geq 3$ be fixed. We associate to every subset $S \subseteq \{1,...,n-1 \}$ a number, which we call Cartan determinant of $S$ (see the end of this post for a representation theoretic background)...
190 views

### Nontrivial expansion in sumsets

Let $A \subset \mathbb{Z}/p$, let $f$ be a function on $\mathbb{Z}/p$ and let $B:=\{f(a): a \in A\}$. Can we conclude that $|A+B|$ is large if $f$ is a sufficiently "nice" function? For instance say ...
86 views

Suppose $G$ is a group and $S \subset G$ is its finite subset. Let’s define the generating graph of $G$ in respect to $S$ as $Gen(G, S)$ - a graph $\Gamma(V, E)$, where $V = S$ and $E = \{(a, b) \in S ... 1answer 238 views ### “Non-associative” standard polynomials I saw somewhere (I appreciate if anyone has any references to proof of this fact) that if$A$is a finite dimensional associative algebra such that$\textrm{dim}(A)<n$, then$A$satisfies the ... 0answers 72 views ### Flag$f$-vectors of CW-complexes Hidden away in the appendix of this nice paper by Björner and Kalai, they give a clean description of$f$-vectors that can arise from regular CW-complexes in terms of truncations of the Euler-Poincaré ... 0answers 129 views ### Tradeoffs in translation-invariant tilings of$\mathbb{R}^3$Suppose I tile$\mathbb{R}^3$in a ($\mathbb{Z}^3$-)translation-invariant manner. If we insist on the tiling being regular, then we are left with only the cubic tiling. However, suppose that we ... 0answers 82 views ### Terminology for set systems: “trace” or “projection”? Although the following question is not in itself mathematical, it is the expertise/breadth of the research community in mathematics that I wish to appeal to, beyond the filtered/trained search results ... 2answers 169 views ### Number of nonequivalent weight functions on a set of$n$elements For a finite set$S$of$n$elements, say a weight function is a function$f \colon S \to \mathbb{R}$. For any subset$T \subseteq S$, define$f(T) = \sum _{x \in T} f(x)$. Define two weight functions ... 0answers 58 views ### The degree of a (combinatorial) selfmap If$f$is a map from a finite set to itself, is there any widely accepted definition of the "degree" of$f$? I would like to define deg$f$as the quantity discussed in Quantifying the ... 1answer 28 views ### Simple balance incomplete block design, (complete graph clique decomposition) I am trying to find methods to construct a$(n,k,1)$-BIBD with large$n$and$k$. Basically, I'm wondering if there's an established method to create as many sets of size$k$from elements$\{1, ..., ...
I would like to classify the sets of integers $a_{1},...,a_{n}$ that satisfy the following two equations. $$\sum_{k=1}^{n}a_{k}\equiv 0\mod 2$$ $$\sum_{i\neq j}a_{i}a_{j}=0$$ For example, if $n=3$, I ...