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]

Mostafa Mbekhta. Representation and approximation of the polar factor of an operator on a Hilbert space. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020463

[2]

Andy Hammerlindl, Jana Rodriguez Hertz, Raúl Ures. Ergodicity and partial hyperbolicity on Seifert manifolds. Journal of Modern Dynamics, 2020, 16: 331-348. doi: 10.3934/jmd.2020012

[3]

Hirokazu Ninomiya. Entire solutions of the Allen–Cahn–Nagumo equation in a multi-dimensional space. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 395-412. doi: 10.3934/dcds.2020364

[4]

Hua Qiu, Zheng-An Yao. The regularized Boussinesq equations with partial dissipations in dimension two. Electronic Research Archive, 2020, 28 (4) : 1375-1393. doi: 10.3934/era.2020073

[5]

Lorenzo Zambotti. A brief and personal history of stochastic partial differential equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 471-487. doi: 10.3934/dcds.2020264

[6]

Yueyang Zheng, Jingtao Shi. A stackelberg game of backward stochastic differential equations with partial information. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020047

[7]

Awais Younus, Zoubia Dastgeer, Nudrat Ishaq, Abdul Ghaffar, Kottakkaran Sooppy Nisar, Devendra Kumar. On the observability of conformable linear time-invariant control systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020444

[8]

Touria Karite, Ali Boutoulout. Global and regional constrained controllability for distributed parabolic linear systems: RHum approach. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020055

[9]

Yongge Tian, Pengyang Xie. Simultaneous optimal predictions under two seemingly unrelated linear random-effects models. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020168

[10]

Chao Wang, Qihuai Liu, Zhiguo Wang. Periodic bouncing solutions for Hill's type sub-linear oscillators with obstacles. Communications on Pure & Applied Analysis, 2021, 20 (1) : 281-300. doi: 10.3934/cpaa.2020266

[11]

Zexuan Liu, Zhiyuan Sun, Jerry Zhijian Yang. A numerical study of superconvergence of the discontinuous Galerkin method by patch reconstruction. Electronic Research Archive, 2020, 28 (4) : 1487-1501. doi: 10.3934/era.2020078

[12]

Vieri Benci, Marco Cococcioni. The algorithmic numbers in non-archimedean numerical computing environments. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020449

[13]

Manuel Friedrich, Martin Kružík, Jan Valdman. Numerical approximation of von Kármán viscoelastic plates. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 299-319. doi: 10.3934/dcdss.2020322

[14]

Leilei Wei, Yinnian He. A fully discrete local discontinuous Galerkin method with the generalized numerical flux to solve the tempered fractional reaction-diffusion equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020319

[15]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

[16]

Omid Nikan, Seyedeh Mahboubeh Molavi-Arabshai, Hossein Jafari. Numerical simulation of the nonlinear fractional regularized long-wave model arising in ion acoustic plasma waves. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020466

[17]

Christopher S. Goodrich, Benjamin Lyons, Mihaela T. Velcsov. Analytical and numerical monotonicity results for discrete fractional sequential differences with negative lower bound. Communications on Pure & Applied Analysis, 2021, 20 (1) : 339-358. doi: 10.3934/cpaa.2020269

2019 Impact Factor: 0.734

Metrics

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

Other articles
by authors

[Back to Top]