Liu, Hong, Sharifzadeh, Maryam and Staden, Katherine (2017) Local conditions for exponentially many subdivisions. Combinatorics, Probability and Computing, 26 (3). pp. 423-430. doi:10.1017/S0963548316000365

PDF WRAP_exp-subd-Nov7-revised.pdf - Accepted Version - Requires a PDF viewer. Download (617Kb)

Request Changes to record.

Abstract

Given a graph F, let st(F) be the number of subdivisions of F, each with a different vertex set, which one can guarantee in a graph G in which every edge lies in at least t copies of F. In 1990, Tuza asked for which graphs F and large t, one has that st(F) is exponential in a power of t. We show that, somewhat surprisingly, the only such F are complete graphs, and for every F which is not complete, st(F) is polynomial in t. Further, for a natural strengthening of the local condition above, we also characterize those F for which st(F) is exponential in a power of t.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science > Mathematics
Library of Congress Subject Headings (LCSH):	Combinatorial analysis
Journal or Publication Title:	Combinatorics, Probability and Computing
Publisher:	Cambridge University Press
ISSN:	0963-5483
Official Date:	May 2017
Dates:	Date Event May 2017 Published 28 November 2016 Available 7 November 2016 Accepted
Date of first compliant deposit:	5 January 2017
Volume:	26
Number:	3
Page Range:	pp. 423-430
DOI:	10.1017/S0963548316000365
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Funder:	Engineering and Physical Sciences Research Council (EPSRC), Leverhulme Trust (LT), European Research Council (ERC)
Grant number:	EP/K012045/1(EPSRC); 306493(ERC); ECF-2016-523(LT)

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads