Search Results

Consider the set of rooted labeled trees in which each node may have up to $d$ children. It is well known that the number of such trees with $\leq v$ vertices is (approximately) $(ed)^v$ and that the …

Suppose $d$ is a constant $< n^2$, and $m > n$. I have a kind of factorial function where I subtract $d$ from each pair of terms. Is there any simple upper bound on $$ P = ( m (m-1) - d) \times ( (m- …

Suppose $k$ is fixed. Consider a set $X$ of subsets of the ground set $\{1, \dots, k \}$, with the following property: there is some ordering of the elements of $X$, as $X = \{ x_1, \dots, x_n \}$, su …

Consider a triangle-free graph $G$, in which the vertices are partitioned in blocks $V = A_1 \sqcup \dots \sqcup A_k$. $G$ has the property that, for each $i \leq j$, each vertex in $A_i$ has at most …

Let $G$ be a graph with $m$ edges and $n$ vertices. For a fixed integer $s \leq n$, what lower bound can be shown on the number of independent sets with $s$ vertices? Letting $d$ denote the average d …

Matroids provide a unified framework for many efficient computer algorithms. For example, finding the maximum-weight element of a matroid can be done with a greedy algorithm and access to a oracle for …

Consider a set $A \subseteq [n] \times [n]$ with $|A| = a = \alpha n$ for some $\alpha \in [0,1]$. Suppose we select a permutation $\pi \in S_n$ uniformly at random. This permutation $\pi$ can also be …

Consider a rank-$r$ hypergraph $H = (V,E)$. I would a lower-bound of the following form: $$ \sum_{e \in E} \frac{ \sum_{v \in e} \text{deg}(v) }{\max_{v \in e} \text{deg}(v)} \geq c \sum_{v \in V} \te …

For a connected graph $G$, let $N_i$ be the number of connected subgraphs of size $i$. The vector $\langle N_0, N_1, \dots \rangle$ is also known as the $f$-vector for the graph. As a superset of a c …

All the references I can find to Covering Set appear to be algorithmic. Is there are any reference for the simple existential question --- Suppose we have $k$ sets $X_1,…,X_k$ which are subsets of a …

Given fixed values for $d \leq k \leq v$. I would like to find a set $B$ of $d$-sets of $[v]$ with the following properties: Every $k$-set of $[v]$ contains at least one element of $B$ Every elemen …

The following statement seems very plausible: If $G$ is a triangle-free graph of degeneracy $d$, then $$ \chi_f(G) \leq O(\frac{d}{\log d}) $$ where $\chi_f$ is the fractional chromatic number. This …