Richmond and Richmond (1997) proved the following theorem: If, in a metric space with at least five points, all triangles are degenerate, then the space is isometric to a subset of the real line. We prove that the hypothesis is unnecessarily strong: In a metric space on n points, fewer than 7n2/6 suitably placed degenerate triangles suffice. However, fewer than n(n−1)/2 degenerate triangles, no matter how cleverly placed, never suffice.

Every graph $G=(V,E)$ is an induced subgraph of some Kneser graph of rank $k$, i.e., there is an assignment of (distinct) $k$-sets $v \mapsto A_v$ to the vertices $v\in V$ such that $A_u$ and $A_v$ are disjoint if and only if $uv\in E$. The smallest such $k$ is called the Kneser rank of $G$ and denoted by $f_{\rm Kneser}(G)$. As an application of a result of Frieze and Reed concerning the clique cover number of random graphs we show that for constant $0< p< 1$ there exist constants $c_i=c_i(p)>0$, $i=1,2$, such that $G\in {\mathcal G}(n, p)$ satisfies with high probability $ c_1 n/(\log n)< f_{\rm Kneser}(G) < c_2 n/(\log n). $ We apply this for other graph representations defined by Boros, Gurvich, and Meshulam. A $k$-min-difference representation of a graph $G$ is an assignment of a set $A_i$ to each vertex $i\in V(G)$ such that $ ij\in E(G) \,\, \Leftrightarrow \, \, \min \{|A_i\setminus A_j|,|A_j\setminus A_i| \}\geq k. $ The smallest $k$ such that there exists a $k$-min-difference representation of $G$ is denoted by $f_{\min}(G)$. Balogh and Prince proved in 2009 that for every $k$ there is a graph $G$ with $f_{\min}(G)\geq k$. We prove that there are constants $c''_1, c''_2>0$ such that $c''_1 n/(\log n)< f_{\min}(G) < c''_2n/(\log n)$ holds for almost all bipartite graphs $G$ on $n+n$ vertices.

For a property $\Gamma$ and a family of sets ${\mathcal F}$, let $f({\mathcal F},\Gamma)$ be the size of the largest subfamily of ${\mathcal F}$ having property $\Gamma$. For a positive integer m, let $f(m,\Gamma)$ be the minimum of $f({\mathcal F},\Gamma)$ over all families of size m. A family ${\mathcal F}$ is said to be $B_d$-free if it has no subfamily ${\mathcal F}'=\{F_I: I \subseteq [d]\}$ of $2^d$ distinct sets such that for every $I,J \subseteq [d]$, both $F_I \cup F_J=F_{I \cup J}$ and $F_I \cap F_J = F_{I \cap J}$ hold. A family ${\mathcal F}$ is a-union-free if $F_1\cup \dots \cup F_a \neq F_{a+1}$ whenever $F_1,\dots,F_{a+1}$ are distinct sets in ${\mathcal F}$. We verify a conjecture of Erdős and Shelah that $f(m, B_2\text{\rm -free})=\Theta(m^{2/3})$. We also obtain lower and upper bounds for $f(m, B_d\text{\rm -free})$ and $f(m,a\text{\rm -union free})$.

A set $\mathcal{F}$ of ordered k-tuples of distinct elements of an n-set is pairwise reverse free if it does not contain two ordered k-tuples with the same pair of elements in the same pair of coordinates in reverse order. Let $F(n,k)$ be the maximum size of a pairwise reverse-free set. In this paper we focus on the case of 3-tuples and prove $\lim F(n,3)/\binom{n}{3}=5/4$, more exactly, $\frac{5}{24}n^3-\frac{1}{2}n^2-O(n\log n)

We prove that dual graphs and relational structures are connected. Moreover we give efficient bounds for their diameter: a linear bound in the case of oriented graphs (and this is best up to a constant) and a polynomial bound in the case of relational structures.