# 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
1 vote
119 views

127 views

### Limit associated with two Beatty sequences that are not a Beatty pair

Suppose that $r>1$ and $s>1$ are irrational numbers, and let $a_n=\lfloor nr \rfloor$ and $b_n=\lfloor ns \rfloor$. Assume that $r$ and $s$ are numbers for which $\{a_n\}\cap\{b_n\}$ is ...
270 views

### Asymptotics of a quadratic recursion

Consider the sequence defined by \begin{align} c_0 &{}= 1 \\ c_n &{}= 2\,n\,c_{n-1}-\frac{1}{2}\sum_{m=1}^{n-1}c_m\,c_{n-m}. \end{align} How can you prove that it has the following asymptotics ...
39 views

### How sparse can a matrix mapping between sparse vectors be?

Let $s$ and $d$ be non-negative integers with $0\leq s<d$ and let $v,u\in \mathbb{R}^d$ be vectors satisfying the sparsity estimate $$\max\{\|u\|_0,\|v\|_0\}\leq d-s,$$ where, as usual, for any ...
97 views

### What is the rank sequence when you taking the smallest number that is no less than the average repeatedly?

This is the same problem at MSE. Since there is no answer (except one wrong deleted answer) there, I decided to post it here. This is a problem created by me, although it may appear/looks like a ...
44 views

### Maximize connectivity probability with a number of edges

We are given a graph $G$, whose edges are either open or closed. Initially all the edges are closed. For each edge $e$, if we choose to activate it, then after the activation, it becomes open with ...
52 views

### Graph reduction and combinatorial optimization

Crossposted at Theoretical Computer Science SE We are given a multigraph $G$. Consider two nodes $u$ and $v$ with multiple edges between them. Each elementary edge is associated with a metric called ...
142 views

132 views

### Reference request: maximal determinant of matrices with pairwise orthogonal rows and entries in $\{1, 0, -1\}$

We know that "Hadamard maximal determinant problem" concerns the largest determinant of a matrix of oder $n$ with entries in $\{-1,1\}$ or $\{0, 1\}$. For $n=4k$, it is the Hadamard ...
117 views

11k views

### Conceptual reason why the sign of a permutation is well-defined?

Teaching group theory this semester, I found myself laboring through a proof that the sign of a permutation is a well-defined homomorphism $\operatorname{sgn} : \Sigma_n \to \Sigma_2$. An insightful ...
1 vote
100 views

### How to distribute least number of $D$ card decks amongst $n$ people so that any $k$ people have a full deck and no $k-1$ people have a full deck

Decks are composed of 1 copy of each of $D$ unique cards. The set of cards is $C$ ($|C|=D$), the set of people is $P$ ($|P|=n\geq k$). Starting with a simpler case (dropping the $k-1$ restriction) One ...
225 views

### Cardinality of the maximum points of the determinant on matrices with entries in [-1, 1]

By multilinearity, the maximum of the determinant on matrices with entries in the interval [-1, 1] is attained at a {-1, 1}-matrix. By the following example, the maximum is attained at infinitely many ...
675 views

### The maximal subset of a finite field where the sum of any subset is non-zero

Given a finite field $\mathbb{F}_q$ with $q=p^m$ where $p$ is the characteristic. For any subset $S=\{a_1,\dots,a_n\}$ of $\mathbb{F}_q$, if any partial sum (i.e. the sum of elements in a non-empty ...
196 views

### Can we explicitly compute this "shift"-quantity over Boolean functions $u:\mathbb{F}_2^n\rightarrow \mathbb{F}_2$?

This question is a follow-up of this question. Let $\mathbb{F}_2=\{0,1\}$ be the field with two elements, and suppose that $n$ is odd. Question: Can we compute the exact minimum A:= \min_{u:\mathbb{...