Examinando por Autor "Quiroz, Daniel A."

Mostrando 1 - 2 de 2
  • Miniatura
    Ítem
    Clique immersions in graphs of independence number two with certain forbidden subgraphs
    (Elsevier, 2021) Quiroz, Daniel A.
    The Lescure–Meyniel conjecture is the analogue of Hadwiger’s conjecture for the immersion order. It states that every graph contains the complete graph as an immersion, and like its minor-order counterpart it is open even for graphs with independence number 2. We show that every graph with independence number and no hole of length between 4 and satisfies this conjecture. In particular, every -free graph with satisfies the Lescure–Meyniel conjecture. We give another generalisation of this corollary, as follows. Let and be graphs with independence number at most 2, such that . If is -free, then satisfies the Lescure–Meyniel conjecture.
  • Miniatura
    Ítem
    Universal arrays
    (Elsevier, 2021) Pavez-Signé, Matías; Quiroz, Daniel A.; Sanhueza-Matamala, Nicolás
    A word on q symbols is a sequence of letters from a fixed alphabet of size q. For an integer , we say that a word w is k-universal if, given an arbitrary word of length k, one can obtain it by removing letters from w. It is easily seen that the minimum length of a k-universal word on q symbols is exactly qk. We prove that almost every word of size is k-universal with high probability, where is an explicit constant whose value is roughly . Moreover, we show that the k-universality property for uniformly chosen words exhibits a sharp threshold. Finally, by extending techniques of Alon (2017) [1], we give asymptotically tight bounds for every higher dimensional analogue of this problem.