Geodesic
The density Turan problem for 3-uniform linear hypertrees. An efficient testing algorithm
Annales Universitatis Mariae Curie-Skłodowska. Mathematica , Tome 72 (2018) no. 2.

Voir la notice de l'article provenant de la source Library of Science

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 ℬ[𝒯].
Keywords: Uniform linear hypertree, blow-up hypergraph, transversal, Turan density 
@article{AUM_2018_72_2_a7,
     author = {Bielak, Halina and Powro\'znik, Kamil},
     title = {The density {Turan} problem for 3-uniform linear hypertrees. {An} efficient testing algorithm},
     journal = {Annales Universitatis Mariae Curie-Sk{\l}odowska. Mathematica },
     publisher = {mathdoc},
     volume = {72},
     number = {2},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/AUM_2018_72_2_a7/}
}
TY  - JOUR
AU  - Bielak, Halina
AU  - Powroźnik, Kamil
TI  - The density Turan problem for 3-uniform linear hypertrees. An efficient testing algorithm
JO  - Annales Universitatis Mariae Curie-Skłodowska. Mathematica 
PY  - 2018
VL  - 72
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AUM_2018_72_2_a7/
LA  - en
ID  - AUM_2018_72_2_a7
ER  - 
%0 Journal Article
%A Bielak, Halina
%A Powroźnik, Kamil
%T The density Turan problem for 3-uniform linear hypertrees. An efficient testing algorithm
%J Annales Universitatis Mariae Curie-Skłodowska. Mathematica 
%D 2018
%V 72
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AUM_2018_72_2_a7/
%G en
%F AUM_2018_72_2_a7
Bielak, Halina; Powroźnik, Kamil. The density Turan problem for 3-uniform linear hypertrees. An efficient testing algorithm. Annales Universitatis Mariae Curie-Skłodowska. Mathematica , Tome 72 (2018) no. 2. http://geodesic.mathdoc.fr/item/AUM_2018_72_2_a7/

[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.