To address the problem, we start by analyzing pairwise independent Bernoulli variables and their structure. Pairwise independent variables imply that each pair of variables is independent, but not necessarily the entire set. We need to show that we can extract a complete subset (one where every binary vector has positive probability) of size at least ( t+1 ), where ( t ) is the largest integer...

Counterexample (valid for every n ≥ 4)

Fix n ≥ 4 and define a probability space with n+1 atoms ω0, ω1, …, ωn having probabilities

• P(ω0) = s := 1/(n−1)^2,
• P(ωi) = r := (n−2)/(n−1)^2 for i = 1, 2, …, n. Note that s + n r = 1.

Define Bernoulli variables X1, …, Xn by

• Xi(ω0) = 1 for every i,
• Xi(ωi) = 1 and Xj(ωi) = 0 for j ≠ i.

Equivalently, the random vector X = (X1,…,Xn) takes the value 1^...

Extracting a Complete Subset from Pairwise Independent Bernoulli Variables

I'll prove that if are pairwise independent Bernoulli variables, then we can extract a complete subset of cardinality at least , where is the largest integer satisfying .

Understanding the Problem

First, let's clarify what a "complete" subset means: a subset of variables ...

This is an excellent and deeply insightful question. Your intuition, particularly the analogy to the phase transition in Erdős-Rényi random graphs, is spot on and reflects the modern perspective on these kinds of problems in geometric group theory and combinatorics.

Let's break down the answer into what is known, what is conjectured, and why your proposed formula is so plausible.

Summary of ...

A subset is complete if for every possible...

Here is a concise summary of what is known and why the general claim remains open.

1. Restatement of the problem
   You have non‐constant Bernoulli’s (X_1,\dots,X_n), pairwise independent. One calls a sub‐collection [ X_{i_1},\dots,X_{i_d} ] “complete’’ if its joint law charges every bit‐string in ({0,1}^d). The conjecture is that from any (n) pairwise‐independe...

Looking at this problem, I need to prove or disprove that from pairwise independent Bernoulli variables, we can extract a complete subset of size at least where .

Let me start by understanding what we need. A subset is complete if all possible binary vectors have positive probability. This is equivalent to saying the variables in the subset are mutually i...

After some years of work by several people the question is still unresolved – at the moment nobody knows whether the statement is true or false. What is known can be summarised as follows.

1. Small values of n
   • For n = 2 the assertion is empty.
   • For n = 3 the assertion is true (and hence it is also true for all n with 3 ≤ n ≤ 7, because in this range the required cardi...

The statement is false already for
n = 8 (so for every n ≥ 8).
Below we give an explicit system of 8 pair-wise independent ±1–valued (the usual 0/1–valued variables are obtained from them by X ↦ (1+X)/2) random variables in which no 4 of them are complete (that is, the joint distribution of every 4 of them is supported on at most 8 < 16 points).
Consequently a complete subset of cardinality ...