Algorithmic Barriers for the Random Hypergraph Panchromatic Coloring Problem

Student: Tiapkin Daniil

Educational Programme: Applied Mathematics and Information Science (Bachelor)

Year of Graduation: 2021

The hypergraph coloring problem is one of the most well-known problems in theoretical computer science. However, this problem is hard to solve for arbitrary hypergraphs. To overcome this, it is convenient to consider a random hypergraph setting. However, there is very limited research on the algorithmic aspects of the ordinary hypergraph coloring problem, and nothing is known for a more restrictive case of panchromatic colorings. In this paper, we study the possible algorithmic barrier for the hypergraph panchromatic coloring problem in a random setting. The approach is based on the work of D.Achlioptas on the shattering phenomenon of the coloring problem in random graphs.

Student Theses at HSE must be completed in accordance with the University Rules and regulations specified by each educational programme.

Summaries of all theses must be published and made freely available on the HSE website.

The full text of a thesis can be published in open access on the HSE website only if the authoring student (copyright holder) agrees, or, if the thesis was written by a team of students, if all the co-authors (copyright holders) agree. After a thesis is published on the HSE website, it obtains the status of an online publication.

Student theses are objects of copyright and their use is subject to limitations in accordance with the Russian Federation’s law on intellectual property.

In the event that a thesis is quoted or otherwise used, reference to the author’s name and the source of quotation is required.

Search all student theses