Skip to main content
MathOverflow

Return to Question

minor clarifications
Source Link
blt
blt
  • 1.2k
  • 1
  • 10
  • 13

Fix a positive integer $N$ and a real $\epsilon>0$. I'll write $[N]$ for the set $\{1,\dots,N-1,N\}$, $\mathcal{P}X$ to denote the power set of a set $X$, and $\#X$ to denote the number of elements of a finite set $X$.

Suppose $\mathcal{S}\subset \mathcal{P}[N]$ is a set-system which satisfies the following 'sparseness/uniformity' property: for every $j\in[N]$, we have that

$$\#\{X\in\mathcal{S}|j\in X\} \leq \epsilon\,\#\mathcal{S}$$

We could paraphrase this property as: for each $j$ in $[N]$, if we pick an element of $\mathcal{S}$ at random, the chance that it contains $j$ is at most $\epsilon$. Very roughly: "$\mathcal{S}$ is not concentrated anywhere".

As an example, we could take $\mathcal{S}$ to be all the subsets of $[N]$ containing exactly $\lfloor \epsilon N \rfloor$ elements.

Now fix an integer $k$. We'd like to pick a $k$-element subset $\mathcal{A}\subset\mathcal{S}$ which is 'still not particularly concentrated anywhere', in the sense that there exists some $R$ such that for each $j$ in $[N]$, $$\#\{X\in\mathcal{A}|j\in X\} \leq R$$

What's the smallest $R$ (in terms of $N$, $\epsilon$ and $k$) for which this will always be possible, however $\mathcal{S}$ was chosen?

Obviously, $R=k$ is possible; the question is how much better than this one can do! Heuristically, it looks like for $k$ smaller than about $\log N/(-\log\epsilon)$ you need to take $R=k$, but for $k$ larger than this but smaller than $1/\epsilon$ (if there are any such $k$) you can take something like $R=\log N/(-\log k\epsilon)$ and still be OK. But this is based on very rough heuristics, so is quite possibly completely unreliable.

It seems like this must be a routine or at least well-studied problem, but I don't know what search terms to use to find the literature onthat would tell me how to solve it, since I'm not an extremal combinatorialist by trade.

I'd be very happy with just an asymptotic solution. In the applications I have in mind, $N$ should be 'large' (say: growing like $10^n$ for some parameter $n$), while $\epsilon$ should be small (going to zero like say $2^{-n}$), and I'm interested in cases where $k$ is something roughly polynomial in $n$.

Fix a positive integer $N$ and a real $\epsilon>0$. I'll write $[N]$ for the set $\{1,\dots,N-1,N\}$, $\mathcal{P}X$ to denote the power set of a set $X$, and $\#X$ to denote the number of elements of a finite set $X$.

Suppose $\mathcal{S}\subset \mathcal{P}[N]$ is a set-system which satisfies the following 'sparseness/uniformity' property: for every $j\in[N]$, we have that

$$\#\{X\in\mathcal{S}|j\in X\} \leq \epsilon\,\#\mathcal{S}$$

We could paraphrase this property as: for each $j$ in $[N]$, if we pick an element of $\mathcal{S}$ at random, the chance that it contains $j$ is at most $\epsilon$. Very roughly: "$\mathcal{S}$ is not concentrated anywhere".

As an example, we could take $\mathcal{S}$ to be all the subsets of $[N]$ containing exactly $\lfloor \epsilon N \rfloor$ elements.

Now fix an integer $k$. We'd like to pick a $k$-element subset $\mathcal{A}\subset\mathcal{S}$ which is 'still not particularly concentrated anywhere', in the sense that there exists some $R$ such that for each $j$ in $[N]$, $$\#\{X\in\mathcal{A}|j\in X\} \leq R$$

What's the smallest $R$ (in terms of $N$, $\epsilon$ and $k$) for which this will always be possible, however $\mathcal{S}$ was chosen?

Obviously, $R=k$ is possible; the question is how much better than this one can do! Heuristically, it looks like for $k$ smaller than about $\log N/(-\log\epsilon)$ you need to take $R=k$, but for $k$ larger than this but smaller than $1/\epsilon$ (if there are any such $k$) you can take something like $R=\log N/(-\log k\epsilon)$ and still be OK. But this is based on very rough heuristics, so is quite possibly completely unreliable.

It seems like this must be a well-studied problem, but I don't know what search terms to use to find the literature on it, since I'm not an extremal combinatorialist by trade.

I'd be very happy with just an asymptotic solution. In the applications I have in mind, $N$ should be 'large' (say: growing like $10^n$ for some parameter $n$), while $\epsilon$ should be small (going to zero like say $2^{-n}$), and I'm interested in cases where $k$ is something roughly polynomial in $n$.

Fix a positive integer $N$ and a real $\epsilon>0$. I'll write $[N]$ for the set $\{1,\dots,N-1,N\}$, $\mathcal{P}X$ to denote the power set of a set $X$, and $\#X$ to denote the number of elements of a finite set $X$.

Suppose $\mathcal{S}\subset \mathcal{P}[N]$ is a set-system which satisfies the following 'sparseness/uniformity' property: for every $j\in[N]$, we have that

$$\#\{X\in\mathcal{S}|j\in X\} \leq \epsilon\,\#\mathcal{S}$$

We could paraphrase this property as: for each $j$ in $[N]$, if we pick an element of $\mathcal{S}$ at random, the chance that it contains $j$ is at most $\epsilon$. Very roughly: "$\mathcal{S}$ is not concentrated anywhere".

As an example, we could take $\mathcal{S}$ to be all the subsets of $[N]$ containing exactly $\lfloor \epsilon N \rfloor$ elements.

Now fix an integer $k$. We'd like to pick a $k$-element subset $\mathcal{A}\subset\mathcal{S}$ which is 'still not particularly concentrated anywhere', in the sense that there exists some $R$ such that for each $j$ in $[N]$, $$\#\{X\in\mathcal{A}|j\in X\} \leq R$$

What's the smallest $R$ (in terms of $N$, $\epsilon$ and $k$) for which this will always be possible, however $\mathcal{S}$ was chosen?

Obviously, $R=k$ is possible; the question is how much better than this one can do! Heuristically, it looks like for $k$ smaller than about $\log N/(-\log\epsilon)$ you need to take $R=k$, but for $k$ larger than this but smaller than $1/\epsilon$ (if there are any such $k$) you can take something like $R=\log N/(-\log k\epsilon)$ and still be OK. But this is based on very rough heuristics, so is quite possibly completely unreliable.

It seems like this must be a routine or at least well-studied problem, but I don't know what search terms to use to find the literature that would tell me how to solve it, since I'm not an extremal combinatorialist by trade.

I'd be very happy with just an asymptotic solution. In the applications I have in mind, $N$ should be 'large' (say: growing like $10^n$ for some parameter $n$), while $\epsilon$ should be small (going to zero like say $2^{-n}$), and I'm interested in cases where $k$ is something roughly polynomial in $n$.

Source Link
blt
blt
  • 1.2k
  • 1
  • 10
  • 13

If we take a small subset of a sparse/uniform set system, how uniform can we arrange for the subset to be?

Fix a positive integer $N$ and a real $\epsilon>0$. I'll write $[N]$ for the set $\{1,\dots,N-1,N\}$, $\mathcal{P}X$ to denote the power set of a set $X$, and $\#X$ to denote the number of elements of a finite set $X$.

Suppose $\mathcal{S}\subset \mathcal{P}[N]$ is a set-system which satisfies the following 'sparseness/uniformity' property: for every $j\in[N]$, we have that

$$\#\{X\in\mathcal{S}|j\in X\} \leq \epsilon\,\#\mathcal{S}$$

We could paraphrase this property as: for each $j$ in $[N]$, if we pick an element of $\mathcal{S}$ at random, the chance that it contains $j$ is at most $\epsilon$. Very roughly: "$\mathcal{S}$ is not concentrated anywhere".

As an example, we could take $\mathcal{S}$ to be all the subsets of $[N]$ containing exactly $\lfloor \epsilon N \rfloor$ elements.

Now fix an integer $k$. We'd like to pick a $k$-element subset $\mathcal{A}\subset\mathcal{S}$ which is 'still not particularly concentrated anywhere', in the sense that there exists some $R$ such that for each $j$ in $[N]$, $$\#\{X\in\mathcal{A}|j\in X\} \leq R$$

What's the smallest $R$ (in terms of $N$, $\epsilon$ and $k$) for which this will always be possible, however $\mathcal{S}$ was chosen?

Obviously, $R=k$ is possible; the question is how much better than this one can do! Heuristically, it looks like for $k$ smaller than about $\log N/(-\log\epsilon)$ you need to take $R=k$, but for $k$ larger than this but smaller than $1/\epsilon$ (if there are any such $k$) you can take something like $R=\log N/(-\log k\epsilon)$ and still be OK. But this is based on very rough heuristics, so is quite possibly completely unreliable.

It seems like this must be a well-studied problem, but I don't know what search terms to use to find the literature on it, since I'm not an extremal combinatorialist by trade.

I'd be very happy with just an asymptotic solution. In the applications I have in mind, $N$ should be 'large' (say: growing like $10^n$ for some parameter $n$), while $\epsilon$ should be small (going to zero like say $2^{-n}$), and I'm interested in cases where $k$ is something roughly polynomial in $n$.