Graphes expanseurs et crible dans les structures combinatoires
| hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
| dc.contributor.author | JOUVE, Florent | |
| hal.structure.identifier | Knowledge representation, reasonning [ORPAILLEUR] | |
| dc.contributor.author | SERENI, Jean-Sébastien | |
| dc.date.accessioned | 2024-04-04T03:11:53Z | |
| dc.date.available | 2024-04-04T03:11:53Z | |
| dc.date.created | 2017-01 | |
| dc.date.issued | 2018 | |
| dc.identifier.issn | 1446-7887 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/193812 | |
| dc.description.abstractEn | We prove a general large sieve statement in the context of random walks on subgraphs of a given graph. This can be seen as a generalization of previously known results where one performs a random walk on a group enjoying a strong spectral gap property. In such a context the point is to exhibit a strong uniform expansion property for a suitable family of Cayley graphs on quotients. In our combinatorial approach, this is replaced by a result of Alon--Roichman about expanding properties of random Cayley graphs. Applying the general setting we show e.g., that with high probability (in a strong explicit sense) random coloured subsets of integers contain monochromatic (non-empty) subsets summing to zero, or that a random coloring of the edges of a complete graph contains a monochromatic triangle. | |
| dc.language.iso | en | |
| dc.publisher | Cambridge University Press | |
| dc.subject.en | Groups | |
| dc.subject.en | Random Walks | |
| dc.subject.en | Graphs | |
| dc.subject.en | Sieve | |
| dc.title | Graphes expanseurs et crible dans les structures combinatoires | |
| dc.title.en | Expander graphs and sieving in combinatorial structures | |
| dc.type | Article de revue | |
| dc.identifier.doi | 10.1017/S1446788717000234 | |
| dc.subject.hal | Mathématiques [math]/Théorie des groupes [math.GR] | |
| dc.subject.hal | Mathématiques [math]/Combinatoire [math.CO] | |
| dc.identifier.arxiv | 1205.0631 | |
| bordeaux.journal | Journal of the Australian Mathematical Society | |
| bordeaux.page | 79--102 | |
| bordeaux.volume | 105 | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.issue | 1 | |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-00693334 | |
| hal.version | 1 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-00693334v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.title=Graphes%20expanseurs%20et%20crible%20dans%20les%20structures%20combinatoires&rft.atitle=Graphes%20expanseurs%20et%20crible%20dans%20les%20structures%20combinatoires&rft.jtitle=Journal%20of%20the%20Australian%20Mathematical%20Society&rft.date=2018&rft.volume=105&rft.issue=1&rft.spage=79--102&rft.epage=79--102&rft.eissn=1446-7887&rft.issn=1446-7887&rft.au=JOUVE,%20Florent&SERENI,%20Jean-S%C3%A9bastien&rft.genre=article |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||