Call a family $F$ of subsets of $S=\{1,2,\ldots,n\}$ distinguishing if for every two distinct subsets $A,B$ of $S$ there exists $X\in F$ so that $|A \cap X|\ne |B \cap X|$. Show that there exists such a distinguishing family $F$ of $S$ of size $|F | \leq \dfrac{(2 + o(1)) n}{\log_3n}$, where $o(1)$ is a quantity […]

Suppose a simple graph $G$. Now consider probability space $G(v;p)$ where $0\leq p\leq 1$ and $v$ vertices. I want to calculate globally-determined properties of $G(v;p)$ such as connectivity and expected value of indicator function $$\mathbb E_{p\sim [0,1]^n}(\phi(G))$$ in terms of st-connectedness where $p$ follows let say uniform distribution. I want to understand which area investigates […]

Let $G = (V, E)$ be a cycle of length $4n$ and let $V = V_1 \cup V_2 \cup … \cup V_n$ be a partition of its $4n$ vertices into n pairwise disjoint subsets, each of cardinality 4. Is it true that there must be an independent set of $G$ containing precisely one vertex from […]

Intereting Posts

To what extent are the Jordan-Chevalley and Levi Decompositions compatible.
A curious coincidence for Wroblewski's solutions to $1^4+x_2^4+x_3^4+x_4^4+x_5^4 = y_1^4$
Interchanging the order of integration in an infinite product measure
Prove that there exists an $n\in\mathbb{Z}\cup\left\{-\infty,+\infty\right\}$ such that… (Dynamics)
$\tbinom{2p}{p}-2$ is divisible by $p^3$
Do expressions like $(-1)^{2/3}$ show up naturally in pure or applied math?
Solving the recurrence relation $T(n)=T(n-1)+cn$
Is this way of teaching how to solve equations dangerous somehow?
When is a recurrence relation linear
Question about the “Cat in the Hat” problem
Orthonormal Basis for Hilbert Spaces
The proof of the Helmholtz decomposition theorem through Neumann boundary value problem
If $f$ continuous differentiable and $f'(r) < 1,$ then $x'=f(x/t)$ has no other solution tangent at zero to $\phi(t)=rt$
Infinite product of sinc functions
What is the maximum point for which number of way to reach is given