HUBAI, Tamás, Daniel KRÁĽ, Olaf PARCZYK and Yuri PERSON. MORE NON-BIPARTITE FORCING PAIRS. Acta Mathematica Universitatis Comenianae. Bratislava: Comenius University, 2019, vol. 88, No 3, p. 819-825. ISSN 0231-6986.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name MORE NON-BIPARTITE FORCING PAIRS
Authors HUBAI, Tamás, Daniel KRÁĽ (203 Czech Republic, guarantor, belonging to the institution), Olaf PARCZYK and Yuri PERSON.
Edition Acta Mathematica Universitatis Comenianae, Bratislava, Comenius University, 2019, 0231-6986.
Other information
Original language English
Type of outcome Article in a journal
Field of Study 10101 Pure mathematics
Country of publisher Slovakia
Confidentiality degree is not subject to a state or trade secret
WWW URL
RIV identification code RIV/00216224:14330/19:00113680
Organization unit Faculty of Informatics
UT WoS 000484349000072
Keywords in English Quasirandom graphs; Forcing Conjecture
Tags International impact, Reviewed
Changed by Changed by: RNDr. Pavel Šmerk, Ph.D., učo 3880. Changed: 8/5/2020 13:27.
Abstract
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.
PrintDisplayed: 28/9/2024 13:43