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

9,275 questions
Filter by
Sorted by
Tagged with
203 views

122 views

### How to find an optimal sequence of merging operations?

Given a set of items, each characterized by a quality $q_i\in(0,1)$. We can merge two items of quality $q_i$ and $q_j$ to a single item $k$ of quality $q_k=f(q_i,q_j)$, where $f$ is increasing in $q_i$...
1 vote
115 views

### Steiner tree subject to non-trivial constraint

Given a edge-weighted transportation network modeled as a graph. A source node $s$ needs to send an object to a set of $k$ destination nodes $t_i$, $1\le i\le k$. For the transportation, $s$ needs to ...
124 views

### Number of "half symmetries" of a finite subset of $\mathbb S^1$

Suppose $X\subset \mathbb S^1$ is a finite subset of the group $\mathbb S^1=\mathbb R/\mathbb Z$. We say that $t\in \mathbb S^1$ is a half symmetry of $X$ if $|(X+t)\cap X|>|X|/2$. Question. Can ...
129 views

### Polynomial count varieties and affine paving (e.g., determinantal varieties)

Let $X$ be a variety defined over $\mathbb{Z}$, $X_{\mathbb{F}}$ be the base change $X\times_{\mathrm{Spec}(\mathbb{Z})} \mathrm{Spec}(\mathbb{F})$. We say $X$ is of polynomial count if there is a ...
339 views

1 vote
84 views

202 views

### Alon-Füredi for homogeneous polynomials

A theorem of Alon and Füredi says that if $A$ and $B$ are finite, nonempty subsets of the field $\mathbb F$, and if a polynomial $P(x,y)\in\mathbb F[x,y]$ vanishes on all, but exactly one point of the ...
588 views

### Indecomposable contracting maps on the integers

$\def\ZZ{\mathbb{Z}}$Call a function $f : \ZZ \to \ZZ$ "contracting" if $$|f(j) - f(i)| \leq |j-i|$$ for all $i$, $j \in \ZZ$. The contracting functions form a monoid under composition; call ...
121 views

### Can connectivity be less than min cut/degree?

Suppose we have a graph with min-cut $\lambda$ and minimum degree $> \lambda$. Is it possible for there to be a vertex that is at most $\lambda$-connected to every other vertex in the graph? ...
99 views

### An efficient generalized algorithm to obtain an arbitrary element of a lexicographically ordered tuple of all balanced $l$-bit binary sequences

Assuming that $l>1$ is even, an $l$-bit binary sequence $b$ is balanced if and only if the number of zeroes in $b$ is equal to $l/2$. Let $T_l$ denote a lexicographically ordered tuple of all ...
136 views

232 views

432 views

### Explicit expression for recursive sums

Let $t_1,t_2,\dots,t_k$ be non-negative integers. Can the following sum $$f_k(t_1,t_2,\dots,t_k):=\sum_{j_1=0}^{t_1} \sum_{j_2=0}^{t_2+j_1} \sum_{j_3=0}^{t_2+j_2} \dots \sum_{j_k=0}^{t_k+j_{k-1}} 1$$ ...
Let $A = (a_{i,j})$ be a double stochastic matrix with positive entries. That is, all entries are positive real numbers, and each row and column sums to one. A permanent of a matrix $A = (a_{i,j})$ is ...
Let $X\neq \emptyset$ be a set. We say $C \subseteq {\cal P}(X)$ is a cover of $X$ if $\bigcup C = X$. For covers $C, D$ of $X$ we say that $C$ is more efficient than $D$ if \$|C\setminus D| < |D \...