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

Halina Bielak, Kamil Powroźnik

Abstract


Let \(\mathcal{T}=(V,\mathcal{E})\) be a  3-uniform linear hypertree. We consider a blow-up hypergraph \(\mathcal{B}[\mathcal{T}]\). We are interested in the following problem. We have to decide whether there exists a blow-up hypergraph \(\mathcal{B}[\mathcal{T}]\) of the hypertree \(\mathcal{T}\), with hyperedge densities satisfying some conditions, such that the hypertree \(\mathcal{T}\) 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 \(\mathcal{T}\) in a blow-up hypergraph \(\mathcal{B}[\mathcal{T}]\).

Keywords


Uniform linear hypertree; blow-up hypergraph; transversal; Turan density

Full Text:

PDF

References


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.




DOI: http://dx.doi.org/10.17951/a.2018.72.2.9
Date of publication: 2018-12-22 22:03:10
Date of submission: 2018-12-21 21:46:04


Statistics


Total abstract view - 1000
Downloads (from 2020-06-17) - PDF - 521

Indicators



Refbacks

  • There are currently no refbacks.


Copyright (c) 2018 Halina Bielak, Kamil Powroźnik