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
    Commented Aug 20, 2012 at 14:43
  • $\begingroup$ Certainly much improved, but what is $\Delta?$ $\endgroup$
    – Igor Rivin
    Commented Aug 20, 2012 at 15:32
  • $\begingroup$ Symmetric difference. $\endgroup$ Commented 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
    Commented 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$ Commented 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$ Commented Aug 20, 2012 at 15:44
  • $\begingroup$ Sean, I added an explanation. $\endgroup$
    – Gil Kalai
    Commented Aug 20, 2012 at 17:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .