Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Is there any known improvement on the Kahn-Kalai-Linial inequality (on the influences of boolean functions) in the special case in which $f$ is the indicator function of an intersecting monotonic set system? More concretely, is there an absolute constant $C>0$ such that the following statement holds:

If $f:\mathcal{P}([n]) \to \lbrace 0,1\rbrace$ is the indicator of an intersecting upset, then there exists $x\in [n]$ such that $I_x(f)\geq C/\sqrt{n}$.

(Note that the "tribes" example of a half-sized system in which all influences are $\ll \log n /n$ is certainly not intersecting.)

Background: The $x$th influence of a boolean function $f$ is defined as

$$I_x(f) = \mathbf{E}(f(X)\neq f(X \Delta \lbrace x\rbrace),$$

($\Delta$ is symmetric difference) where $X$ is drawn randomly and uniformly from $\mathcal{P}([n])$. In particular, if $f$ is the indicator of a monotonic set system $\mathcal{U}\subset\mathcal{P}([n])$ (monotonic meaning $X\subset Y$ and $X\in\mathcal{U}$ implies $Y\in\mathcal{U}$), $I_x(f)$ is the number of sets $X\in \mathcal{U}$ containing $x$, minus the number of such sets not containing $x$, divided by $2^{n-1}$.

share|improve this question
1  
You might want to explain a bit more what the setting of your question is, as it is, you have a positive probability of getting an answer from @Gil Kalai, and a not-so-positive probability of getting an answer from anyone else... –  Igor Rivin Aug 20 '12 at 14:43
    
Certainly much improved, but what is $\Delta?$ –  Igor Rivin Aug 20 '12 at 15:32
    
Symmetric difference. –  Sean Eberhard Aug 20 '12 at 15:33
    
Sorry for a naive question, but what do you mean here by an intersecting set system? –  Seva Aug 21 '12 at 9:41
    
@Seva Sorry for being unclear. $\mathcal{U}$ is intersecting if every pair of sets $A,B\in\mathcal{U}$ intersect: $A\cap B\ne\emptyset$. –  Sean Eberhard Aug 21 '12 at 10:39

1 Answer 1

up vote 7 down vote accepted

This is a natural question and indeed the property of being intersecting is quite interesting also in various aspect of influences. However, you cannot improve KKL's theorem if f is intersecting: An example is this: consider your variables on a circle and let f=1 if the longest run of 1's is larger than the longest 1's of 0's and in case of equality consider the second longest run (and continue lexicographically). In this case f is intersecting and the influence of every variable is logn/n.

This example is symmetric under rotations and therefore all influences are the same. The sum of influences can be described as the integral over all configurations x of h(x) the number of pivotal variables. Here a variable is pivotal if changing its value changes the value of f. Given x with f(x)=1 typically a variable is pivotal only if it belongs to the largest run which is of expected size logn. There are cases of equality (between 1 runs and 0 euns or between two runs) that the number of pivotal variables will be larger than log n but those are rare. This explains why every influence is proportional to logn/n but for a complete proof some more work is needed.

share|improve this answer
    
Lovely example. I see why it's intersecting and monotonic. Is there any easy way to see why the influences are so small? –  Sean Eberhard Aug 20 '12 at 15:44
    
Sean, I added an explanation. –  Gil Kalai Aug 20 '12 at 17:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.