Problem med halsband

Halsbandsproblemet är ett problem inom rekreationsmatematiken som rör rekonstruktionen av halsband (cykliska arrangemang av binära värden ) från partiell information.

Formulering

Halsbandsproblemet involverar rekonstruktionen av ett halsband med $n$ pärlor, som var och en är antingen svart eller vit, från partiell information. Informationen anger hur många kopior halsbandet innehåller av varje möjlig arrangemang av $k$ svarta pärlor. Till exempel, för $k=2$ , ger den angivna informationen antalet par svarta pärlor som är åtskilda av $i$ -positioner, för $i=0,\dots \lfloor n/2-1\rfloor$ . Detta kan göras formellt genom att definiera en $k$ -konfiguration till att vara ett halsband av $k$ svarta pärlor och $nk$ vita pärlor, och räkna antalet sätt att rotera en $k$ -konfiguration så att var och en av dess svarta pärlor sammanfaller med en av de svarta pärlorna i det givna halsbandet.

Halsbandsproblemet frågar: om $n$ ges, och antalet kopior av varje $k$ -konfiguration är kända upp till någon tröskel $k\leq K$ , hur stor måste tröskeln $K$ vara innan denna information helt bestämmer halsbandet som den beskriver? På motsvarande sätt, om informationen om $k$ -konfigurationer tillhandahålls i steg, där ${\displaystyle k}:$ e steget ger antalet kopior av varje $k$ -konfiguration, hur många steg behövs (i värsta fall) för att rekonstruera det exakta mönstret av svarta och vita pärlor i originalhalsbandet?

Övre gränser

Alon , Caro, Krasikov och Roditty visade att 1 + log ₂ ( n ) är tillräckligt, med hjälp av en smart förbättrad inklusions-exkluderingsprincip .

Radcliffe och Scott visade att om n är primtal är 3 tillräckligt, och för vilket n som helst räcker 9 gånger antalet primtalsfaktorer av n .

Pebody visade att för vilket n som helst räcker 6 och i en uppföljning är det tillräckligt med 4 för udda n . Han förmodade att 4 återigen är tillräckligt för till och med n större än 10, men detta förblir obevisat.

Se även

Alon, N.; Caro, Y.; Krasikov, I.; Roditty, Y. (1989). "Kombinatoriska rekonstruktionsproblem" . J. Combin. Teori Ser. B . 47 (2): 153–161. doi : 10.1016/0095-8956(89)90016-6 .
Radcliffe, AJ; Scott, AD (1998). "Rekonstruera delmängder av Z _n " . J. Combin. Teori Ser. A . 83 (2): 169–187. doi : 10.1006/jcta.1998.2870 .
Pebody, Luke (2004). "Rekonstruktiviteten av ändliga abelska grupper". Kombinera. Probab. Comput. 13 (6): 867–892. doi : 10.1017/S0963548303005807 .
Pebody, Luke (2007). "Rekonstruera udda halsband". Kombinera. Probab. Comput . 16 (4): 503–514. doi : 10.1017/S0963548306007875 .
Paul K. Stockmeyer (1974). "Problemet med berlockarmband och dess tillämpningar". I Bari, Ruth A. ; Harary, Frank (red.). Grafer och kombinatorik: Proceedings of the Capital Conference on Graph Theory and Combinatorics vid George Washington University, 18–22 juni 1973 . Föreläsningsanteckningar i matematik. Vol. 406. s. 339–349. doi : 10.1007/BFb0066456 . ISBN 978-3-540-06854-9 .