Article Contents
Article Contents

# Associating a numerical semigroup to the triangle-free configurations

• It is proved that a numerical semigroup can be associated to the triangle-free $(r,k)$-configurations, and some results on existence are deduced. For example it is proved that for any $r,k\geq 2$ there exists infinitely many $(r,k)$-configurations. Most proofs are given from a graph theoretical point of view, in the sense that the configurations are represented by their incidence graphs. An application to private information retrieval is described.
Mathematics Subject Classification: Primary: 05B30; Secondary: 51E30, 20M99.

 Citation:

•  [1] G. Araujo-Pardo, On upper bounds of odd girth cages, Discrete Math., 310 (2010), 1622-1626.doi: 10.1016/j.disc.2009.12.025. [2] C. Balbuena, A construction of small regular bipartite graphs of girth 8, Discrete Math. Theor. Comp. Sci., 11 (2009), 33-46. [3] A. Betten, G. Brinkmann and T. Pisanski, Counting symmetric configurations $v_3$, Discrete Appl. Math., 99 (2000), 331-338.doi: 10.1016/S0166-218X(99)00143-2. [4] N. Biggs, "Algebraic Graph Theory," 2nd edition, Cambridge University Press, Cambridge, 1993. [5] J. G. Bokowski, "Computational Oriented Matroids," Cambridge University Press, Cambridge, 2006. [6] M. Bras-Amorós and K. Stokes, The semigroup of combinatorial configurations, preprint, arXiv:0907.4230v3 [7] F. De Clerck, J. A. Thas and H. Van Maldeghem, Generalized polygons and semipartial geometries, EIDMA minicourse, 1996. [8] J. Domingo-Ferrer and M. Bras-Amorós, Peer-to-peer private information retrieval, in "Privacy in Statistical Databases,'' (2008), 315-323. [9] J. Domingo-Ferrer, M. Bras-Amorós, Q. Wu and J. Manjón, User-private information retrieval based on a peer-to-peer community, Data Knowl. Eng., 68 (2009), 1237-1252.doi: 10.1016/j.datak.2009.06.004. [10] M. Flanagan, M. Greferath and C. Roessing, An encoding scheme, and a decoding scheme using a series of LDPC codes based on finite inversive spaces, Technical Publication, 2007. [11] M. Flanagan, M. Greferath and C. Roessing, On LDPC codes from $(0,1)$-geometries induced by finite inversive spaces of even order, in "Workshop on Coding and Cryptography 2007, WCC '07,'' Versailles, France, 2007. [12] A. Gács and T. Héger, On geometric constructions of $(k,g)$-graphs, Contrib. Discrete Math., 3 (2008), 63-80. [13] H. Gropp, Configurations, in "The CRC Handbook Of Combinatorial Designs" (eds. C.J. Colbourn and J.H. Dinitz), 2nd edition, CRC Press, Boca Raton, FL, (2007), 352-355. [14] B. Grünbaum, "Configurations of Points and Lines,'' American Mathematical Society, Providence, RI, 2009. [15] F. Lazebnik, V. A. Ustimenko and A. J. Woldar, New upper bounds on the order of cages, Electr. J. Combin., 4 (1997), 11. [16] J. Lee and D. R. Stinson, A combinatorial approach to key predistribution for distributed sensor networks, in "IEEE Wireless Communications and Networking Conference, CD-ROM,'' paper PHY53-06, (2005), 6. [17] J. Lee and D. R. Stinson, On the construction of practical key predistribution schemes for distributed sensor networks using combinatorial designs, ACM Trans. Inf. Syst. Secur., 11 (2008), 1-35.doi: 10.1145/1330332.1330333. [18] V. Martinetti, Sopra alcune configurazioni piane, Annali Mat. Pura Appl (1867-1897), 14 (1886), 161-192. [19] J. M. F Moura, J. Lu and H. Zhang, Structured LDPC codes with large girth, in "IEEE Signal Processing Magazine, Special Issue on Iterative Signal Processing for Communications,'' 21 (2004), 42-55. [20] S. E. Payne and J. A. Thas, "Finite Generalized Quadrangles,'' European Math. Soc., Zürich, 2009. [21] T. Pisanski, Yet another look at the Gray graph, New Zealand J. Math, 36 (2007), 85-92. [22] T. Pisanski, M. Boben and D. Marušič, A. Orbanić and A. Graovac, The 10-cages and derived configurations, Discrete Math., 275 (2004), 265-276.doi: 10.1016/S0012-365X(03)00110-9. [23] J. L. Ramírez Alfonsín, "The Diophantine Frobenius Problem,'' Oxford University Press, Oxford, 2005. [24] J. C. Rosales and P. A. García-Sánchez, "Numerical Semigroups,'' Springer, New York, 2009. [25] H. Sachs, Regular graphs with given girth and restricted circuits, J. London Math. Soc., 38 (1963), 423-429.doi: 10.1112/jlms/s1-38.1.423. [26] K. Sinha, A triangle free configuration, Časopis Pěst. Mat., 103 (1978), 147-148, 202. [27] K. Stokes and M. Bras-Amorós, Optimal configurations for peer-to-peer user-private information retrieval, Comp. Math. Appl., 59 (2010), 1568-1577.doi: 10.1016/j.camwa.2010.01.003. [28] L. Storme, Finite geometry, in "The CRC Handbook Of Combinatorial Designs" (eds. C.J. Colbourn and J.H. Dinitz), 2nd edition, CRC Press, Boca Raton, FL, (2007), 702-729. [29] B. Vasic and O. Milenkovic, Combinatorial constructions of low-density parity-check codes for iterative decoding, IEEE Trans. Inform. Theory, 50 (2004), 1156-1176.doi: 10.1109/TIT.2004.828066. [30] A. Viejo and J. Castellà-Roca, Using social networks to distort users' profiles generated by web search engines, Computer Networks, 54 (2010), 1343-1357.doi: 10.1016/j.comnet.2009.11.003. [31] E. Visconti, Sulle configurazioni piane atrigone, Giornale Mat. Battaglini, 54 (1916), 27-41. [32] P. K. Wong, Cages-a survey, J. Graph Theory, 6 (1982), 1-22.doi: 10.1002/jgt.3190060103.