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

Halina Bielak, and 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 72.2 (2018): null. <http://eudml.org/doc/290759>.

@article{HalinaBielak2018,
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\}]$.},
author = {Halina Bielak, Kamil Powroźnik},
journal = {Annales Universitatis Mariae Curie-Skłodowska, sectio A – Mathematica},
keywords = {Uniform linear hypertree; blow-up hypergraph; transversal; Turan density},
language = {eng},
number = {2},
pages = {null},
title = {The density Turan problem for 3-uniform linear hypertrees. An efficient testing algorithm},
url = {http://eudml.org/doc/290759},
volume = {72},
year = {2018},
}

TY - JOUR
AU - Halina Bielak
AU - Kamil Powroźnik
TI - The density Turan problem for 3-uniform linear hypertrees. An efficient testing algorithm
JO - Annales Universitatis Mariae Curie-Skłodowska, sectio A – Mathematica
PY - 2018
VL - 72
IS - 2
SP - null
AB - 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}]$.
LA - eng
KW - Uniform linear hypertree; blow-up hypergraph; transversal; Turan density
UR - http://eudml.org/doc/290759
ER -