Reunattomien osittaissanojen ja harvojen viivoittimien yhteydestä
Vanhatalo, Aleksi (2024-03-25)
Reunattomien osittaissanojen ja harvojen viivoittimien yhteydestä
(25.03.2024)
Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty.
avoin
Julkaisun pysyvä osoite on:
https://urn.fi/URN:NBN:fi-fe2024032713407
https://urn.fi/URN:NBN:fi-fe2024032713407
Tiivistelmä
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.
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.