File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Asymptotic upper bounds for ramsey functions

TitleAsymptotic upper bounds for ramsey functions
Authors
KeywordsAverage degree
Convex function
Independence number
Ramsey number
Issue Date2001
PublisherSpringer Japan. The Journal's web site is located at http://link.springer-ny.com/link/service/journals/00373/index.htm
Citation
Graphs And Combinatorics, 2001, v. 17 n. 1, p. 123-128 How to Cite?
AbstractWe show that for any graph G with N vertices and average degree d, if the average degree of any neighborhood induced subgraph is at most a, then the independence number of G is at least Nfa+1(d), where fa+1(d)=∫0 1(((1-t) 1/(a+1))/(a+1+(d-a-1)t))dt. Based on this result, we prove that for any fixed k and l, there holds r(Kk+K̄l,Kn)≤ (l+o(1))nk/(logn)k-1. In particular, r(Kk, Kn)≤(1+o(1))nk-1/(log n)k-2. © Springer-Verlag 2001.
Persistent Identifierhttp://hdl.handle.net/10722/75441
ISSN
2015 Impact Factor: 0.48
2015 SCImago Journal Rankings: 0.797
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorLi, Yen_HK
dc.contributor.authorRousseau, CCen_HK
dc.contributor.authorZang, Wen_HK
dc.date.accessioned2010-09-06T07:11:08Z-
dc.date.available2010-09-06T07:11:08Z-
dc.date.issued2001en_HK
dc.identifier.citationGraphs And Combinatorics, 2001, v. 17 n. 1, p. 123-128en_HK
dc.identifier.issn0911-0119en_HK
dc.identifier.urihttp://hdl.handle.net/10722/75441-
dc.description.abstractWe show that for any graph G with N vertices and average degree d, if the average degree of any neighborhood induced subgraph is at most a, then the independence number of G is at least Nfa+1(d), where fa+1(d)=∫0 1(((1-t) 1/(a+1))/(a+1+(d-a-1)t))dt. Based on this result, we prove that for any fixed k and l, there holds r(Kk+K̄l,Kn)≤ (l+o(1))nk/(logn)k-1. In particular, r(Kk, Kn)≤(1+o(1))nk-1/(log n)k-2. © Springer-Verlag 2001.en_HK
dc.languageengen_HK
dc.publisherSpringer Japan. The Journal's web site is located at http://link.springer-ny.com/link/service/journals/00373/index.htmen_HK
dc.relation.ispartofGraphs and Combinatoricsen_HK
dc.subjectAverage degreeen_HK
dc.subjectConvex functionen_HK
dc.subjectIndependence numberen_HK
dc.subjectRamsey numberen_HK
dc.titleAsymptotic upper bounds for ramsey functionsen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0911-0119&volume=17&spage=123&epage=128&date=2001&atitle=Asymptotic+Upper+Bounds+for+Ramsey+Functionsen_HK
dc.identifier.emailZang, W:wzang@maths.hku.hken_HK
dc.identifier.authorityZang, W=rp00839en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/s003730170060-
dc.identifier.scopuseid_2-s2.0-0042627199en_HK
dc.identifier.hkuros63195en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0042627199&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume17en_HK
dc.identifier.issue1en_HK
dc.identifier.spage123en_HK
dc.identifier.epage128en_HK
dc.identifier.isiWOS:000168577900011-
dc.publisher.placeJapanen_HK
dc.identifier.scopusauthoridLi, Y=7502087425en_HK
dc.identifier.scopusauthoridRousseau, CC=7102137402en_HK
dc.identifier.scopusauthoridZang, W=7005740804en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats