Reunattomien osittaissanojen ja harvojen viivoittimien yhteydestä

Abstract

Työssä esitetään uusi yhteys harvojen viivoittimien ja reunattomien osittaissanojen välillä. Tämä tuottaa uudet parhaat ylä- ja alarajat reunattomien osittaissanojen maksimaaliselle kolomäärälle riippuen aakkostokoosta. Alarajan parannus saadaan aikaan suoralla konstruktiolla, joka käyttää neljää aakkosta. Uusi yläraja pätee kaikille aakkostoille, mutta voittaa ennestään tunnetut ylärajat vasta, kun aakkosia on käytössä vähintään kuusi. Työ sisältää aiemmin tunnetut maksimaalisten kolojen määrän ratkaisut yksinkertaisen reunan ja binääriaakkoston tapauksissa. Kummatkin tapaukset ratkaistaan yleisellä graafeihin perustuvalla argumentilla, jolla voidaan tutkia myös isompien aakkostojen tapauksia. Harvojen viivoittimien kappaleessa esitetään kysymys siitä, kuinka paljon vähintään tulee pituuksia merkitä annetun pituiseen viivoittimeen, jotta sillä voi mitata kaikki pituuttaan pienemmät etäisyydet. Tähän kysymykseen esitetään parhaat tunnetut tulokset todistuksineen. Viivoittimia käsittelevässä kappaleessa todistetaan myös Wichmann-resepti toimivaksi viivoitinkonstruktioksi. Todistusta ei ennestään esiinny kirjallisuudessa, vaikkakin Wichmann mainitsee todistuksen olevan olemassa. Tuloksia sovelletaan tämän jälkeen reunattomiin osittaissanoihin.