Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A computerised classification of some almost minimal triangle-free Ramsey graphs
Stockholm University, Faculty of Science, Department of Mathematics.
(English)Manuscript (preprint) (Other academic)
Abstract [en]

A graph G is called a (3,j;n)-minimal Ramsey graph if it has the least amount of edges, e(3,j;n), given that G is triangle-free, the independence number α(G)<j and that G has n vertices. Triangle-free graphs G with α(G)<j and where e(G)−e(3,j;n) is small are said to be almost minimal Ramsey graphs. We look at a construction of some almost minimal Ramsey graphs, called H₁₃-patterned graphs. We make computer calculations of the number of almost minimal Ramsey triangle-free graphs that are H₁₃-patterned. The results of these calculations indicate that many of these graphs are in fact H₁₃-patterned. In particular, all but one of the connected (3,j;n)-minimal Ramsey graphs for j≤9 are indeed H₁₃-patterned.

National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
URN: urn:nbn:se:su:diva-151218OAI: oai:DiVA.org:su-151218DiVA, id: diva2:1172269
Available from: 2018-01-09 Created: 2018-01-09 Last updated: 2018-01-09
In thesis
1. On minimal triangle-free Ramsey graphs
Open this publication in new window or tab >>On minimal triangle-free Ramsey graphs
2017 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

A graph G is called a minimal Ramsey (3, k; n)-graph if it has the least amount of edges, e(3, k; n), possible given that G is triangle-free, has independence number α(G) < k an has n vertices. The numbers e(3, k; n) and the minimalRamsey graphs are directly related to the Ramsey numbers R(3, k).This licentiate thesis studies minimal Ramsey graphs, graphs that are closeto being minimal Ramsey graphs and the edge numbers e(3, k; n) from several different aspects. Lower bounds on e(3, k; n) are lower bounds on the numberof edges in triangle-free graphs. In Paper I we show the bound

e(G) ≥ (1/3)(17n(G) − 35α(G) − N(C 4 ; G)),

where N(C4 ; G) that is number of cycles of length four in G. We also classifyall triangle-free graphs which satisfy this bound with equality.

In Paper II we study constructions of minimal Ramsey graphs, and graphsG such that e(G) − e(3, k; n) is small. We use a way to describe some of these graphs in terms of “patterns” and a recursive procedure to construct them. We also present the result of computer calculations where we have actually performed such constructions of Ramsey graphs and compare these lists to other computations of Ramsey graphs.

Place, publisher, year, edition, pages
Department of Mathematics, 2017. p. 108
National Category
Discrete Mathematics
Identifiers
urn:nbn:se:su:diva-151219 (URN)
Presentation
2018-01-16, Room 306, House 6, Kräftriket 6, 104 05, Stockholm, 15:15 (English)
Opponent
Supervisors
Available from: 2018-01-11 Created: 2018-01-09 Last updated: 2018-01-11Bibliographically approved

Open Access in DiVA

No full text in DiVA

By organisation
Department of Mathematics
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 2 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf