N1-0095 Turán numbers and extremal problems for paths

FMF - logo ang
IMFM - logo
ARRS - logo ang

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

Research Organisations

Researchers

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.