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 linear graph invariants related to Ramsey and edge numbers: or how I learned to stop worrying and love the alien invasion
Stockholm University, Faculty of Science, Department of Mathematics.ORCID iD: 0000-0002-6188-0596
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 [en]
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: urn:nbn:se:su:diva-174786ISBN: 978-91-7797-905-0 (print)ISBN: 978-91-7797-906-7 (electronic)OAI: oai:DiVA.org:su-174786DiVA, id: diva2:1359821
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: 2022-02-26Bibliographically 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
2019 (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.

National Category
Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:su:diva-173072 (URN)000481626800001 ()
Available from: 2019-09-18 Created: 2019-09-18 Last updated: 2022-02-26Bibliographically approved
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: 2022-02-28Bibliographically approved
3. An improved method for recursively computing upper bounds for two-colour Ramsey numbers
Open this publication in new window or tab >>An improved method for recursively computing upper bounds for two-colour Ramsey numbers
2020 (English)In: Utilitas mathematica, ISSN 0315-3681, Vol. 116, p. 83-89Article in journal (Refereed) Published
Abstract [en]

The two-colour Ramsey number R(m,n) is the least natural number p such that any graph of order p must contain either a clique of size m or an independent set of size n. We exhibit a method for computing upper bounds for R(m,n) recursively,using known upper bounds of R(.,.) with lower values for at least one of the arguments. We also show how this method can be used to improve many of the best known bounds that are available in the literature.

National Category
Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:su:diva-174781 (URN)000637080300008 ()
Available from: 2019-10-10 Created: 2019-10-10 Last updated: 2022-01-26Bibliographically approved
4. Searching for non-negative invariants for K4-free graphs
Open this publication in new window or tab >>Searching for non-negative invariants for K4-free graphs
(English)Manuscript (preprint) (Other academic)
Abstract [en]

In this paper we describe a method to generate graph invariants of the form

ia,b,c,d(G) = ak1(G) + bk2(G) + ck3(G) + dα(G),

where kn(G) denotes the number of cliques of size n in G and α(G) is the independence number. The invariants are generated by computer with the purpose of getting hypotheses of the following form:

ia,b,c,d(G) ≥ 0$ for all K4-free graphs G.

We preform this generation on a particular data set and prove a select few of the generated hypotheses.

National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:su:diva-174783 (URN)
Available from: 2019-10-10 Created: 2019-10-10 Last updated: 2022-02-26Bibliographically approved
5. On invariants related to edge numbers of Kl+1-free graphs
Open this publication in new window or tab >>On invariants related to edge numbers of Kl+1-free graphs
(English)Manuscript (preprint) (Other academic)
Abstract [en]

In this paper we discuss a generalisation of Turán's theorem, where we do not only consider an upper bound on the clique number but also on the independence number, α(G). This generalisation can be expressed in terms of the non-negativity of the graph invariant

iₗ(G) = 2e(G) - ⌈(7\ell-2)/2⌉ n(G) + l ⌊(5\ell + 1)/2⌋ α(G),

for all Kₗ₊₁-free graphs G, where e(G) and n(G) denote the number or edges and the number of vertices of the graph G, respectively. We show several strong properties that must be satisfied by a minimal Kₗ₊₁-free graph such that iₗ(G) < 0. Moreover, for some special cases for l we show that indeed iₗ(G) ≥ 0 and classify the graphs for which we have equality.

National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:su:diva-174784 (URN)
Available from: 2019-10-10 Created: 2019-10-10 Last updated: 2022-02-26Bibliographically approved

Open Access in DiVA

On linear graph invariants related to Ramsey and edge numbers(624 kB)413 downloads
File information
File name FULLTEXT01.pdfFile size 624 kBChecksum SHA-512
0bd24a75a62e593587c4cca57d607c309be6c1341ceeddd11999aadef8ecaac5a5bec8d7f516d079d9eec56f9096dd8838d32470ce40eeea9e43efc08ebbd899
Type fulltextMimetype application/pdf

Authority records

Krüger, Oliver

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar
Total: 413 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

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