MORE NON-BIPARTITE FORCING PAIRS

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.

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

Language

English

Type of outcome

Článek v odborném periodiku

Field of Study

10101 Pure mathematics

Country of publisher

Slovakia

Confidentiality degree

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

References:

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

---

Abstract

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.