Research project is (co) funded by the Slovenian Research Agency.
UL Member: Faculty of Mathematics and Physics
Code: N1-0095
Project: Turán numbers and extremal problems for paths
Period: 1. 10. 2019 - 30. 9. 2022
Range per year: 0,52 FTE category: B
Head: Sandi Klavžar
Research activity: Natural sciences and mathematics
Citations for bibliographic records
Project description:
The main objects of our joint research are extremal combinatorial problems. We plan to investigate several types of such problems, with an emphasis on Turán-type problems and path-related extremal questions. Understanding extremal parameters of different structures that come from a local property helps us to describe global properties of the structures. Paths are one of the most basic structures in graph theory, that can be building parts of more complex structures. Investigating different extremal parameters on paths could provide us information about the behaviour of other structures.
The first main topic of the proposed project are Turán-type problems. We list five questions analogous to the classical Turán question that we plan to investigate. (i) Generalized Turán numbers. The problem here is counting subgraphs in a graph, under the forbiddance of other graphs as subgraphs. (ii) Turán numbers of Berge hypergraphs. Here the main object to be investigated is the Turán number of Berge-F which is defined as the maximum possible number of hyperedges in a Berge-F-free hypergraph. (iii) Turán numbers of ordered graphs. The Turán problem for a set of ordered graphs H asks for the maximum number of edges that an ordered graph can have without containing any H as an ordered subgraph. (iv) Turán numbers with degree restrictions. In the beginning of the 1990’s, Albertson proved that a graph or its complement on at least 6 vertices contains a triangle such that two of its vertices have the same degree. We plan to explore this phenomenon in different settings. (v) Vertex Turán numbers in hypercubes. We will try to exploit techniques invented for forbidden subposet problems to obtain results in this area.
The second main topic of the proposed project are path-related extremal problems in graphs. Several important graph-theoretic problems are concerned with a (minimum) set S of vertices in a graph G such that G − S does not contain a graph from a given family F as a subgraph. For instance, the vertex cover number is such a problem. The main topics we plan to investigate are the following. (i) Vertex k-path cover. We plan to continue the investigation of the vertex k-path cover, and expand it to various problems related to hitting different types of paths in graphs. (ii) Related concepts of hitting paths. We plan to study an edge analogue of vertex k-path cover and also vertex k-path covers with respect to other types of paths. (iii) Simultaneously avoiding shortest paths. We will investigate the general position problem and in particular try to find connections between the new concept and some well-established concepts. (iv) Extremal problems concerning path systems. We propose the study of a family of new models which are common generalizations of some graph-theoretic problems on one side, and scheduling or bin packing on the other. Since the new model is a common generalization of network flows and of bin packing or scheduling, we plan to apply the ideas and methods from all these classical areas.
