Abstract. Denote by [Formula: see text] the smallest eigenvalue of the signless Laplacian matrix of an [Formula: see text]-vertex graph [Formula: see text]. Brandt conjectured in 1997 that for regular triangle-free graphs [Formula: see text]. We prove a stronger result: If [Formula: see text] is a triangle-free graph, then [Formula: see text]. Brandt’s conjecture is a subproblem of two famous conjectures of Erdős: (1) Sparse-half-conjecture: Every [Formula: see text]-vertex triangle-free graph has a subset of vertices of size [Formula: see text] spanning at most [Formula: see text] edges. (2) Every [Formula: see text]-vertex triangle-free graph can be made bipartite by removing at most [Formula: see text] edges. In our proof we use linear algebraic methods to upper bound [Formula: see text] by the ratio between the number of induced paths with 3 and 4 vertices. We give an upper bound on this ratio via the method of flag algebras.

The Hall ratio of a graph $G$ is the maximum value of $v(H) / \alpha(H)$ taken over all non-null subgraphs $H \subseteq G$. For any graph, the Hall ratio is a lower-bound on its fractional chromatic number. In this note, we present various constructions of graphs whose fractional chromatic number grows much faster than their Hall ratio. This refutes a conjecture of Harris.

The notion of limits of dense graphs was invented, among other reasons, to attack problems in extremal graph theory. It is straightforward to define limits of order types in analogy with limits of graphs, and this paper examines how to adapt to this setting two approaches developed to study limits of dense graphs. We first consider flag algebras, which were used to open various questions on graphs to mechanical solving via semidefinite programming. We define flag algebras of order types, and use them to obtain, via the semidefinite method, new lower bounds on the density of 5- or 6-tuples in convex position in arbitrary point sets, as well as some inequalities expressing the difficulty of sampling order types uniformly. We next consider graphons, a representation of limits of dense graphs that enable their study by continuous probabilistic or analytic methods. We investigate how planar measures fare as a candidate analogue of graphons for limits of order types. We show that the map sending a measure to its associated limit is continuous and, if restricted to uniform measures on compact convex sets, a homeomorphism. We prove, however, that this map is not surjective. Finally, we examine a limit of order types similar to classical constructions in combinatorial geometry (Erdos-Szekeres, Horton...) and show that it cannot be represented by any somewhere regular measure; we analyze this example via an analogue of Sylvester's problem on the probability that k random points are in convex position.

For every $d\ge 3$ and $k\in\{2\}\cup[3,\infty)$, we determine the smallest $\varepsilon$ such that every fractional $(k+\varepsilon)$-precoloring of vertices at mutual distance at least d of a graph G with fractional chromatic number equal to k can be extended to a proper fractional $(k+\varepsilon)$-coloring of G. Our work complements analogous results of Albertson for ordinary colorings and those of Albertson and West for circular colorings.

We show that every (sub)cubic [Formula: see text]-vertex graph with sufficiently large girth has fractional chromatic number at most 2.2978, which implies that it contains an independent set of size at least [Formula: see text]. Our bound on the independence number is valid for random cubic graphs as well, as it improves existing lower bounds on the maximum cut in cubic graphs with large girth.