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
An invariant for minimum triangle-free graphs
Stockholm University, Faculty of Science, Department of Mathematics.ORCID iD: 0000-0002-6188-0596
Number of Authors: 12019 (English)In: Australasian Journal of Combinatorics, ISSN 2202-3518, Vol. 74, p. 371-388Article in journal (Refereed) Published
Abstract [en]

We study the number of edges, e(G), in triangle-free graphs with a prescribed number of vertices, n(G), independence number, alpha(G), and number of cycles of length 4, N(C-4; G). In particular we show that 3e(G) - 17n(G) + 35 alpha(G) + N(C-4; G) >= 0 for all triangle-free graphs G. We also characterise the graphs that satisfy this inequality with equality. As a consequence we improve the previously best known lower bounds on the independence ratio i(G) = alpha(G)/n(G) for graphs of average degree at most 4 and girth at least 5, 6 or 7.

Place, publisher, year, edition, pages
2019. Vol. 74, p. 371-388
National Category
Mathematics
Research subject
Mathematics
Identifiers
URN: urn:nbn:se:su:diva-173072ISI: 000481626800001OAI: oai:DiVA.org:su-173072DiVA, id: diva2:1352354
Available from: 2019-09-18 Created: 2019-09-18 Last updated: 2019-12-17Bibliographically approved
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
Stockholm: Department of Mathematics, Stockholm University, 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, Stockholm, 15:15 (English)
Opponent
Supervisors
Available from: 2018-01-11 Created: 2018-01-09 Last updated: 2019-12-17Bibliographically approved
2. On linear graph invariants related to Ramsey and edge numbers: or how I learned to stop worrying and love the alien invasion
Open this publication in new window or tab >>On linear graph invariants related to Ramsey and edge numbers: or how I learned to stop worrying and love the alien invasion
2019 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

In this thesis we study the Ramsey numbers, R(l,k), the edge numbers, e(l,k;n) and graphs that are related to these. The edge number e(l,k;n) may be defined as the least natural number m for which all graphs on n vertices and less than m edges either contains a complete subgraph of size l or an independent set of size k. The Ramsey number R(l,k) may then be defined as the least natural number n for which e(l,k;n) = ∞ .

In Paper I, IV and V we study strict lower bounds for e(l,k;n). In Paper I we do this in the case where l = 3 by, in particular, showing e(G) ≥ (1/3)(17n(G) - 35α(G) - N(C4;G)) for all triangle-free graphs G, where N(C4;G) denotes the number of cycles of length 4 in G. In Paper IV we describe a general method for generating similar inequalities to the one above but for graphs that may contain triangles, but no complete subgraphs of size 4. We then show a selection of the inequalities we get from the computerised generation. In Paper V we study the inequality 

e(G) ≥ (1/2)(ceil((7l - 2)/2)n(G) - l floor((5l + 1)/2)α(G))

for l ≥ 2, and examine the properties of graphs G without cliques of size l+1 such that G is minimal with respect to the above inequality not holding, and show for small l that no such graphs G can exist.

In Paper II we study constructions of graphs G such that e(G) - e(3,k;n) is small when n ≤ 3.5(k-1). We employ a description of some of these graphs in terms of 'patterns' and a recursive procedure to construct them from the patterns. We also present the result of computer calculations where we actually have performed such constructions of Ramsey graphs and compare these lists to previously computed lists of Ramsey graphs.

In Paper III we develop a method for computing, recursively, upper bounds for Ramsey numbers R(l,k). In particular the method uses bounds for the edge numbers e(l,k;n). In Paper III we have implemented this method as a computer program which we have used to improve several of the best known upper bounds for small Ramsey numbers R(l,k).

Place, publisher, year, edition, pages
Stockholm: Department of Mathematics, Stockholm University, 2019. p. 47
Keywords
Ramsey number, edge number, minimal Ramsey graph, independence number, clique number, Turán's theorem, crochet pattern, H13-pattern, linear graph invariant, triangle-free graph
National Category
Mathematics Discrete Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:su:diva-174786 (URN)978-91-7797-905-0 (ISBN)978-91-7797-906-7 (ISBN)
Public defence
2019-12-16, sal 14, hus 5, Kräftriket, Roslagsvägen 101, Stockholm, 10:00 (English)
Opponent
Supervisors
Note

At the time of the doctoral defense, the following papers were unpublished and had a status as follows: Paper 2: Manuscript. Paper 3: Accepted. Paper 4: Manuscript. Paper 5: Manuscript.

Available from: 2019-11-21 Created: 2019-10-10 Last updated: 2019-11-19Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Free full text

Search in DiVA

By author/editor
Krüger, Oliver
By organisation
Department of Mathematics
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

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