BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We introduce and study embeddings of graphs in finite projective planes, and present related results for some families of graphs including complete graphs and complete bipartite graphs. We also make connections between embeddings of graphs and the existence of certain substructures in a plane, such as Baer subplanes and arcs.
Fix integers n≥r≥2. A clique partition of (r[n]) is a collection of proper subsets A1,A2,...,At⊂[n] such that ⋃i(rAi) is a partition of (r[n]). Clique partitions are related to design theory, coding theory, projective geometry, and extremal combinatorics. Let $\cp(n,r)$ denote the minimum size of a clique partition of (r[n]). A classical theorem of de Bruijn and Erd\H os states that $\cp(n, 2) = n$ and also determines the extremal configurations. In this paper we study $\cp(n,r)$, and show in general that for each fixed r≥3, \[\cp(n,r) \geq (1 + o(1))n^{r/2} \quad \quad {as}n \to \infty.\] We conjecture $\cp(n,r) = (1 + o(1))n^{r/2}$, and prove this conjecture in a very strong sense for r=3 by giving a characterization of optimal clique partitions of (3[n]) for infinitely many n. Precisely, when n=q2+1 and q is a prime power, we show \[ \cp(n,3) = n\sqrt{n-1} \] and characterize those clique partitions achieving equality. We also give an absolute lower bound $\cp(n,r) \geq {n \choose r}/{q + r - 1 \choose r}$ when n=q2+q+r−1, and for each r characterize the finitely many configurations achieving equality with the lower bound. Finally we note the connection of $\cp(n,r)$ to extremal graph theory, and determine some new asymptotically sharp bounds for the Zarankiewicz problem.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.