BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Keith E. Mellinger appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
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.
Published work
We define and study embeddings of cycles in finite affine and projective planes. We show that for all $k$, $3\le k\le q^2$, a $k$-cycle can be embedded in any affine plane of order $q$. We also prove a similar result for finite projective planes: for all $k$, $3\le k\le q^2+q+1$, a $k$-cycle can be embedded in any projective plane of order $q$.
Fix integers $n \ge r \ge 2$. A clique partition of ${[n] \choose r}$ is a collection of proper subsets $A_1, A_2, \ldots, A_t \subset [n]$ such that $\bigcup_i{A_i \choose r}$ is a partition of ${[n] \choose r}$. Let $\cp(n,r)$ denote the minimum size of a clique partition of ${[n] \choose r}$. A classical theorem of de Bruijn and Erd\H os states that $\cp(n, 2) = n$. In this paper we study $\cp(n,r)$, and show in general that for each fixed $r \geq 3$, \[ \cp(n,r) \geq (1 + o(1))n^{r/2} \quad \quad \mbox{as}n \rightarrow \infty.\] We conjecture $\cp(n,r) = (1 + o(1))n^{r/2}$. This conjecture has already been verified (in a very strong sense) for $r = 3$ by Hartman-Mullin-Stinson. We give further evidence of this conjecture by constructing, for each $r \ge 4$, a family of $(1+o(1))n^{r/2}$ subsets of $[n]$ with the following property: no two $r$-sets of $[n]$ are covered more than once and all but $o(n^r)$ of the $r$-sets of $[n]$ are covered. We also give an absolute lower bound $\cp(n,r) \geq {n \choose r}/{q + r - 1 \choose r}$ when $n = q^2 + 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.