PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2018 | 72 | 2 |
Tytuł artykułu

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

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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}]\).
Rocznik
Tom
72
Numer
2
Opis fizyczny
Daty
wydano
2018
online
2018-12-22
Twórcy
Bibliografia
  • 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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.ojs-doi-10_17951_a_2018_72_2_9
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.