CiteExport$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_upper_j_idt879",{id:"formSmash:upper:j_idt879",widgetVar:"widget_formSmash_upper_j_idt879",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:upper:exportLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt880_j_idt884",{id:"formSmash:upper:j_idt880:j_idt884",widgetVar:"widget_formSmash_upper_j_idt880_j_idt884",target:"formSmash:upper:j_idt880:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

On linear graph invariants related to Ramsey and edge numbers: or how I learned to stop worrying and love the alien invasionPrimeFaces.cw("AccordionPanel","widget_formSmash_some",{id:"formSmash:some",widgetVar:"widget_formSmash_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_all",{id:"formSmash:all",widgetVar:"widget_formSmash_all",multiple:true});
function selectAll()
{
var panelSome = $(PrimeFaces.escapeClientId("formSmash:some"));
var panelAll = $(PrimeFaces.escapeClientId("formSmash:all"));
panelAll.toggle();
toggleList(panelSome.get(0).childNodes, panelAll);
toggleList(panelAll.get(0).childNodes, panelAll);
}
/*Toggling the list of authorPanel nodes according to the toggling of the closeable second panel */
function toggleList(childList, panel)
{
var panelWasOpen = (panel.get(0).style.display == 'none');
// console.log('panel was open ' + panelWasOpen);
for (var c = 0; c < childList.length; c++) {
if (childList[c].classList.contains('authorPanel')) {
clickNode(panelWasOpen, childList[c]);
}
}
}
/*nodes have styleClass ui-corner-top if they are expanded and ui-corner-all if they are collapsed */
function clickNode(collapse, child)
{
if (collapse && child.classList.contains('ui-corner-top')) {
// console.log('collapse');
child.click();
}
if (!collapse && child.classList.contains('ui-corner-all')) {
// console.log('expand');
child.click();
}
}
2019 (English)Doctoral thesis, comprehensive summary (Other academic)
##### Abstract [en]

##### 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

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt1223",{id:"formSmash:j_idt1223",widgetVar:"widget_formSmash_j_idt1223",multiple:true});
##### Supervisors

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt1229",{id:"formSmash:j_idt1229",widgetVar:"widget_formSmash_j_idt1229",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt1235",{id:"formSmash:j_idt1235",widgetVar:"widget_formSmash_j_idt1235",multiple:true});
##### Note

##### List of papers

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(C_{4};G)) for all triangle-free graphs G, where N(C_{4};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).

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 approved1. An invariant for minimum triangle-free graphs$(function(){PrimeFaces.cw("OverlayPanel","overlay1352354",{id:"formSmash:j_idt1284:0:j_idt1288",widgetVar:"overlay1352354",target:"formSmash:j_idt1284:0:partsLink",showEvent:"mousedown",hideEvent:"mousedown",showEffect:"blind",hideEffect:"fade",appendToBody:true});});

2. A computerised classification of some almost minimal triangle-free Ramsey graphs$(function(){PrimeFaces.cw("OverlayPanel","overlay1172269",{id:"formSmash:j_idt1284:1:j_idt1288",widgetVar:"overlay1172269",target:"formSmash:j_idt1284:1:partsLink",showEvent:"mousedown",hideEvent:"mousedown",showEffect:"blind",hideEffect:"fade",appendToBody:true});});

3. An improved method for recursively computing upper bounds for two-colour Ramsey numbers$(function(){PrimeFaces.cw("OverlayPanel","overlay1359778",{id:"formSmash:j_idt1284:2:j_idt1288",widgetVar:"overlay1359778",target:"formSmash:j_idt1284:2:partsLink",showEvent:"mousedown",hideEvent:"mousedown",showEffect:"blind",hideEffect:"fade",appendToBody:true});});

4. Searching for non-negative invariants for K_{4}-free graphs$(function(){PrimeFaces.cw("OverlayPanel","overlay1359783",{id:"formSmash:j_idt1284:3:j_idt1288",widgetVar:"overlay1359783",target:"formSmash:j_idt1284:3:partsLink",showEvent:"mousedown",hideEvent:"mousedown",showEffect:"blind",hideEffect:"fade",appendToBody:true});});

5. On invariants related to edge numbers of K_{l+1}-free graphs$(function(){PrimeFaces.cw("OverlayPanel","overlay1359784",{id:"formSmash:j_idt1284:4:j_idt1288",widgetVar:"overlay1359784",target:"formSmash:j_idt1284:4:partsLink",showEvent:"mousedown",hideEvent:"mousedown",showEffect:"blind",hideEffect:"fade",appendToBody:true});});

isbn
urn-nbn$(function(){PrimeFaces.cw("Tooltip","widget_formSmash_j_idt2089",{id:"formSmash:j_idt2089",widgetVar:"widget_formSmash_j_idt2089",showEffect:"fade",hideEffect:"fade",showDelay:500,hideDelay:300,target:"formSmash:altmetricDiv"});});

CiteExport$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_lower_j_idt2178",{id:"formSmash:lower:j_idt2178",widgetVar:"widget_formSmash_lower_j_idt2178",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:lower:exportLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_lower_j_idt2181_j_idt2184",{id:"formSmash:lower:j_idt2181:j_idt2184",widgetVar:"widget_formSmash_lower_j_idt2181_j_idt2184",target:"formSmash:lower:j_idt2181:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});