
arXiv: 1601.05058
Given a projective plane $��$ and a polarity $��$ of $��$, the corresponding polarity graph is the graph whose vertices are the points of $��$, and two distinct points $p_1$ and $p_2$ are adjacent if $p_1$ is incident to $p_2^{ ��}$ in $��$. A well-known example of a polarity graph is the Erd��s-R��nyi orthogonal polarity graph $ER_q$, which appears frequently in a variety of extremal problems. Eigenvalue methods provide an upper bound on the independence number of any polarity graph. Mubayi and Williford showed that in the case of $ER_q$, the eigenvalue method gives the correct upper bound in order of magnitude. We prove that this is also true for other families of polarity graphs. This includes a family of polarity graphs for which the polarity is neither orthogonal nor unitary. We conjecture that any polarity graph of a projective plane of order $q$ has an independent set of size $��(q^{3/2})$. Some related results are also obtained.
Extremal problems in graph theory, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), independent sets, FOS: Mathematics, Mathematics - Combinatorics, polarity graphs, Combinatorics (math.CO), polarities
Extremal problems in graph theory, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), independent sets, FOS: Mathematics, Mathematics - Combinatorics, polarity graphs, Combinatorics (math.CO), polarities
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
