The density Turan problem for 3-uniform linear hypertrees. An efficient testing algorithm

Halina Bielak; Kamil Powroźnik

Annales Universitatis Mariae Curie-Skłodowska, sectio A – Mathematica, Tome 72 (2018), / Harvested from The Polish Digital Mathematics Library

Access to full text
Full (PDF)

Résumé

Let $𝒯 = (V, ℰ)$ be a 3-uniform linear hypertree. We consider a blow-up hypergraph $ℬ [𝒯]$ . We are interested in the following problem. We have to decide whether there exists a blow-up hypergraph $ℬ [𝒯]$ of the hypertree $𝒯$ , with hyperedge densities satisfying some conditions, such that the hypertree $𝒯$ does not appear in a blow-up hypergraph as a transversal. We present an efficient algorithm to decide whether a given set of hyperedge densities ensures the existence of a 3-uniform linear hypertree $𝒯$ in a blow-up hypergraph $ℬ [𝒯]$ .

Publié le : 2018-01-01
EUDML-ID : urn:eudml:doc:290759

@article{bwmeta1.element.ojs-doi-10_17951_a_2018_72_2_9,
     author = {Halina Bielak and Kamil Powro\'znik},
     title = {The density Turan problem for 3-uniform linear hypertrees. An efficient testing algorithm},
     journal = {Annales Universitatis Mariae Curie-Sk\l odowska, sectio A -- Mathematica},
     volume = {72},
     year = {2018},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.ojs-doi-10_17951_a_2018_72_2_9}
}

Halina Bielak; Kamil Powroźnik. The density Turan problem for 3-uniform linear hypertrees. An efficient testing algorithm. Annales Universitatis Mariae Curie-Skłodowska, sectio A – Mathematica, Tome 72 (2018) . http://gdmltest.u-ga.fr/item/bwmeta1.element.ojs-doi-10_17951_a_2018_72_2_9/

Bibliographie

Baber, R., Johnson, J. R., Talbot, J., The minimal density of triangles in tripartite graphs, LMS J. Comput. Math. 13 (2010), 388-413,

http://dx.doi.org/10.1112/S1461157009000436.

Berge, C., Graphs and Hypergraphs, Elsevier, New York, 1973.

Bielak, H., Powroznik, K., An efficient algorithm for the density Tur´an problem of some unicyclic graphs, in: Proceedings of the 2014 FedCSIS, Annals of Computer Science and Information Systems 2 (2014), 479-486,

http://dx.doi.org/10.15439/978-83-60810-58-3.

Bollobas, B., Extremal Graph Theory, Academic Press, London, 1978.

Bondy, A., Shen, J., Thomasse, S., Thomassen, C., Density conditions for triangles in multipartite graphs, Combinatorica 26 (2) (2006), 121-131,

http://dx.doi.org/10.1007/s00493-006-0009-y.

Brown, W. G., Erdos, P., Simonovits, M., Extremal problems for directed graphs, J. Combin. Theory B 15 (1) (1973), 77-93,

http://dx.doi.org/10.1016/0095-8956(73)90034-8.

Csikvari, P., Nagy, Z. L., The density Tur´an problem, Combin. Probab. Comput. 21 (2012), 531-553,

http://dx.doi.org/10.1017/S0963548312000016.

Furedi, Z., Turan type problems, in: (A. D. Keedwell, ed.) Survey in Combinatorics, 1991, Cambridge Univ. Press, Cambridge, 1991, 253-300,

http://dx.doi.org/10.1017/cbo9780511666216.010.

Godsil, C. D., Royle, G., Algebraic Graph Theory, Springer-Verlag, New York, 2001,

http://dx.doi.org/10.1007/978-1-4613-0163-9.

Jin, G., Complete subgraphs of r-partite graphs, Combin. Probab. Comput. 1 (1992), 241-250,

http://dx.doi.org/10.1017/s0963548300000274.

Nagy, Z. L., A multipartite version of the Turan problem – density conditions and eigenvalues, Electron. J. Combin. 18 (1) (2011), Paper 46, 15 pp.

Turan, P., On an extremal problem in graph theory, Mat. Fiz. Lapok 48 (1941), 436-452.

Yuster, R., Independent transversal in r-partite graphs, Discrete Math. 176 (1997), 255-261,

http://dx.doi.org/10.1016/s0012-365x(96)00300-7.