The Library
More non-bipartite forcing pairs
Tools
Tools
Tools
Hubai, Tamàs, Král', Daniel, Parczyk, Olaf and Person, Yury (2019) More non-bipartite forcing pairs. In: EuroComb 2019, Bratislava, Slovakia, 26-30 Aug 2019. Published in: Acta Mathematica Universitatis Comenianae, 88 (3). pp. 819-825. ISSN 0862-9544.
|
PDF
WRAP-more-non-bipartite-forcing-pairs-Kral-2019.pdf - Accepted Version - Requires a PDF viewer. Download (397Kb) | Preview |
Official URL: http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/am...
Abstract
We study pairs of graphs (H1, H2) such that every graph with the densities of H1 and H2 close to the densities ofH1andH2in a random graph is quasi random; such pairs (H1, H2) are called forcing. Non-bipartite forcing pairs were first discovered by Conlon, Hàn, Person and Schacht [Weak quasi-randomness for uniform hypergraphs, Random Structures Algorithms 40(2012), no. 1, 1–38]: they showed that (Kt, F) is forcing where F is the graph that arises from Kt 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 fort >3.We show that⌈(t+ 1)/2⌉doublings always suffice.
| Item Type: | Conference Item (Paper) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | |||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | |||||||||
| Library of Congress Subject Headings (LCSH): | Graph theory | |||||||||
| Journal or Publication Title: | Acta Mathematica Universitatis Comenianae | |||||||||
| Publisher: | Faculty of Mathematics, Physics and Informatics, Comenius University | |||||||||
| ISSN: | 0862-9544 | |||||||||
| Official Date: | 1 August 2019 | |||||||||
| Dates: |
|
|||||||||
| Volume: | 88 | |||||||||
| Number: | 3 | |||||||||
| Page Range: | pp. 819-825 | |||||||||
| Status: | Peer Reviewed | |||||||||
| Publication Status: | Published | |||||||||
| Access rights to Published version: | Restricted or Subscription Access | |||||||||
| Date of first compliant deposit: | 11 June 2019 | |||||||||
| Date of first compliant Open Access: | 12 June 2019 | |||||||||
| RIOXX Funder/Project Grant: |
|
|||||||||
| Conference Paper Type: | Paper | |||||||||
| Title of Event: | EuroComb 2019 | |||||||||
| Type of Event: | Conference | |||||||||
| Location of Event: | Bratislava, Slovakia | |||||||||
| Date(s) of Event: | 26-30 Aug 2019 | |||||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
