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. doi: 10.1016/j.disc.2009.12.025. Google Scholar

[2]

C. Balbuena, A construction of small regular bipartite graphs of girth 8,, Discrete Math. Theor. Comp. Sci., 11 (2009), 33. Google Scholar

[3]

A. Betten, G. Brinkmann and T. Pisanski, Counting symmetric configurations $v_3$,, Discrete Appl. Math., 99 (2000), 331. doi: 10.1016/S0166-218X(99)00143-2. Google Scholar

[4]

N. Biggs, "Algebraic Graph Theory," 2nd edition,, Cambridge University Press, (1993). Google Scholar

[5]

J. G. Bokowski, "Computational Oriented Matroids,", Cambridge University Press, (2006). Google Scholar

[6]

M. Bras-Amorós and K. Stokes, The semigroup of combinatorial configurations,, preprint, (). Google Scholar

[7]

F. De Clerck, J. A. Thas and H. Van Maldeghem, Generalized polygons and semipartial geometries,, EIDMA minicourse, (1996). Google Scholar

[8]

J. Domingo-Ferrer and M. Bras-Amorós, Peer-to-peer private information retrieval,, in, (2008), 315. Google Scholar

[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. doi: 10.1016/j.datak.2009.06.004. Google Scholar

[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). Google Scholar

[11]

M. Flanagan, M. Greferath and C. Roessing, On LDPC codes from $(0,1)$-geometries induced by finite inversive spaces of even order,, in, (2007). Google Scholar

[12]

A. Gács and T. Héger, On geometric constructions of $(k,g)$-graphs,, Contrib. Discrete Math., 3 (2008), 63. Google Scholar

[13]

H. Gropp, Configurations,, in, (2007), 352. Google Scholar

[14]

B. Grünbaum, "Configurations of Points and Lines,'', American Mathematical Society, (2009). Google Scholar

[15]

F. Lazebnik, V. A. Ustimenko and A. J. Woldar, New upper bounds on the order of cages,, Electr. J. Combin., 4 (1997). Google Scholar

[16]

J. Lee and D. R. Stinson, A combinatorial approach to key predistribution for distributed sensor networks,, in, (2005), 53. Google Scholar

[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. doi: 10.1145/1330332.1330333. Google Scholar

[18]

V. Martinetti, Sopra alcune configurazioni piane,, Annali Mat. Pura Appl (1867-1897), 14 (1886), 1867. Google Scholar

[19]

J. M. F Moura, J. Lu and H. Zhang, Structured LDPC codes with large girth,, in, 21 (2004), 42. Google Scholar

[20]

S. E. Payne and J. A. Thas, "Finite Generalized Quadrangles,'', European Math. Soc., (2009). Google Scholar

[21]

T. Pisanski, Yet another look at the Gray graph,, New Zealand J. Math, 36 (2007), 85. Google Scholar

[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. doi: 10.1016/S0012-365X(03)00110-9. Google Scholar

[23]

J. L. Ramírez Alfonsín, "The Diophantine Frobenius Problem,'', Oxford University Press, (2005). Google Scholar

[24]

J. C. Rosales and P. A. García-Sánchez, "Numerical Semigroups,'', Springer, (2009). Google Scholar

[25]

H. Sachs, Regular graphs with given girth and restricted circuits,, J. London Math. Soc., 38 (1963), 423. doi: 10.1112/jlms/s1-38.1.423. Google Scholar

[26]

K. Sinha, A triangle free configuration,, Časopis Pěst. Mat., 103 (1978), 147. Google Scholar

[27]

K. Stokes and M. Bras-Amorós, Optimal configurations for peer-to-peer user-private information retrieval,, Comp. Math. Appl., 59 (2010), 1568. doi: 10.1016/j.camwa.2010.01.003. Google Scholar

[28]

L. Storme, Finite geometry,, in, (2007), 702. Google Scholar

[29]

B. Vasic and O. Milenkovic, Combinatorial constructions of low-density parity-check codes for iterative decoding,, IEEE Trans. Inform. Theory, 50 (2004), 1156. doi: 10.1109/TIT.2004.828066. Google Scholar

[30]

A. Viejo and J. Castellà-Roca, Using social networks to distort users' profiles generated by web search engines,, Computer Networks, 54 (2010), 1343. doi: 10.1016/j.comnet.2009.11.003. Google Scholar

[31]

E. Visconti, Sulle configurazioni piane atrigone,, Giornale Mat. Battaglini, 54 (1916), 27. Google Scholar

[32]

P. K. Wong, Cages-a survey,, J. Graph Theory, 6 (1982), 1. doi: 10.1002/jgt.3190060103. Google Scholar

show all references

References:
[1]

G. Araujo-Pardo, On upper bounds of odd girth cages,, Discrete Math., 310 (2010), 1622. doi: 10.1016/j.disc.2009.12.025. Google Scholar

[2]

C. Balbuena, A construction of small regular bipartite graphs of girth 8,, Discrete Math. Theor. Comp. Sci., 11 (2009), 33. Google Scholar

[3]

A. Betten, G. Brinkmann and T. Pisanski, Counting symmetric configurations $v_3$,, Discrete Appl. Math., 99 (2000), 331. doi: 10.1016/S0166-218X(99)00143-2. Google Scholar

[4]

N. Biggs, "Algebraic Graph Theory," 2nd edition,, Cambridge University Press, (1993). Google Scholar

[5]

J. G. Bokowski, "Computational Oriented Matroids,", Cambridge University Press, (2006). Google Scholar

[6]

M. Bras-Amorós and K. Stokes, The semigroup of combinatorial configurations,, preprint, (). Google Scholar

[7]

F. De Clerck, J. A. Thas and H. Van Maldeghem, Generalized polygons and semipartial geometries,, EIDMA minicourse, (1996). Google Scholar

[8]

J. Domingo-Ferrer and M. Bras-Amorós, Peer-to-peer private information retrieval,, in, (2008), 315. Google Scholar

[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. doi: 10.1016/j.datak.2009.06.004. Google Scholar

[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). Google Scholar

[11]

M. Flanagan, M. Greferath and C. Roessing, On LDPC codes from $(0,1)$-geometries induced by finite inversive spaces of even order,, in, (2007). Google Scholar

[12]

A. Gács and T. Héger, On geometric constructions of $(k,g)$-graphs,, Contrib. Discrete Math., 3 (2008), 63. Google Scholar

[13]

H. Gropp, Configurations,, in, (2007), 352. Google Scholar

[14]

B. Grünbaum, "Configurations of Points and Lines,'', American Mathematical Society, (2009). Google Scholar

[15]

F. Lazebnik, V. A. Ustimenko and A. J. Woldar, New upper bounds on the order of cages,, Electr. J. Combin., 4 (1997). Google Scholar

[16]

J. Lee and D. R. Stinson, A combinatorial approach to key predistribution for distributed sensor networks,, in, (2005), 53. Google Scholar

[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. doi: 10.1145/1330332.1330333. Google Scholar

[18]

V. Martinetti, Sopra alcune configurazioni piane,, Annali Mat. Pura Appl (1867-1897), 14 (1886), 1867. Google Scholar

[19]

J. M. F Moura, J. Lu and H. Zhang, Structured LDPC codes with large girth,, in, 21 (2004), 42. Google Scholar

[20]

S. E. Payne and J. A. Thas, "Finite Generalized Quadrangles,'', European Math. Soc., (2009). Google Scholar

[21]

T. Pisanski, Yet another look at the Gray graph,, New Zealand J. Math, 36 (2007), 85. Google Scholar

[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. doi: 10.1016/S0012-365X(03)00110-9. Google Scholar

[23]

J. L. Ramírez Alfonsín, "The Diophantine Frobenius Problem,'', Oxford University Press, (2005). Google Scholar

[24]

J. C. Rosales and P. A. García-Sánchez, "Numerical Semigroups,'', Springer, (2009). Google Scholar

[25]

H. Sachs, Regular graphs with given girth and restricted circuits,, J. London Math. Soc., 38 (1963), 423. doi: 10.1112/jlms/s1-38.1.423. Google Scholar

[26]

K. Sinha, A triangle free configuration,, Časopis Pěst. Mat., 103 (1978), 147. Google Scholar

[27]

K. Stokes and M. Bras-Amorós, Optimal configurations for peer-to-peer user-private information retrieval,, Comp. Math. Appl., 59 (2010), 1568. doi: 10.1016/j.camwa.2010.01.003. Google Scholar

[28]

L. Storme, Finite geometry,, in, (2007), 702. Google Scholar

[29]

B. Vasic and O. Milenkovic, Combinatorial constructions of low-density parity-check codes for iterative decoding,, IEEE Trans. Inform. Theory, 50 (2004), 1156. doi: 10.1109/TIT.2004.828066. Google Scholar

[30]

A. Viejo and J. Castellà-Roca, Using social networks to distort users' profiles generated by web search engines,, Computer Networks, 54 (2010), 1343. doi: 10.1016/j.comnet.2009.11.003. Google Scholar

[31]

E. Visconti, Sulle configurazioni piane atrigone,, Giornale Mat. Battaglini, 54 (1916), 27. Google Scholar

[32]

P. K. Wong, Cages-a survey,, J. Graph Theory, 6 (1982), 1. doi: 10.1002/jgt.3190060103. Google Scholar

[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 & Continuous Dynamical Systems - A, 2016, 36 (9) : 5163-5181. doi: 10.3934/dcds.2016024

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

Eugenia N. Petropoulou, Panayiotis D. Siafarikas. Polynomial solutions of linear partial differential equations. Communications on Pure & 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 & Related Fields, 2016, 6 (2) : 185-216. doi: 10.3934/mcrf.2016001

[16]

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 & Applied Analysis, 2011, 10 (5) : 1503-1515. doi: 10.3934/cpaa.2011.10.1503

[17]

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

[18]

Valter Pohjola. An inverse problem for the magnetic Schrödinger operator on a half space with partial data. Inverse Problems & Imaging, 2014, 8 (4) : 1169-1189. doi: 10.3934/ipi.2014.8.1169

[19]

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

[20]

Lars Grüne, Manuela Sigurani. Numerical event-based ISS controller design via a dynamic game approach. Journal of Computational Dynamics, 2015, 2 (1) : 65-81. doi: 10.3934/jcd.2015.2.65

2018 Impact Factor: 0.879

Metrics

  • PDF downloads (5)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]