ArticleOriginal scientific text

Title

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

Authors ,

Abstract

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

Keywords

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

Bibliography

  1. Baber, R., Johnson, J. R., Talbot, J., The minimal density of triangles in tripartite graphs, LMS J. Comput. Math. 13 (2010), 388-413,
  2. http://dx.doi.org/10.1112/S1461157009000436.
  3. Berge, C., Graphs and Hypergraphs, Elsevier, New York, 1973.
  4. 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,
  5. http://dx.doi.org/10.15439/978-83-60810-58-3.
  6. Bollobas, B., Extremal Graph Theory, Academic Press, London, 1978.
  7. Bondy, A., Shen, J., Thomasse, S., Thomassen, C., Density conditions for triangles in multipartite graphs, Combinatorica 26 (2) (2006), 121-131,
  8. http://dx.doi.org/10.1007/s00493-006-0009-y.
  9. Brown, W. G., Erdos, P., Simonovits, M., Extremal problems for directed graphs, J. Combin. Theory B 15 (1) (1973), 77-93,
  10. http://dx.doi.org/10.1016/0095-8956(73)90034-8.
  11. Csikvari, P., Nagy, Z. L., The density Tur´an problem, Combin. Probab. Comput. 21 (2012), 531-553,
  12. http://dx.doi.org/10.1017/S0963548312000016.
  13. Furedi, Z., Turan type problems, in: (A. D. Keedwell, ed.) Survey in Combinatorics, 1991, Cambridge Univ. Press, Cambridge, 1991, 253-300,
  14. http://dx.doi.org/10.1017/cbo9780511666216.010.
  15. Godsil, C. D., Royle, G., Algebraic Graph Theory, Springer-Verlag, New York, 2001,
  16. http://dx.doi.org/10.1007/978-1-4613-0163-9.
  17. Jin, G., Complete subgraphs of r-partite graphs, Combin. Probab. Comput. 1 (1992), 241-250,
  18. http://dx.doi.org/10.1017/s0963548300000274.
  19. Nagy, Z. L., A multipartite version of the Turan problem – density conditions and eigenvalues, Electron. J. Combin. 18 (1) (2011), Paper 46, 15 pp.
  20. Turan, P., On an extremal problem in graph theory, Mat. Fiz. Lapok 48 (1941), 436-452.
  21. Yuster, R., Independent transversal in r-partite graphs, Discrete Math. 176 (1997), 255-261,
  22. http://dx.doi.org/10.1016/s0012-365x(96)00300-7.
Main language of publication
English
Published
2018
Published online
2018-12-22
Exact and natural sciences