Mattheus, Sam; Pavese, Francesco Triangle-free induced subgraphs of the unitary polarity graph. (English) Zbl 1390.05109 Eur. J. Comb. 72, 83-96 (2018). Summary: Let \(\bot\) be a unitary polarity of a finite projective plane \(\pi\) of order \(q^2\). The unitary polarity graph is the graph with vertex set the points of \(\pi\) where two vertices \(x\) and \(y\) are adjacent if \(x \in y^\bot\). We show that a triangle-free induced subgraph of the unitary polarity graph of an arbitrary projective plane has at most \((q^4 + q)/2\) vertices. When \(\pi\) is the Desarguesian projective plane \(\operatorname{PG}(2, q^2)\) and \(q\) is even, we show that the upper bound is asymptotically sharp, by providing an example on \(q^4/2\) vertices. Finally, the case when \(\pi\) is the Figueroa plane is discussed. Cited in 1 Document MSC: 05C35 Extremal problems in graph theory 51A35 Non-Desarguesian affine and projective planes 51E21 Blocking sets, ovals, \(k\)-arcs Keywords:oval; hyperovals; Figueroa planes; unitals Software:Magma PDFBibTeX XMLCite \textit{S. Mattheus} and \textit{F. Pavese}, Eur. J. Comb. 72, 83--96 (2018; Zbl 1390.05109) Full Text: DOI arXiv References: [1] Baer, R., Polarities in finite projective planes, Bull. Amer. Math. Soc., 52, 77-93, (1946) · Zbl 0060.32308 [2] Barwick, S.; Ebert, G., (Unitals in Projective Planes, Springer Monographs in Mathematics, (2008), Springer New York) · Zbl 1156.51006 [3] A. Bishnoi, S. Mattheus, J. Schillewaert, Minimal multiple blocking sets, 2017, https://arxiv.org/abs/1703.07843; A. Bishnoi, S. Mattheus, J. Schillewaert, Minimal multiple blocking sets, 2017, https://arxiv.org/abs/1703.07843 · Zbl 1410.51009 [4] A. Bishnoi, A. Potukuchi, Personal communication.; A. Bishnoi, A. Potukuchi, Personal communication. [5] Bong, N. H., Properties and structures in extremal graphs, (2017), University of Newcastle Australia, (Ph.D. thesis) [6] Bosma, W.; Cannon, J.; Playoust, C., The magma algebra system. I. the user language. computational algebra and number theory, J. Symbolic Comput., 24, 235-265, (1997) · Zbl 0898.68039 [7] Brown, J. M.N., Some partitions in figueroa planes, Note Math., 29, 33-44, (2009) · Zbl 1252.51005 [8] Calderbank, R.; Kantor, W. M., The geometry of two-weight codes, Bull. Lond. Math. Soc., 18, 97-122, (1986) · Zbl 0582.94019 [9] B. Csajbók, Personal communication.; B. Csajbók, Personal communication. [10] De Bruyn, B.; Suzuki, H., Intriguing sets of vertices of regular graphs, Graphs Combin., 26, 629-646, (2010) · Zbl 1230.05297 [11] De Resmini, M.; Hamilton, N., Hyperovals and unitals in figueroa planes, European J. Combin., 19, 215-220, (1998) · Zbl 0917.51001 [12] Figueroa, R., A family of not \((V, l)\)-transitive projective planes of order \(q^3\), \(q \not\equiv 1(\operatorname{mod} 3)\) and \(q > 2\), Math. Z., 181, 471-479, (1982) · Zbl 0477.51009 [13] Füredi, Z., Graphs without quadrilaterals, J. Combin. Theory Ser. B, 34, 187-190, (1983) · Zbl 0505.05038 [14] Füredi, Z., On the number of edges of quadrilateral-free graphs, J. Combin. Theory Ser. B, 68, 1-6, (1996) · Zbl 0858.05063 [15] Godsil, C. D.; Newman, M. W., Eigenvalue bounds for independent sets, J. Combin. Theory Ser. B, 98, 721-734, (2008) · Zbl 1156.05041 [16] Grundhöfer, T., A synthetic construction of the figueroa planes, J. Geom., 26, 191-201, (1986) · Zbl 0595.51010 [17] Haemers, W. H., Eigenvalue techniques in design and graph theory, (1979), University of Eindhoven, (Ph.D. thesis) · Zbl 0429.05012 [18] Haemers, W. H., Interlacing eigenvalues and graphs, Linear Algebra Appl., 226/228, 593-616, (1995) · Zbl 0831.05044 [19] Hamilton, N., Maximal arcs in finite projective planes and associated structures in projective spaces, (1995), University of Western Australia, (Ph.D. thesis) [20] Hering, Ch.; Schaeffer, H. J., On the new projective planes of R figueroa, (Jungnickel, D.; etal., Combinatorial Theory. Proc. Schloss Rauischholzhausen, 1982, (1982), Springer Berlin), 187-190 · Zbl 0488.00006 [21] Hirschfeld, J. W.P., (Projective Geometries over Finite Fields, Oxford Mathematical Monographs, (1998), Oxford Science Publications, The Clarendon Press, Oxford University Press, New York) · Zbl 0899.51002 [22] Hughes, D.; Piper, F., (Projective Planes, Graduate Texts in Mathematics, (1973), Springer-Verlag New York-Berlin) · Zbl 0267.50018 [23] Lazebnik, F.; Verstraete, J., On hypergraphs of girth five, Electron. J. Combin., 10, 25, (2003) · Zbl 1023.05131 [24] J. Loucks, C. Timmons, Triangle-free induced subgraphs of polarity graphs, 2017, https://arxiv.org/abs/1703.06347; J. Loucks, C. Timmons, Triangle-free induced subgraphs of polarity graphs, 2017, https://arxiv.org/abs/1703.06347 [25] Lund, B.; Saraf, S., Incidence bounds for block designs, SIAM J. Discrete Math., 30, 1997-2010, (2016) · Zbl 1353.05028 [26] S. Mattheus, F. Pavese, L. Storme, On the independence number of graphs related to a polarity, 2017, https://arxiv.org/pdf/1704.00487; S. Mattheus, F. Pavese, L. Storme, On the independence number of graphs related to a polarity, 2017, https://arxiv.org/pdf/1704.00487 [27] Mubayi, D.; Williford, J., On the independence number of the Erdős-Rényi and projective norm graphs and a related hypergraph, J. Graph Theory, 56, 113-127, (2007) · Zbl 1128.05040 [28] Parsons, T. D., Graphs from projective planes, Aequationes Math., 14, 167-189, (1976) · Zbl 0323.05116 [29] Penttila, T.; Royle, G., Sets of type \((m n)\) in the affine and projective planes of order nine, Des. Codes Cryptogr., 6, 229-245, (1995) · Zbl 0841.05012 [30] Piper, F., Polarities in the Hughes plane, Bull. Lond. Math. Soc., 2, 209-213, (1970) · Zbl 0204.53701 [31] Winter, S. D.; Schillewaert, J.; Verstraete, J., Large incidence-free sets in geometries, Electron. J. Combin., 19, 24, (2012) · Zbl 1266.51004 [32] Xing, P.; Tait, M.; Timmons, C., On the chromatic number of the Erdős-Rényi orthogonal polarity graph, Electron. J. Combin., 22, 2, 21, (2015) · Zbl 1312.05053 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.