Frankl, My Dear : 1

Re: Dick Lipton & Ken Regan(1)(2)

I need to think a little about the context that Lipton and Regan have wrapped around the Frankl Conjecture, if not exactly about the problem itself.  This will be a scratch-worky post-in-progress (PIP❢), or a series of posts, and I may even delete it down the road if it runs out of gas or turns into too much nonsense.

Just to get started, let me post the passage from the 2nd of the above articles where I thought I spied something familiar, though it was late, past my bedtime, and I was pondering weak and weary, etc.

Let us use {J_{i}(f)} to denote those {x} such that

\displaystyle f(x) \neq f(x^{i}).

Obviously the following is true:

\displaystyle \frac{|J_{i}(f)|}{2^{n}} = I_{i}(f).

There must be a better notation than {J_{i}} — we are open to suggestions. Any?

In order to understand the above formulas, we have to back up a little and pick up a couple of earlier definitions, rephrasing them slightly in the style of notation to which I would like you to become accustomed.

Let {\mathbb{B} = \{0,1\}} and let {f : \mathbb{B}^{n} \to \mathbb{B}} be a boolean function. The influence of the {i}^\text{th} input of {f} is defined by

\displaystyle I_{i}(f) = \mathrm{Prob}_{x}[ f(x) \neq f(x^{i}) ],

where {x^{i}} is equal to

\displaystyle x_{1}, \dots, x_{i-1}, \neg x_{i}, x_{i+1}, \dots, x_{n}.

There is another way of expressing the bit flip operation {x \mapsto x^i} that I like a bit better.  Here is the formal definition, using {j} instead of {i} as the index of the indicated variable.

Definition.  Let the function {\lnot_j : \mathbb{B}^k \to \mathbb{B}} be defined for each integer {j} in the interval {[1, k]} by the following equation:

{\lnot_j (x_1, \ldots, x_j, \ldots, x_k) ~=~ x_1 \land \ldots \land x_{j-1} \land \lnot x_j \land x_{j+1} \land \ldots \land x_k}.

It is conventional to write logical conjunction as multiplication, with or without a dot between conjuncts. It is also convenient in many contexts to write logical negation {\lnot x_j} with a tilde as {\tilde{x}_j} or with distinctive parentheses as {\texttt{(} x_j \texttt{)}}. Thus we may see the function {\lnot_j : \mathbb{B}^k \to \mathbb{B}} written in either of the following forms:

\begin{matrix}  \lnot_j (x_1, \ldots, x_j, \ldots, x_k)  & = &  x_1 x_2 \ldots x_{j-1} \tilde{x}_j x_{j+1} \ldots x_{k-1} x_k  \\[4pt]  & = &  x_1 x_2 \ldots x_{j-1} \texttt{(} x_j \texttt{)} x_{j+1} \ldots x_{k-1} x_k  \end{matrix}

Visually speaking, {\lnot_j (x_1, \ldots, x_k)} is a singular proposition that picks out a single cell {x} of the associated venn diagram, namely, the cell where {x_j} is false and all the rest of the {x_i} are true.  By way of context, I used the above notations for {\lnot_j} in defining minimal negation operators, which may eventually find use in this discussion.

This looks like a good place to break and start a second post in the series.

To be continued …

Advertisements
This entry was posted in Boolean Algebra, Boolean Functions, Computational Complexity, Differential Logic, Frankl Conjecture, Logic, Logical Graphs, Mathematics, Péter Frankl and tagged , , , , , , , , . Bookmark the permalink.

2 Responses to Frankl, My Dear : 1

  1. Pingback: Frankl, My Dear : 2 | Inquiry Into Inquiry

  2. Pingback: Survey of Differential Logic • 1 | Inquiry Into Inquiry

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s