6
$\begingroup$

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}$.

$\endgroup$
5
  • 1
    $\begingroup$ 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... $\endgroup$
    – Igor Rivin
    Aug 20, 2012 at 14:43
  • $\begingroup$ Certainly much improved, but what is $\Delta?$ $\endgroup$
    – Igor Rivin
    Aug 20, 2012 at 15:32
  • $\begingroup$ Symmetric difference. $\endgroup$ Aug 20, 2012 at 15:33
  • $\begingroup$ Sorry for a naive question, but what do you mean here by an intersecting set system? $\endgroup$
    – Seva
    Aug 21, 2012 at 9:41
  • $\begingroup$ @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$. $\endgroup$ Aug 21, 2012 at 10:39

1 Answer 1

8
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Lovely example. I see why it's intersecting and monotonic. Is there any easy way to see why the influences are so small? $\endgroup$ Aug 20, 2012 at 15:44
  • $\begingroup$ Sean, I added an explanation. $\endgroup$
    – Gil Kalai
    Aug 20, 2012 at 17:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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