Skip to main content
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
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 …
passerby51's user avatar
  • 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 …
passerby51's user avatar
  • 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 …
passerby51's user avatar
  • 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 …
passerby51's user avatar
  • 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 …
passerby51's user avatar
  • 1,731