Uma generalização equilibrada do teorema de Hall

8

Deixe que e Y ser conjuntos, e B ser uma partição de X x Y . Gostaria de provar que não existe uma distribuição de D ao longo X x Y cuja marginal é uniforme ao longo de X , e de tal modo que a distribuição ao longo B induzida por D tem grande entropia (o último distribuição é definida através da atribuição de cada B B a probabilidade total massa dos elementos de B em D ). Podemos usar a seguinte condição:XYBX×YDX×YXBDBBBD

Considere o gráfico bipartido cujos lados são X e B , de modo que para cada ( x , y ) B exista uma aresta ( x , B ) em G (possíveis arestas múltiplas). Então, todo conjunto de xs de tamanho pelo menos 3GXB(x,y)B(x,B)Gxtem pelo menos134|X|vizinhos em G.1100|B|

Eu apreciaria se alguém pudesse me indicar um teorema relevante. Esta questão pode ser vista em um sentido como uma generalização do teorema de Hall, onde a condição acima é uma condição de relaxamento de Hall e, em vez de obter uma correspondência perfeita, obtemos um conjunto de arestas cujo subgráfico correspondente é aproximadamente regular.

Antecedentes : A motivação para essas perguntas vem da complexidade da comunicação. No cenário da complexidade da comunicação, dois players, Alice e Bob, obtêm entradas e y , respectivamente, e interagem para calcular alguma função f ( x , y ) . Aqui, cada conjunto B B consiste em pares ( x , y ) que produzem a mesma transcrição de comunicação entre Alice e Bob, e eu gostaria de provar que, sob alguma condição, é possível encontrar uma distribuição sobre X × Yxyf(x,y)BB(x,y)X×Y de modo que Alice receba uma entrada uniformemente distribuída e de modo que a entropia da transcrição sob a distribuição seja grande.

Ou Meir
fonte
1
Geralmente, não gostamos de postagem cruzada simultânea. Tende a fragmentar e duplicar a discussão.
Suresh Venkat
Obrigado, vi essa política um pouco mais tarde e removi a pergunta do excesso de matemática.
Ou Meir

Respostas:

5

Você pode examinar o conceito de fatores- e, especialmente, o teorema de Tutte sobre a existência de fatores- f . Você pode achar a Proposição 2 deste documento relevante.ff

hbm
fonte