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
Li, YRousseau, CCZang, W
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?
DOI: http://dx.doi.org/10.1007/s003730170060
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
0911-0119
2023 Impact Factor: 0.6
2023 SCImago Journal Rankings: 0.511
ISI Accession Number ID
WOS:000168577900011
References
References in Scopus

 

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
dc.identifier.issnl0911-0119-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats