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
On minimal triangle-free Ramsey graphs
Stockholm University, Faculty of Science, Department of Mathematics.
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. , 108 p.
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:su:diva-151219OAI: oai:DiVA.org:su-151219DiVA: diva2:1172282
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
List of papers
1. An invariant for minimum triangle-free graphs
Open this publication in new window or tab >>An invariant for minimum triangle-free graphs
(English)Manuscript (preprint) (Other academic)
Abstract [en]

We study the number of edges, e(G), in triangle-free graphs with a prescribed number of vertices, n(G), independence number, α(G), and number of cycles of length four, N(C₄;G). We in particular show that 3e(G) - 17n(G) + 35α(G) + N(C₄;G) ≥ 0 for all triangle-free graphs G. We also characterise the graphs that satisfy this inequality with equality.

National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:su:diva-151216 (URN)
Available from: 2018-01-09 Created: 2018-01-09 Last updated: 2018-01-09
2. A computerised classification of some almost minimal triangle-free Ramsey graphs
Open this publication in new window or tab >>A computerised classification of some almost minimal triangle-free Ramsey graphs
(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:nbn:se:su:diva-151218 (URN)
Available from: 2018-01-09 Created: 2018-01-09 Last updated: 2018-01-09

Open Access in DiVA

No full text

By organisation
Department of Mathematics
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 29 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