May  2011, 5(2): 351-371. doi: 10.3934/amc.2011.5.351

Associating a numerical semigroup to the triangle-free configurations

1. 

Universitat Rovira i Virgili, Av. Països Catalans 26, 43007, Tarragona, Catalonia, Spain, Spain

Received  April 2010 Revised  March 2011 Published  May 2011

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.
Citation: Klara Stokes, Maria Bras-Amorós. Associating a numerical semigroup to the triangle-free configurations. Advances in Mathematics of Communications, 2011, 5 (2) : 351-371. doi: 10.3934/amc.2011.5.351
References:
[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.

show all references

References:
[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.

[1]

Jeffrey K. Lawson, Tanya Schmah, Cristina Stoica. Euler-Poincaré reduction for systems with configuration space isotropy. Journal of Geometric Mechanics, 2011, 3 (2) : 261-275. doi: 10.3934/jgm.2011.3.261

[2]

Heiko Enderling, Alexander R.A. Anderson, Mark A.J. Chaplain, Glenn W.A. Rowe. Visualisation of the numerical solution of partial differential equation systems in three space dimensions and its importance for mathematical models in biology. Mathematical Biosciences & Engineering, 2006, 3 (4) : 571-582. doi: 10.3934/mbe.2006.3.571

[3]

Xin Yu, Guojie Zheng, Chao Xu. The $C$-regularized semigroup method for partial differential equations with delays. Discrete and Continuous Dynamical Systems, 2016, 36 (9) : 5163-5181. doi: 10.3934/dcds.2016024

[4]

Lili Ju, Wei Leng, Zhu Wang, Shuai Yuan. Numerical investigation of ensemble methods with block iterative solvers for evolution problems. Discrete and Continuous Dynamical Systems - B, 2020, 25 (12) : 4905-4923. doi: 10.3934/dcdsb.2020132

[5]

Susanne Pumplün, Thomas Unger. Space-time block codes from nonassociative division algebras. Advances in Mathematics of Communications, 2011, 5 (3) : 449-471. doi: 10.3934/amc.2011.5.449

[6]

Fang Chen, Ning Gao, Yao- Lin Jiang. On product-type generalized block AOR method for augmented linear systems. Numerical Algebra, Control and Optimization, 2012, 2 (4) : 797-809. doi: 10.3934/naco.2012.2.797

[7]

Magdi S. Mahmoud, Mohammed M. Hussain. Control design of linear systems with saturating actuators: A survey. Numerical Algebra, Control and Optimization, 2012, 2 (2) : 413-435. doi: 10.3934/naco.2012.2.413

[8]

Gianluca Mola, Noboru Okazawa, Jan Prüss, Tomomi Yokota. Semigroup-theoretic approach to identification of linear diffusion coefficients. Discrete and Continuous Dynamical Systems - S, 2016, 9 (3) : 777-790. doi: 10.3934/dcdss.2016028

[9]

Onur Alp İlhan. Solvability of some partial integral equations in Hilbert space. Communications on Pure and Applied Analysis, 2008, 7 (4) : 837-844. doi: 10.3934/cpaa.2008.7.837

[10]

Mario Grassi, Giuseppe Pontrelli, Luciano Teresi, Gabriele Grassi, Lorenzo Comel, Alessio Ferluga, Luigi Galasso. Novel design of drug delivery in stented arteries: A numerical comparative study. Mathematical Biosciences & Engineering, 2009, 6 (3) : 493-508. doi: 10.3934/mbe.2009.6.493

[11]

Hassan Khodaiemehr, Dariush Kiani. High-rate space-time block codes from twisted Laurent series rings. Advances in Mathematics of Communications, 2015, 9 (3) : 255-275. doi: 10.3934/amc.2015.9.255

[12]

Susanne Pumplün, Andrew Steele. The nonassociative algebras used to build fast-decodable space-time block codes. Advances in Mathematics of Communications, 2015, 9 (4) : 449-469. doi: 10.3934/amc.2015.9.449

[13]

Susanne Pumplün. How to obtain division algebras used for fast-decodable space-time block codes. Advances in Mathematics of Communications, 2014, 8 (3) : 323-342. doi: 10.3934/amc.2014.8.323

[14]

Eugenia N. Petropoulou, Panayiotis D. Siafarikas. Polynomial solutions of linear partial differential equations. Communications on Pure and Applied Analysis, 2009, 8 (3) : 1053-1065. doi: 10.3934/cpaa.2009.8.1053

[15]

Farid Ammar Khodja, Franz Chouly, Michel Duprez. Partial null controllability of parabolic linear systems. Mathematical Control and Related Fields, 2016, 6 (2) : 185-216. doi: 10.3934/mcrf.2016001

[16]

Emmanuel Trélat. Optimal control of a space shuttle, and numerical simulations. Conference Publications, 2003, 2003 (Special) : 842-851. doi: 10.3934/proc.2003.2003.842

[17]

Liqiang Jin, Yanqing Liu, Yanyan Yin, Kok Lay Teo, Fei Liu. Design of probabilistic $ l_2-l_\infty $ filter for uncertain Markov jump systems with partial information of the transition probabilities. Journal of Industrial and Management Optimization, 2022, 18 (4) : 2335-2349. doi: 10.3934/jimo.2021070

[18]

Roberto Camassa, Pao-Hsiung Chiu, Long Lee, W.-H. Sheu. A particle method and numerical study of a quasilinear partial differential equation. Communications on Pure and Applied Analysis, 2011, 10 (5) : 1503-1515. doi: 10.3934/cpaa.2011.10.1503

[19]

Minoo Kamrani. Numerical solution of partial differential equations with stochastic Neumann boundary conditions. Discrete and Continuous Dynamical Systems - B, 2019, 24 (10) : 5337-5354. doi: 10.3934/dcdsb.2019061

[20]

Vianney Perchet, Marc Quincampoix. A differential game on Wasserstein space. Application to weak approachability with partial monitoring. Journal of Dynamics and Games, 2019, 6 (1) : 65-85. doi: 10.3934/jdg.2019005

2020 Impact Factor: 0.935

Metrics

  • PDF downloads (116)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]