3
votes
1answer
73 views

Are there further transformation principles similar to the Inclusion-Exclusion Principle (IEP)?

This question is motivated by the elaboration of the question Combinatorial Proof of Inclusion-Exclusion Principle (IEP). Let's consider the following two aspects: 1.) IEP transforms at least ...
0
votes
1answer
32 views

Number of non-increasing boolean functions of $n$ booleans, up to permutations.

How many non-increasing boolean functions of $n$ boolean variables are there? I don't want to count functions that ignore some of their inputs. If two or more functions differ only by permuting their ...
0
votes
0answers
49 views

Whats wrong with this reasoning… A Textbook Example?

This question is directly related to another one, as I see it the faulty reasoning is applied in the proof I will giving next: Lemma: Suppose we have $b$ boolean functions with two arguments (like ...
1
vote
1answer
70 views

Whats wrong with this reasoning…

Suppose I have two non-distinguishable balls (for example two white ones) and I color them with red and green, then a combinatorial reasoning could go like this. Suppose I enumerate the balls, ball ...
1
vote
0answers
58 views

Expansion of subsets of a hamming ball in hypercube

Consider a hypercube graph $G_n = (V,E)$ in n dimensions. Let $H_{1/2} \subset V$ be the set which represents the hamming ball of radius $n/2$. That is for every $v \in H_{1/2}$ the hamming weight of ...
3
votes
1answer
70 views

Find the solutions of Boolean equations

It's given 4 Boolean equations. I need to find the number of solutions of each. $a)\ x_{1}x_{2}\oplus x_{2}x_{3}\oplus\ ...\ \oplus\ x_{n-1}x_{n}=1$ $b)\ x_{1}x_{2}\vee x_{2}x_{3}\vee\ ...\ \vee\ ...
3
votes
3answers
162 views

The sum of a polynomial over a boolean affine subcube

Let $P:\mathbb{Z}_2^n\to\mathbb{Z}_2$ be a polynomial of degree $k$ over the boolean cube. An affine subcube inside $\mathbb{Z}_2^n$ is defined by a basis of $k+1$ linearly independent vectors and an ...
1
vote
1answer
67 views

The fraction of k-juntas with low influences in all of the coordinates

Let $f:\{-1,1\}^n\to\{-1,1\}$ be a boolean function. Define the influence of the $i$'th coordinate of $f$ as follows: $$\operatorname{Inf}_i(f)=\Pr_{x}[f(x)\neq f(\hat x_i)]$$ where $x$ is uniformly ...
4
votes
1answer
207 views

A Boolean function with total influence 1 must be a dictatorship

Let $f:\{-1,1\}^n\to\{-1,1\}$ be a boolean function. Define the influence of the $i$'th coordinate of $f$ as follows: $$\operatorname{Inf}_i(f)=\Pr_{x}[f(x)\neq f(\hat x_i)]$$ where $x$ is uniformly ...
3
votes
2answers
75 views

Parity is the only function with maximal influences

Let $f:\{-1,1\}^n\to\{-1,1\}$ be a boolean function. Define the influence of the $i$'th coordinate of $f$ as follows: $$\operatorname{Inf}_i(f)=\Pr_{x}[f(x)\neq f(\hat x_i)]$$ where $x$ is uniformly ...