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.

[2]

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

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

[4]

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

[5]

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

[6]

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

[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, (2008), 315.

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

[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, (2007).

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

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

[18]

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

[19]

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

[20]

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

[21]

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

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

[23]

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

[24]

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

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

[26]

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

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

[28]

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

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

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

[31]

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

[32]

P. K. Wong, Cages-a survey,, J. Graph Theory, 6 (1982), 1. 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. 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.

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

[4]

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

[5]

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

[6]

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

[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, (2008), 315.

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

[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, (2007).

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

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

[18]

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

[19]

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

[20]

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

[21]

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

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

[23]

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

[24]

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

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

[26]

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

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

[28]

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

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

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

[31]

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

[32]

P. K. Wong, Cages-a survey,, J. Graph Theory, 6 (1982), 1. 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 & 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]

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

[6]

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

[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]

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

[14]

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

[15]

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

[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]

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

[18]

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

[19]

George Avalos, Roberto Triggiani. Semigroup well-posedness in the energy space of a parabolic-hyperbolic coupled Stokes-Lamé PDE system of fluid-structure interaction. Discrete & Continuous Dynamical Systems - S, 2009, 2 (3) : 417-447. doi: 10.3934/dcdss.2009.2.417

[20]

G. Acosta, Julián Fernández Bonder, P. Groisman, J.D. Rossi. Numerical approximation of a parabolic problem with a nonlinear boundary condition in several space dimensions. Discrete & Continuous Dynamical Systems - B, 2002, 2 (2) : 279-294. doi: 10.3934/dcdsb.2002.2.279

2016 Impact Factor: 0.8

Metrics

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

Other articles
by authors

[Back to Top]