J 2019

MORE NON-BIPARTITE FORCING PAIRS

HUBAI, Tamás; Daniel KRÁĽ; Olaf PARCZYK a Yuri PERSON

Základní údaje

Originální název

MORE NON-BIPARTITE FORCING PAIRS

Autoři

HUBAI, Tamás; Daniel KRÁĽ; Olaf PARCZYK a Yuri PERSON

Vydání

Acta Mathematica Universitatis Comenianae, Bratislava, Comenius University, 2019, 0231-6986

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10101 Pure mathematics

Stát vydavatele

Slovensko

Utajení

není předmětem státního či obchodního tajemství

Odkazy

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/19:00113680

Organizační jednotka

Fakulta informatiky

UT WoS

EID Scopus

Klíčová slova anglicky

Quasirandom graphs; Forcing Conjecture

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 8. 5. 2020 13:27, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

We study pairs of graphs (H-1, H-2) such that every graph with the densities of H-1 and H-2 close to the densities of H-1 and H-2 in a random graph is quasirandom; such pairs (H-1, H-2) are called forcing. Non-bipartite forcing pairs were first discovered by Conlon, Han, Person and Schacht [Weak quasi-randomness for uniform hypergraphs, Random Structures Algorithms 40 (2012), no. 1, 1-38]: they showed that (K-t, F) is forcing where F is the graph that arises from K-t by iteratively doubling its vertices and edges in a prescribed way t times. Reiher and Schacht [Forcing quasirandomness with triangles, Forum of Mathematics, Sigma. Vol. 7, 2019] strengthened this result for t = 3 by proving that two doublings suffice and asked for the minimum number of doublings needed for t > 3. We show that [t + 1)/2] doublings always suffice.