Skip to main content
formatting, added tags
Source Link
YCor
  • 63.9k
  • 5
  • 187
  • 286

Let $A \subset \{-1,1\}^{n}$ be a subset of the Hamming cube with cardinality $|A|=2^{n-1}$. Define $w_{A} : \{-1,1\}^{n} \to \mathbb{N}\cup \{0\}$ so that $w_{A}(x)$ to be number of boundary edges to $A$ containing $x$, i.e., $w_{A}(x)$ counts number of edges of $\{-1,1\}^{n}$ with endpoints in $A$ and in the complement of $A$ so that one of the endpoint is $x$. Clearly $w_{A}(x)=0$ if $x$ is in the "strict interior" of $A$, or in the "strict complement" of $A$, and it is nonzero if and only if $x$ is on the "boundary" of $A$. Notice that $w_{A}(x)$ can be nonzero for some $x \notin A$.

The classical edge--isoperimetricedge–isoperimetric inequality on the Hamming cube of Harper implies that $$ \frac{1}{2^{n}}\sum_{x \in \{-1,1\}^{n}}w_{A}(x) \geq 1 $$ and the constant $1$ on the right hand side is sharp.

My question is what is known about the best possible $C(p)\geq 0$ such that $$ \frac{1}{2^{n}}\sum_{x \in \{-1,1\}^{n}}w_{A}^{p/2}(x) \geq C(p), \quad 1\leq p\leq 2 $$ for all sets $A \subset \{-1,1\}^{n}$ with cardinality $2^{n-1}$.

Let $A \subset \{-1,1\}^{n}$ be a subset of the Hamming cube with cardinality $|A|=2^{n-1}$. Define $w_{A} : \{-1,1\}^{n} \to \mathbb{N}\cup \{0\}$ so that $w_{A}(x)$ to be number of boundary edges to $A$ containing $x$, i.e., $w_{A}(x)$ counts number of edges of $\{-1,1\}^{n}$ with endpoints in $A$ and in the complement of $A$ so that one of the endpoint is $x$. Clearly $w_{A}(x)=0$ if $x$ is in the "strict interior" of $A$, or in the "strict complement" of $A$, and it is nonzero if and only if $x$ is on the "boundary" of $A$. Notice that $w_{A}(x)$ can be nonzero for some $x \notin A$.

The classical edge--isoperimetric inequality on the Hamming cube of Harper implies that $$ \frac{1}{2^{n}}\sum_{x \in \{-1,1\}^{n}}w_{A}(x) \geq 1 $$ and the constant $1$ on the right hand side is sharp.

My question is what is known about the best possible $C(p)\geq 0$ such that $$ \frac{1}{2^{n}}\sum_{x \in \{-1,1\}^{n}}w_{A}^{p/2}(x) \geq C(p), \quad 1\leq p\leq 2 $$ for all sets $A \subset \{-1,1\}^{n}$ with cardinality $2^{n-1}$.

Let $A \subset \{-1,1\}^{n}$ be a subset of the Hamming cube with cardinality $|A|=2^{n-1}$. Define $w_{A} : \{-1,1\}^{n} \to \mathbb{N}\cup \{0\}$ so that $w_{A}(x)$ to be number of boundary edges to $A$ containing $x$, i.e., $w_{A}(x)$ counts number of edges of $\{-1,1\}^{n}$ with endpoints in $A$ and in the complement of $A$ so that one of the endpoint is $x$. Clearly $w_{A}(x)=0$ if $x$ is in the "strict interior" of $A$, or in the "strict complement" of $A$, and it is nonzero if and only if $x$ is on the "boundary" of $A$. Notice that $w_{A}(x)$ can be nonzero for some $x \notin A$.

The classical edge–isoperimetric inequality on the Hamming cube of Harper implies that $$ \frac{1}{2^{n}}\sum_{x \in \{-1,1\}^{n}}w_{A}(x) \geq 1 $$ and the constant $1$ on the right hand side is sharp.

My question is what is known about the best possible $C(p)\geq 0$ such that $$ \frac{1}{2^{n}}\sum_{x \in \{-1,1\}^{n}}w_{A}^{p/2}(x) \geq C(p), \quad 1\leq p\leq 2 $$ for all sets $A \subset \{-1,1\}^{n}$ with cardinality $2^{n-1}$.

added 8 characters in body
Source Link
Paata Ivanishvili
  • 3.9k
  • 1
  • 21
  • 30

Let $A \subset \{-1,1\}^{n}$ be a subset of the Hamming cube with cardinality $|A|=2^{n-1}$. Define $w_{A} : \{-1,1\}^{n} \to \mathbb{N}\cup \{0\}$ so that $w_{A}(x)$ to be number of boundary edges to $A$ containing $x$, i.e., $w_{A}(x)$ counts number of edges of $\{-1,1\}^{n}$ with endpoints in $A$ and in the complement of $A$ so that one of the endpoint is $x$. Clearly $w_{A}(x)=0$ if $x$ is in the "strict interior" of $A$, or in the "strict complement" of $A$, and it is nonzero if and only if $x$ is on the "boundary" of $A$. Notice that $w_{A}(x)$ can be nonzero for some $x \notin A$.

The classical edge--isoperimetric inequality on the Hamming cube of Harper implies that $$ \frac{1}{2^{n}}\sum_{x \in \{-1,1\}^{n}}w_{A}(x) \geq 1 $$ and the constant $1$ on the right hand side is sharp.

My question is what is known about the best possible $C(p)>0$$C(p)\geq 0$ such that $$ \frac{1}{2^{n}}\sum_{x \in \{-1,1\}^{n}}w_{A}^{p/2}(x) \geq C(p), \quad 1<p\leq 2 $$$$ \frac{1}{2^{n}}\sum_{x \in \{-1,1\}^{n}}w_{A}^{p/2}(x) \geq C(p), \quad 1\leq p\leq 2 $$ for all sets $A \subset \{-1,1\}^{n}$ with cardinality $2^{n-1}$.

Let $A \subset \{-1,1\}^{n}$ be a subset of the Hamming cube with cardinality $|A|=2^{n-1}$. Define $w_{A} : \{-1,1\}^{n} \to \mathbb{N}\cup \{0\}$ so that $w_{A}(x)$ to be number of boundary edges to $A$ containing $x$, i.e., $w_{A}(x)$ counts number of edges of $\{-1,1\}^{n}$ with endpoints in $A$ and in the complement of $A$ so that one of the endpoint is $x$. Clearly $w_{A}(x)=0$ if $x$ is in the "strict interior" of $A$, or in the "strict complement" of $A$, and it is nonzero if and only if $x$ is on the "boundary" of $A$. Notice that $w_{A}(x)$ can be nonzero for some $x \notin A$.

The classical edge--isoperimetric inequality on the Hamming cube of Harper implies that $$ \frac{1}{2^{n}}\sum_{x \in \{-1,1\}^{n}}w_{A}(x) \geq 1 $$ and the constant $1$ on the right hand side is sharp.

My question is what is known about the best possible $C(p)>0$ such that $$ \frac{1}{2^{n}}\sum_{x \in \{-1,1\}^{n}}w_{A}^{p/2}(x) \geq C(p), \quad 1<p\leq 2 $$ for all sets $A \subset \{-1,1\}^{n}$ with cardinality $2^{n-1}$.

Let $A \subset \{-1,1\}^{n}$ be a subset of the Hamming cube with cardinality $|A|=2^{n-1}$. Define $w_{A} : \{-1,1\}^{n} \to \mathbb{N}\cup \{0\}$ so that $w_{A}(x)$ to be number of boundary edges to $A$ containing $x$, i.e., $w_{A}(x)$ counts number of edges of $\{-1,1\}^{n}$ with endpoints in $A$ and in the complement of $A$ so that one of the endpoint is $x$. Clearly $w_{A}(x)=0$ if $x$ is in the "strict interior" of $A$, or in the "strict complement" of $A$, and it is nonzero if and only if $x$ is on the "boundary" of $A$. Notice that $w_{A}(x)$ can be nonzero for some $x \notin A$.

The classical edge--isoperimetric inequality on the Hamming cube of Harper implies that $$ \frac{1}{2^{n}}\sum_{x \in \{-1,1\}^{n}}w_{A}(x) \geq 1 $$ and the constant $1$ on the right hand side is sharp.

My question is what is known about the best possible $C(p)\geq 0$ such that $$ \frac{1}{2^{n}}\sum_{x \in \{-1,1\}^{n}}w_{A}^{p/2}(x) \geq C(p), \quad 1\leq p\leq 2 $$ for all sets $A \subset \{-1,1\}^{n}$ with cardinality $2^{n-1}$.

added 2 characters in body
Source Link
Paata Ivanishvili
  • 3.9k
  • 1
  • 21
  • 30

Let $A \subset \{-1,1\}^{n}$ be a subset of the Hamming cube with cardinality $|A|=2^{n-1}$. Define $w_{A} : \{-1,1\}^{n} \to \mathbb{N}\cup \{0\}$ so that $w_{A}(x)$ to be number of boundary edges to $A$ containing $x$, i.e., $w_{A}(x)$ counts number of edges of $\{-1,1\}^{n}$ with endpoints in $A$ and in the complement of $A$ so that one of the endpoint is $x$. Clearly $w_{A}(x)=0$ if $x$ is in the "strict interior" of $A$, or in the "strict complement" of $A$, and it is nonzero if and only if $x$ is on the "boundary" of $A$. Notice that $w_{A}(x)$ can be nonzero for some $x \notin A$.

The classical edge--isoperimetric inequality on the Hamming cube of Harper implies that $$ \frac{1}{2^{n}}\sum_{x \in \{-1,1\}^{n}}w_{A}(x) \geq 1 $$ and the constant $1$ on the right hand side is sharp.

My question is what is known about the best possible $C(p)>0$ such that $$ \frac{1}{2^{n}}\sum_{x \in \{-1,1\}^{n}}w_{A}^{p/2}(x) \geq C(p), \quad 1<p\leq 2 $$ for all sets $A \subset \{-1,1\}^{n}$ with cardinality $2^{n-1}$.

Let $A \subset \{-1,1\}^{n}$ be a subset of the Hamming cube with cardinality $|A|=2^{n-1}$. Define $w_{A} : \{-1,1\}^{n} \to \mathbb{N}\cup \{0\}$ so that $w_{A}(x)$ to be number of boundary edges to $A$ containing $x$, i.e., $w_{A}(x)$ counts number of edges of $\{-1,1\}^{n}$ with endpoints in $A$ and in the complement of $A$ so that one of the endpoint is $x$. Clearly $w_{A}(x)=0$ if $x$ is in the "strict interior" of $A$, or in the "strict complement" of $A$, and it is nonzero if and only if $x$ is on the "boundary" of $A$. Notice that $w_{A}(x)$ can be nonzero for some $x \notin A$.

The classical edge--isoperimetric inequality on the Hamming cube of Harper implies that $$ \frac{1}{2^{n}}\sum_{x \in \{-1,1\}^{n}}w_{A}(x) \geq 1 $$ and the constant $1$ on the right hand side is sharp.

My question is what is known about the best possible $C(p)>0$ such that $$ \frac{1}{2^{n}}\sum_{x \in \{-1,1\}^{n}}w_{A}^{p/2}(x) \geq C(p), \quad 1<p\leq 2 $$ for all sets $A \subset \{-1,1\}^{n}$ with cardinality $2^{n-1}$.

Let $A \subset \{-1,1\}^{n}$ be a subset of the Hamming cube with cardinality $|A|=2^{n-1}$. Define $w_{A} : \{-1,1\}^{n} \to \mathbb{N}\cup \{0\}$ so that $w_{A}(x)$ to be number of boundary edges to $A$ containing $x$, i.e., $w_{A}(x)$ counts number of edges of $\{-1,1\}^{n}$ with endpoints in $A$ and in the complement of $A$ so that one of the endpoint is $x$. Clearly $w_{A}(x)=0$ if $x$ is in the "strict interior" of $A$, or in the "strict complement" of $A$, and it is nonzero if and only if $x$ is on the "boundary" of $A$. Notice that $w_{A}(x)$ can be nonzero for some $x \notin A$.

The classical edge--isoperimetric inequality on the Hamming cube of Harper implies that $$ \frac{1}{2^{n}}\sum_{x \in \{-1,1\}^{n}}w_{A}(x) \geq 1 $$ and the constant $1$ on the right hand side is sharp.

My question is what is known about the best possible $C(p)>0$ such that $$ \frac{1}{2^{n}}\sum_{x \in \{-1,1\}^{n}}w_{A}^{p/2}(x) \geq C(p), \quad 1<p\leq 2 $$ for all sets $A \subset \{-1,1\}^{n}$ with cardinality $2^{n-1}$.

Source Link
Paata Ivanishvili
  • 3.9k
  • 1
  • 21
  • 30
Loading