The long standing Zarankiewicz's conjecture states that the crossing number cr(Km,n) of the complete bipartite graph is Z(m,n):= [m/2][m-1/2][n/2][n-1/2]. Using flag algebras we show that cr(Kn,n) ≥ 0.9118 • Z(n, n) + o(n4). We also show that the rectilinear crossing number cr-(Kn,n) of Kn,n is at least 0.987 • Z(n,n) + o(n4). Finally, we show that if a drawing of Kn,n has no K3,4 that has exactly two crossings, and these crossings share exactly one vertex, then it has at least Z(n,n) + o(n4) crossings. This is a local restriction inspired by Turán type problems that gives an asymptotically tight result.

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.

Finding exact Ramsey numbers is a problem typically restricted to relatively small graphs. The flag algebra method was developed to find asymptotic results for very large graphs, so it seems that the method is not suitable for finding small Ramsey numbers. But this intuition is wrong, and we will develop a technique to do just that in this paper. We find new upper bounds for many small graph and hypergraph Ramsey numbers. As a result, we prove the exact values $R(K_4^-,K_4^-,K_4^-)=28$, $R(K_8,C_5)= 29$, $R(K_9,C_6)= 41$, $R(Q_3,Q_3)=13$, $R(K_{3,5},K_{1,6})=17$, $R(C_3, C_5, C_5)= 17$, and $R(K_4^-,K_5^-;3)= 12$. We hope that this technique will be adapted to address other questions for smaller graphs with the flag algebra method.

For a given multigraph $H$, a graph $G$ is $H$-linked if $|G|\ge |H|$ and for every injective map $\tau: V(H)\to V(G)$, we can find internally disjoint paths in $G$, such that every edge from $uv$ in $H$ corresponds to a $\tau(u)-\tau(v)$ path. To guarantee that a $G$ is $H$-linked, you need a minimum degree larger than $\frac{|G|}{2}$. This situation changes, if you know that $G$ has a certain connectivity $k$. Depending on $k$, even a minimum degree independent of $|G|$ may suffice. Let $\delta(k,H,N)$ be the minimum number such that every $k$-connected graph $G$ with $|G|=N$ and $\delta(G)\ge \delta(k,H,N)$ is $H$-linked. We study bounds for this quantity. In particular, we find bounds for all multigraphs $H$ with at most three edges and some with four edges, which are optimal up to small additive or multiplicative constants. As a consequence, we also establish a few pure connectivity bounds for graph linkages.

A weighting of the edges of a graph is called irregular if the weighted degrees of the vertices are all different. In this note we show that such a weighting is possible from the weight set [Formula: see text] for all graphs not containing a component with exactly two vertices or two isolated vertices.