¿Cuál es el nombre de este objeto combinatorio y lugar para leer sobre él?

Question

El título es sin duda noninformative pero yo no podía entender cómo a meterse en la descripción del objeto que me interesa. Juzgar por ti mismo.

Tengo un alfabeto en $d$ símbolos. Quiero construir una matriz rectangular con $pd$ filas y $qd$ columnas rellenas con ellos de tal manera que cada fila contiene $p$ copias de cada símbolo, cada columna contiene $q$ copias de cada símbolo, y el siguiente número $n$ es mínimo.

Para cada par $i,j$ de las columnas, vamos a $n_{ij}$ el número de filas donde estas columnas contienen símbolos idénticos. A continuación, $n$ es la mayor de las $n_{ij}$ para todos los $i\ne j$.

Ni siquiera puedo averiguar cuál es el menor valor posible de $n$ por $d,p,q$.

He intentado buscar este tipo de estructuras. No es que no he encontrado nada. Por el contrario, he encontrado demasiados muy similar investigaciones en torno a los gadgets llamado diseños de bloques, esquemas de asociación, Steiner triples y otras cosas. Por desgracia no he podido encontrar lo que necesito, ni siquiera de darle un nombre, ya que estoy seguro de que ya tiene un nombre establecido, pero no puedo averiguar qué es.

Answer 1

Lo que estás pidiendo es un código con dos sin restricciones habituales. Es un código sobre el alfabeto de tamaño $d$. Desea que cada palabra de código para tener la longitud $pd$ y deseas $qd$ total de palabras de código.

El parámetro de llamar a $n$ es igual a $pd - \Delta$ donde $\Delta$ se llama la distancia de su código. Desea minimizar $n,$ que es la misma como la maximización de la distancia $\Delta.$

Hasta ahora, su configuración es exactamente la misma que la de costumbre-en la teoría de la codificación, y este problema es muy bien estudiado. Agrega las dos restricciones adicionales que

1. Si proyectamos en cualquier coordenada, entonces cada símbolo debe aparecer con la misma frecuencia (esto no es realmente mucho de una restricción ya que podríamos tomar códigos lineales cuando dice $d$ es una fuente primaria de energía); y

2. Cada palabra de código necesidades de uso de cada símbolo el mismo número de veces (esto es mucho más de una restricción, diría yo).

En cualquier caso, si usted desea conseguir el mejor de los posibles límites, considere la posibilidad de decir Hoffman atado (un límite superior en los códigos que no necesitan para satisfacer sus adicionales 1 y 2). A continuación, considere la posibilidad de un adecuado código aleatorio, lo que usted necesita para asegurarse de que tiene la propiedad 2 por la construcción. Entonces, es casi tienen la propiedad 1, así que asegúrese de guardar un par de palabras de código en el final de modo que usted puede solucionar este problema. Entonces espero que este código aleatorio que va a coincidir con la de Hoffman obligado decentemente bien.

Otro pensamiento es mirar a decir Reed-Solomon códigos.

El caso de $d=2$ está muy, muy bien estudiado (códigos binarios), y no me sorprendería si su problema es conocido en ese ambiente.

Añadió:

De hecho, parece que este ha sido estudiado. Condición 2 se llama "equilibrado" códigos (o más generalmente, el peso constante de los códigos). Tienen aplicaciones de códigos de barras y tal, al parecer. Vea aquí.