Abstract. We present an essentially tight bound for the Ramsey–Turán problem for 4-cliques without using the Regularity lemma. This enables us to substantially extend the range in which one has the tight bound for the number of edges in [Formula: see text]-free graphs as a function of the independence number, apart from lower order terms.

Let $H$ and $G$ be graphs on $n$ vertices, where $n$ is sufficiently large. We prove that if $H$ has Ore-degree at most 5 and $G$ has minimum degree at least $2n/3$, then $H$ is a subgraph of $G$.MSC codesembedding problemsOre-degreeBollobás--Eldridge--Catlin conjectureMSC codes05C3505C7505C0768R10

Dependence clusters are (maximal) groups of source code entities that each depend on the other according to some dependence relation. Such clusters are generally seen as detrimental to many software engineering activities, but their formation and overall structure are not well understood yet. In a set of subject programs from moderate to large sizes, we observed frequent occurrence of dependence clusters using Static Execute After (SEA) dependences (SEA is a conservative yet efficiently computable dependence relation on program procedures). We identified potential linchpins inside the clusters; these are procedures that can primarily be made responsible for keeping the cluster together. Furthermore, we found that as the size of the system increases, it is more likely that multiple procedures are jointly responsible as sets of linchpins. We also give a heuristic method based on structural metrics for locating possible linchpins as their exact identification is unfeasible in practice, and presently there are no better ways than the brute-force method. We defined novel metrics and comparison methods to be able to demonstrate clusters of different sizes in programs.