{"entities":{"Q858141":{"pageid":859989,"ns":120,"title":"Item:Q858141","lastrevid":64873344,"modified":"2026-04-11T22:47:54Z","type":"item","id":"Q858141","labels":{"en":{"language":"en","value":"Expansion of product replacement graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5082373"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q858141$4842FCB1-F932-49B6-BC77-CD0BF94A7F87","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2694c217b7b96693d18d44b5b3a10d091f1d76fa","datavalue":{"value":{"text":"Expansion of product replacement graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q858141$41BAFE55-DAE5-4CBF-BD2D-D6D294D6AA40","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cb7e816a39fb957b3749101a9c00226c488c6c65","datavalue":{"value":"1121.05114","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q858141$0267CBF3-F790-4520-9973-2F2AE67573F4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"555ac274dde5860b69fa4ea6ade5f6a944f308a9","datavalue":{"value":{"entity-type":"item","numeric-id":187137,"id":"Q187137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q858141$42A6C865-55FC-4F72-8FD7-193E037FECD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3177ed6d2d9e3636171896fe2dbeeca7aa1d2f7a","datavalue":{"value":{"entity-type":"item","numeric-id":512333,"id":"Q512333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q858141$CCE92111-BF68-4D60-8A22-1DC33789189B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q858141$34D7EE3A-8D23-4799-B660-AF407E275D39","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"febce9c403bb8368209e045225b9a575071ba47f","datavalue":{"value":{"time":"+2007-01-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q858141$CEC07765-EFFF-4BB4-8EEC-E021CB673551","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"86b4c53f273bc8c54cd531d91848a168afe504d1","datavalue":{"value":"The explicit construction of expander graphs goes back to the work of \\textit{G. A. Margulis} [Probl. Peredachi Inf. 9, No. 4, 71--80 (1973; Zbl 0312.22011)], and \\textit{A. Lubotzky, R. Phillips} and \\textit{P. Sarnak} [Combinatorica 8, No. 3, 261--277 (1988; Zbl 0661.05035)]. Here we can see a different approach, when expander graphs arise from merely group properties.   The product replacement graph \\(\\Gamma_k(G)\\) is the following. The vertices of \\(\\Gamma_k(G)\\) are the \\(k\\)-tuples of generators \\(\\{g_1,\\dots, g_k\\}\\) of the group \\(G\\). For \\((i, j)\\), \\(1 \\leq i, j \\leq k\\), \\(i \\not = j\\) there is an edge corresponding to the \\(4k(k-1)\\) transformations \\(L_{i, j}^{\\pm}\\) and \\(R_{i, j}^{\\pm}\\) as:  \\[  R_{i, j}^{\\pm} : (g_1, \\dots, g_i, \\dots, g_k) \\mapsto (g_1, \\dots, g_ig_j^{\\pm 1}, \\dots, g_k), \\]   \\[  L_{i, j}^{\\pm} : (g_1, \\dots, g_i, \\dots, g_k) \\mapsto (g_1, \\dots, g_ig_j^{\\pm 1}, \\dots, g_k). \\]    The main theorem of the paper is that the expansion coefficient of the product replacement graph \\(\\Gamma_k(G)\\) can be bounded by the minimal expansion coefficient of a Cayley graph of \\(G\\) with \\(k\\) generators. While to spell out the theorem needs lots of technicalities, it has a nice consequences. One of those: If the sequence of groups \\(\\{\\text{PLS}(2, p),\\;p-\\text{prime}\\}\\) have universal expansion with \\(m=4\\) generators then the sequence of graphs \\(\\{\\Gamma_k(\\text{PLS}(2, p)), p-\\text{prime}\\}\\) form an expander family for any fixed \\(k \\geq 3\\).   The result gives the theoretical basis for the heuristic used for generating a random element in a finite group, see in \\textit{J. D. Lafferty} and \\textit{D. Rockmore} [Exp. Math. 1, No. 2, 115--139 (1992; Zbl 0773.65091)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q858141$3738A025-779B-449E-9B15-66EDC7D38D99","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"73456c3353ea197c90c73d5f0daaf3b9d502d311","datavalue":{"value":{"entity-type":"item","numeric-id":235726,"id":"Q235726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q858141$CA26D686-9741-4E75-BC38-3AFF5383269B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"74e7832a915a62c417a3bf8c026eff5989fd94d3","datavalue":{"value":"05C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q858141$A1596B70-92FD-482B-A0CF-14B1C0F284CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"239a4a174af03c82b61364f762873d53ef0a37ef","datavalue":{"value":"05C90","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q858141$BFB46883-B055-4DF8-BAB3-D320E79715B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q858141$9C0CF48C-6308-42C6-BC72-6EEBC7A6C581","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"7560d7c00da9c803324a799b9e549a4182d5fe47","datavalue":{"value":"20F99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q858141$BE2411B2-3270-4EFC-B21F-4A4227BFBA6E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4b9ab5e2920d44a2e3e5405112f7152f75583112","datavalue":{"value":"5082373","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q858141$42464B8F-BD84-4117-9E77-E13AD8E078F4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"89b097773537f6be57565fe94a10dc3fe9a9882f","datavalue":{"value":"expanders","type":"string"},"datatype":"string"},"type":"statement","id":"Q858141$62C33583-9E98-4D58-93B7-6029CF0F7253","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"64e1ee688b6f898d32c9c2776a1d825855a56d60","datavalue":{"value":"Cayley graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q858141$EB405C93-F71B-4D5A-9CD3-D69A85B4DB89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf122bdf6ffb39cb767522a29bed44cd4c46ccd8","datavalue":{"value":"product replacement graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q858141$65AFAABB-CD87-45F9-9107-03A2C7740EC8","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q858141$97B049DC-56A0-43A7-9670-9202758DAB60","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"612d13bfdc0a23246515178a01d311f8a1ef5cdb","datavalue":{"value":"https://doi.org/10.1007/s00493-006-0023-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q858141$3ABF3D22-76E9-4DE0-B0CC-9FC4B461E4CD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"07be3a03c673292ea21edff64a7c7229cd6dc1db","datavalue":{"value":"W3138552645","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q858141$956F74B9-1A9E-4228-AA1D-65725F8879CB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6460d62f4e43935579bce90585b83183d1987c01","datavalue":{"value":"10.1007/S00493-006-0023-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q858141$BAF4DC5A-6979-48ED-AD1C-09C0ECC8F3B0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ba3978b0dc72b26d9da0523678207bad36dc5b6","datavalue":{"value":{"entity-type":"item","numeric-id":5166968,"id":"Q5166968"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"09f688e89d6eeb8ace7cb8753d6c159c90e0a53b","datavalue":{"value":{"amount":"+0.8164009","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q858141$163CEA4D-3E90-4253-B3B9-37852E6FEDD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"533ac5ec3be8ccf9e0fa57a98a6cd06be5c19f2b","datavalue":{"value":{"entity-type":"item","numeric-id":607667,"id":"Q607667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b59226bc6e5921588670233c6ef8420f0da3272","datavalue":{"value":{"amount":"+0.8100787","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q858141$BB14C847-5159-4294-83EE-004D9AA17CF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c681d2289488b896d3cabd8b4d95df3005781b87","datavalue":{"value":{"entity-type":"item","numeric-id":4629557,"id":"Q4629557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3f629244a89693a2f3fbd089717bcb445653f2cf","datavalue":{"value":{"amount":"+0.80164254","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q858141$94467DE1-9514-4D57-B67C-C69C585E12F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4b21c8d5d244a46947ddbc78e251644b1a05cf33","datavalue":{"value":{"entity-type":"item","numeric-id":4273626,"id":"Q4273626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2497c3239c0cb70472998eb6101100ee0f301524","datavalue":{"value":{"amount":"+0.79366606","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q858141$1C1742DA-E564-49D0-993D-D8271B7BEA62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"645e819c152dddcfc3bf3589c16e9add9c77c859","datavalue":{"value":{"entity-type":"item","numeric-id":3102220,"id":"Q3102220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"741f233b28857c39c29acb14e298a858d39ec166","datavalue":{"value":{"amount":"+0.78435916","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q858141$03655CB6-6A01-4D69-AE5B-2F99E52A630E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"80e8067e03cff29010192885807f633e22c95c03","datavalue":{"value":{"entity-type":"item","numeric-id":5248797,"id":"Q5248797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5f1dbf399072d56c32f5f09cf3d49a84a36bfc98","datavalue":{"value":{"amount":"+0.7810968","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q858141$3F9C27C1-8E36-4377-AD92-0A988F8398A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"529c66c02bea5c9e1d014609d6a06f84549973b8","datavalue":{"value":{"entity-type":"item","numeric-id":5220077,"id":"Q5220077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"56edf03f37e37e1e62929dc9b115fea0dcbf01d0","datavalue":{"value":{"amount":"+0.7623277","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q858141$2D48DD2E-92A0-4F30-9675-6811BC58F04B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6448a1cfe8609ba23d452b3edd1f7683eafbbafe","datavalue":{"value":{"entity-type":"item","numeric-id":700158,"id":"Q700158"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a6f39c5004fd605ecb5bc9cbce04f76a63dd6632","datavalue":{"value":{"amount":"+0.761796","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q858141$82ACEB40-BAF7-4E5B-AF70-C8700CB9064E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"749a9c4a2207ed009cfcb2610e9924596a6a1859","datavalue":{"value":{"entity-type":"item","numeric-id":1276303,"id":"Q1276303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ecb9d7ecf71f447feaf4eb893a6140ff99d14303","datavalue":{"value":{"amount":"+0.74846846","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q858141$138AF1F5-C426-4589-AB2F-385C03134D1D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Expansion of product replacement graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Expansion_of_product_replacement_graphs"}}}}}