Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with co.combinatorics
Search options not deleted
user 36687
Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.
6
votes
3
answers
258
views
Algorithm to decide if the union of a set system covers the power set
Assume that we have a set system $\mathfrak T = \{\mathcal T_1, \mathcal T_2, \dots, \mathcal T_N \}$ where each $\mathcal T_k$ is a collection of subsets of $[n] := \{1,\dots,n\}$ of the form
$$ \ma …
- 1,731
6
votes
2
answers
270
views
Counting a class of backtracking walks
We are interested in a class of walks on the complete graph on $[n] = \{1,2,\dots,n\}$. A walk of length $k$ is an ordered tuple of directed edges
$$
((i_1,i_2),(i_2,i_3),\ldots,(i_k,i_{k+1}))
$$
wher …
- 1,731
4
votes
1
answer
251
views
An optimization involving (random) graphs
Suppose we have a graph on $n$ nodes. We would like to assign to each node either a $+1$ or a $-1$. Call this a configuration $\sigma \in \{+1,-1\}^n$. The number of $+1$s that we have to assign is ex …
- 1,731
2
votes
1
answer
1k
views
A covering problem for the Hamming cube
Consider the set of all $k$-subsets of $\{1,\dots,n\}$, naturally identified with a subset $A$ of $\{0,1\}^n$ where each element has exactly $k$ ones. Is there a sharp bound known for $\epsilon$-cover …
- 1,731
0
votes
Counting a class of backtracking walks
Based on the answer and comments by @Corentin B, I believe the following upper bound holds:
$$
C_{k,t}^n \leq D_t \binom{n-1}{t}\cdot t! \cdot S(k/2,t)
$$
for $k \in 2 \mathbb N$ and $t \le k/2$, wher …
- 1,731