Log in

Relevant bibliographies by topics / Expander graphs / Journal articles

To see the other types of publications on this topic, follow the link: Expander graphs.

Journal articles on the topic 'Expander graphs'

Author: Grafiati

Published: 4 June 2021

Last updated: 6 September 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Expander graphs.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

CZUMAJ, ARTUR, and CHRISTIAN SOHLER. "Testing Expansion in Bounded-Degree Graphs." Combinatorics, Probability and Computing 19, no. 5-6 (June 9, 2010): 693–709. http://dx.doi.org/10.1017/s096354831000012x.

Full text

Abstract:

We consider the problem of testing expansion in bounded-degree graphs. We focus on the notion of vertex expansion: an α-expander is a graph G = (V, E) in which every subset U ⊆ V of at most |V|/2 vertices has a neighbourhood of size at least α ⋅ |U|. Our main result is that one can distinguish good expanders from graphs that are far from being weak expanders in time $\widetilde{\O}(\sqrt{n})$. We prove that the property-testing algorithm proposed by Goldreich and Ron with appropriately set parameters accepts every α-expander with probability at least $\frac23$ and rejects every graph that is ϵ-far from any α*-expander with probability at least $\frac23$, where $\expand^* \,{=}\, \Theta(\frac{\expand^2}{d^2 \log(n/\epsilon)})$ and d is the maximum degree of the graphs. The algorithm assumes the bounded-degree graphs model with adjacency list graph representation and its running time is $\O(\frac{d^2 \sqrt{n} \log(n/\epsilon)} {\expand^2 \epsilon^3})$.

APA, Harvard, Vancouver, ISO, and other styles

2

Kamber, Amitay. "Lp-Expander Graphs." Israel Journal of Mathematics 234, no. 2 (October 2019): 863–905. http://dx.doi.org/10.1007/s11856-019-1938-7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Polak, Monika, and Vasyl Ustimenko. "Algorithms for generation of Ramanujan graphs, other Expanders and related LDPC codes." Annales Universitatis Mariae Curie-Sklodowska, sectio AI – Informatica 15, no. 2 (October 11, 2015): 14. http://dx.doi.org/10.17951/ai.2015.15.2.14-21.

Full text

Abstract:

Expander graphs are highly connected sparse finite graphs. The property of being an expander seems significant in many of these mathematical, computational and physical contexts. For practical applications it is very important to construct expander and Ramanujan graphs with given regularity and order. In general, constructions of the best expander graphs with a given regularity and order is no easy task. In this paper we present algorithms for generation of Ramanujan graphs and other expanders. We describe properties of obtained graphs in comparison to previously known results. We present a method to obtain a new examples of irregular LDPC codes based on described graphs and we briefly describe properties of this codes.

APA, Harvard, Vancouver, ISO, and other styles

4

Cheung, Ho Yee, Lap Chi Lau, and Kai Man Leung. "Graph Connectivities, Network Coding, and Expander Graphs." SIAM Journal on Computing 42, no. 3 (January 2013): 733–51. http://dx.doi.org/10.1137/110844970.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Angel, D., R. Mary Jeya Jothi, R. Revathi, and A. Raja. "Expander Graphs – A Study." Journal of Physics: Conference Series 1770, no. 1 (March 1, 2021): 012078. http://dx.doi.org/10.1088/1742-6596/1770/1/012078.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Dutta, Neelav, and David Jensen. "Gonality of expander graphs." Discrete Mathematics 341, no. 9 (September 2018): 2535–43. http://dx.doi.org/10.1016/j.disc.2018.06.012.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Harrow, A. W. "Quantum expanders from any classical Cayley graph expander." Quantum Information and Computation 8, no. 8&9 (September 2008): 715–21. http://dx.doi.org/10.26421/qic8.8-9-2.

Full text

Abstract:

We give a simple recipe for translating walks on Cayley graphs of a group G into a quantum operation on any irrep of G. Most properties of the classical walk carry over to the quantum operation: degree becomes the number of Kraus operators, the spectral gap becomes the gap of the quantum operation (viewed as a linear map on density matrices), and the quantum operation is efficient whenever the classical walk and the quantum Fourier transform on G are efficient. This means that using classical constant-degree constant-gap families of Cayley expander graphs on e.g. the symmetric group, we can construct efficient families of quantum expanders.

APA, Harvard, Vancouver, ISO, and other styles

8

LEUNG, KA HIN, VINH NGUYEN, and WASIN SO. "NONEXISTENCE OF A CIRCULANT EXPANDER FAMILY." Bulletin of the Australian Mathematical Society 83, no. 1 (November 17, 2010): 87–95. http://dx.doi.org/10.1017/s0004972710001644.

Full text

Abstract:

AbstractThe expansion constant of a simple graph G of order n is defined as where $E(S, \overline {S})$ denotes the set of edges in G between the vertex subset S and its complement $\overline {S}$. An expander family is a sequence {Gi} of d-regular graphs of increasing order such that h(Gi)>ϵ for some fixed ϵ>0. Existence of such families is known in the literature, but explicit construction is nontrivial. A folklore theorem states that there is no expander family of circulant graphs only. In this note, we provide an elementary proof of this fact by first estimating the second largest eigenvalue of a circulant graph, and then employing Cheeger’s inequalities where G is a d-regular graph and λ2(G) denotes the second largest eigenvalue of G. Moreover, the associated equality cases are discussed.

APA, Harvard, Vancouver, ISO, and other styles

9

JOUVE, FLORENT, and JEAN-SÉBASTIEN SERENI. "EXPANDER GRAPHS AND SIEVING IN COMBINATORIAL STRUCTURES." Journal of the Australian Mathematical Society 105, no. 1 (January 11, 2018): 79–102. http://dx.doi.org/10.1017/s1446788717000234.

Full text

Abstract:

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, for instance, that with high probability (in a strong explicit sense) random coloured subsets of integers contain monochromatic (nonempty) subsets summing to $0$, and that a random colouring of the edges of a complete graph contains a monochromatic triangle.

APA, Harvard, Vancouver, ISO, and other styles

10

Hoory, Shlomo, Nathan Linial, and Avi Wigderson. "Expander graphs and their applications." Bulletin of the American Mathematical Society 43, no. 04 (August 7, 2006): 439–562. http://dx.doi.org/10.1090/s0273-0979-06-01126-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

11

Kassabov, Martin. "Symmetric groups and expander graphs." Inventiones mathematicae 170, no. 2 (August 23, 2007): 327–54. http://dx.doi.org/10.1007/s00222-007-0065-y.

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

Ben-Shimon, Sonny, and Michael Krivelevich. "Vertex percolation on expander graphs." European Journal of Combinatorics 30, no. 2 (February 2009): 339–50. http://dx.doi.org/10.1016/j.ejc.2008.07.001.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Frieze, Alan M. "Edge-Disjoint Paths in Expander Graphs." SIAM Journal on Computing 30, no. 6 (January 2001): 1790–801. http://dx.doi.org/10.1137/s0097539700366103.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Firooz, Mohammad Hamed, and Sumit Roy. "Link Delay Estimation via Expander Graphs." IEEE Transactions on Communications 62, no. 1 (January 2014): 170–81. http://dx.doi.org/10.1109/tcomm.2013.112413.120750.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

Chapman, Michael, Nati Linial, and Yuval Peled. "Expander Graphs — Both Local and Global." Combinatorica 40, no. 4 (July 6, 2020): 473–509. http://dx.doi.org/10.1007/s00493-019-4127-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

Hoory, Shlomo, and Avi Wigderson. "Universal traversal sequences for expander graphs." Information Processing Letters 46, no. 2 (May 1993): 67–69. http://dx.doi.org/10.1016/0020-0190(93)90199-j.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

Blok, Rieuwert J., Corneliu G. Hoffman, and Alina Vdovina. "Expander graphs from Curtis–Tits groups." Journal of Combinatorial Theory, Series A 119, no. 3 (April 2012): 521–25. http://dx.doi.org/10.1016/j.jcta.2011.10.007.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

Charles, Denis X., Kristin E. Lauter, and Eyal Z. Goren. "Cryptographic Hash Functions from Expander Graphs." Journal of Cryptology 22, no. 1 (September 15, 2007): 93–113. http://dx.doi.org/10.1007/s00145-007-9002-x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

Peleg, D., and E. Upfal. "Constructing disjoint paths on expander graphs." Combinatorica 9, no. 3 (September 1989): 289–313. http://dx.doi.org/10.1007/bf02125897.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

DOTTERRER, DOMINIC, and MATTHEW KAHLE. "COBOUNDARY EXPANDERS." Journal of Topology and Analysis 04, no. 04 (December 2012): 499–514. http://dx.doi.org/10.1142/s1793525312500197.

Full text

Abstract:

We describe a higher-dimensional generalization of edge expansion from graphs to simplicial complexes, which we discuss as a type of co-isoperimetric inequality. The main point is to observe that sufficiently dense random simplicial complexes have this expander-like property with high probability, a higher-dimensional analogue of the fact that random graphs are expanders.

APA, Harvard, Vancouver, ISO, and other styles

21

Badaoui, Mohamad, Alain Bretto, David Ellison, and Bassam Mourad. "On constructing expander families of G-graphs." Ars Mathematica Contemporanea 15, no. 2 (August 14, 2018): 425–40. http://dx.doi.org/10.26493/1855-3974.1537.97c.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

Gabow, Harold N. "Using expander graphs to find vertex connectivity." Journal of the ACM 53, no. 5 (September 2006): 800–844. http://dx.doi.org/10.1145/1183907.1183912.

Full text

APA, Harvard, Vancouver, ISO, and other styles

23

Lubotzky, Alexander. "Expander graphs in pure and applied mathematics." Bulletin of the American Mathematical Society 49, no. 1 (January 1, 2012): 113–62. http://dx.doi.org/10.1090/s0273-0979-2011-01359-3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Frieze, Alan. "Corrigendum: Edge-Disjoint Paths in Expander Graphs." SIAM Journal on Computing 31, no. 3 (January 2001): 988. http://dx.doi.org/10.1137/s0097539701395097.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

Somlai, Gábor. "Non-expander Cayley Graphs of Simple Groups." Communications in Algebra 43, no. 3 (January 7, 2015): 1156–75. http://dx.doi.org/10.1080/00927872.2013.865041.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Glebov, Roman, Michael Krivelevich, and Tibor Szabó. "On covering expander graphs by hamilton cycles." Random Structures & Algorithms 44, no. 2 (August 10, 2012): 183–200. http://dx.doi.org/10.1002/rsa.20455.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

Hemenway, Brett, and Rafail Ostrovsky. "Efficient robust secret sharing from expander graphs." Cryptography and Communications 10, no. 1 (March 7, 2017): 79–99. http://dx.doi.org/10.1007/s12095-017-0215-z.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

Galanis, Andreas, Leslie Ann Goldberg, and James Stewart. "Fast Algorithms for General Spin Systems on Bipartite Expanders." ACM Transactions on Computation Theory 13, no. 4 (December 31, 2021): 1–18. http://dx.doi.org/10.1145/3470865.

Full text

Abstract:

A spin system is a framework in which the vertices of a graph are assigned spins from a finite set. The interactions between neighbouring spins give rise to weights, so a spin assignment can also be viewed as a weighted graph homomorphism. The problem of approximating the partition function (the aggregate weight of spin assignments) or of sampling from the resulting probability distribution is typically intractable for general graphs. In this work, we consider arbitrary spin systems on bipartite expander Δ-regular graphs, including the canonical class of bipartite random Δ-regular graphs. We develop fast approximate sampling and counting algorithms for general spin systems whenever the degree and the spectral gap of the graph are sufficiently large. Roughly, this guarantees that the spin system is in the so-called low-temperature regime. Our approach generalises the techniques of Jenssen et al. and Chen et al. by showing that typical configurations on bipartite expanders correspond to “bicliques” of the spin system; then, using suitable polymer models, we show how to sample such configurations and approximate the partition function in Õ( n 2 ) time, where n is the size of the graph.

APA, Harvard, Vancouver, ISO, and other styles

29

Špakula, Ján. "Non-K-exact uniform Roe C*-algebras." Journal of K-Theory 10, no. 1 (August 3, 2010): 191–201. http://dx.doi.org/10.1017/is010006007jkt122.

Full text

Abstract:

AbstractWe prove that uniform Roe C*-algebras C*uX associated to some expander graphs X coming from discrete groups with property (τ) are not K-exact. In particular, we show that this is the case for the expander obtained as Cayley graphs of a sequence of alternating groups (with appropriately chosen generating sets).

APA, Harvard, Vancouver, ISO, and other styles

30

Høholdt, Tom, and Jørn Justesen. "On the sizes of expander graphs and minimum distances of graph codes." Discrete Mathematics 325 (June 2014): 38–46. http://dx.doi.org/10.1016/j.disc.2014.02.005.

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

Pankaj, Rajesh K. "All-Optical Network Topologies Based on Expander Graphs." Journal of High Speed Networks 4, no. 2 (1995): 117–31. http://dx.doi.org/10.3233/jhs-1995-4202.

Full text

APA, Harvard, Vancouver, ISO, and other styles

32

Jenssen, Matthew, Peter Keevash, and Will Perkins. "Algorithms for #BIS-Hard Problems on Expander Graphs." SIAM Journal on Computing 49, no. 4 (January 2020): 681–710. http://dx.doi.org/10.1137/19m1286669.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

Ellenberg, Jordan S., Chris Hall, and Emmanuel Kowalski. "Expander graphs, gonality, and variation of Galois representations." Duke Mathematical Journal 161, no. 7 (May 2012): 1233–75. http://dx.doi.org/10.1215/00127094-1593272.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Bolla, Marianna. "Beyond the Expanders." International Journal of Combinatorics 2011 (June 28, 2011): 1–11. http://dx.doi.org/10.1155/2011/787596.

Full text

Abstract:

Expander graphs are widely used in communication problems and construction of error correcting codes. In such graphs, information gets through very quickly. Typically, it is not true for social or biological networks, though we may find a partition of the vertices such that the induced subgraphs on them and the bipartite subgraphs between any pair of them exhibit regular behavior of information flow within or between the vertex subsets. Implications between spectral and regularity properties are discussed.

APA, Harvard, Vancouver, ISO, and other styles

35

Raviv, Netanel, Itzhak Tamo, Rashish Tandon, and Alexandros G. Dimakis. "Gradient Coding From Cyclic MDS Codes and Expander Graphs." IEEE Transactions on Information Theory 66, no. 12 (December 2020): 7475–89. http://dx.doi.org/10.1109/tit.2020.3029396.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

Jafarpour, Sina, Weiyu Xu, Babak Hassibi, and Robert Calderbank. "Efficient and Robust Compressed Sensing Using Optimized Expander Graphs." IEEE Transactions on Information Theory 55, no. 9 (September 2009): 4299–308. http://dx.doi.org/10.1109/tit.2009.2025528.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Gillman, David. "A Chernoff Bound for Random Walks on Expander Graphs." SIAM Journal on Computing 27, no. 4 (August 1998): 1203–20. http://dx.doi.org/10.1137/s0097539794268765.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Paturi, Ramamohan, Dau-Tsuong Lu, Joseph E. Ford, Sadik C. Esener, and Sing H. Lee. "Parallel algorithms based on expander graphs for optical computing." Applied Optics 30, no. 8 (March 10, 1991): 917. http://dx.doi.org/10.1364/ao.30.000917.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

PELED, RON, WOJCIECH SAMOTIJ, and AMIR YEHUDAYOFF. "Lipschitz Functions on Expanders are Typically Flat." Combinatorics, Probability and Computing 22, no. 4 (June 11, 2013): 566–91. http://dx.doi.org/10.1017/s0963548313000163.

Full text

Abstract:

This work studies the typical behaviour of random integer-valued Lipschitz functions on expander graphs with sufficiently good expansion. We consider two families of functions: M-Lipschitz functions (functions which change by at most M along edges) and integer-homomorphisms (functions which change by exactly 1 along edges). We prove that such functions typically exhibit very small fluctuations. For instance, we show that a uniformly chosen M-Lipschitz function takes only M+1 values on most of the graph, with a double exponential decay for the probability of taking other values.

APA, Harvard, Vancouver, ISO, and other styles

40

Mehrabian, Abbas. "Cops and Robber Game with a Fast Robber on Expander Graphs and Random Graphs." Annals of Combinatorics 16, no. 4 (October 5, 2012): 829–46. http://dx.doi.org/10.1007/s00026-012-0163-4.

Full text

APA, Harvard, Vancouver, ISO, and other styles

41

Kim, Han-Doo, Sung-Jin Cho, and Un-Sook Choi. "Expander graphs based on 60/102 NBCA and its application." Journal of the Korean Institute of Information and Communication Engineering 15, no. 9 (September 30, 2011): 1939–46. http://dx.doi.org/10.6109/jkiice.2011.15.9.1939.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

Broder, Andrei Z., Alan M. Frieze, and Eli Upfal. "Existence and Construction of Edge-Disjoint Paths on Expander Graphs." SIAM Journal on Computing 23, no. 5 (October 1994): 976–89. http://dx.doi.org/10.1137/s0097539792232021.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

Nikoletseas, S., C. Raptopoulos, and P. G. Spirakis. "Expander properties and the cover time of random intersection graphs." Theoretical Computer Science 410, no. 50 (November 2009): 5261–72. http://dx.doi.org/10.1016/j.tcs.2009.08.028.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

Zinnatullin, I. "Cryptographic Properties of the Quantum Hashing Based on Expander Graphs." Lobachevskii Journal of Mathematics 44, no. 2 (February 2023): 776–87. http://dx.doi.org/10.1134/s1995080223020397.

Full text

APA, Harvard, Vancouver, ISO, and other styles

45

PARZANCHEVSKI, ORI. "Mixing in High-Dimensional Expanders." Combinatorics, Probability and Computing 26, no. 5 (May 17, 2017): 746–61. http://dx.doi.org/10.1017/s0963548317000116.

Full text

Abstract:

We establish a generalization of the Expander Mixing Lemma for arbitrary (finite) simplicial complexes. The original lemma states that concentration of the Laplace spectrum of a graph implies combinatorial expansion (which is also referred to asmixing, orpseudo-randomness). Recently, an analogue of this lemma was proved for simplicial complexes of arbitrary dimension, provided that the skeleton of the complex is complete. More precisely, it was shown that a concentrated spectrum of the simplicial Hodge Laplacian implies a similar type of pseudo-randomness as in graphs. In this paper we remove the assumption of a complete skeleton, showing that simultaneous concentration of the Laplace spectra in all dimensions implies pseudo-randomness in any complex. We discuss various applications and present some open questions.

APA, Harvard, Vancouver, ISO, and other styles

46

Türkelli, Seyfi. "A note on a theorem of Cadoret and Tamagawa." International Journal of Number Theory 14, no. 02 (February 8, 2018): 349–53. http://dx.doi.org/10.1142/s1793042118500227.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

Bah, Bubacarr, and Jared Tanner. "Vanishingly Sparse Matrices and Expander Graphs, With Application to Compressed Sensing." IEEE Transactions on Information Theory 59, no. 11 (November 2013): 7491–508. http://dx.doi.org/10.1109/tit.2013.2274267.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

Harcos, Gergely, and Daniel Soltész. "New Bounds on Even Cycle Creating Hamiltonian Paths Using Expander Graphs." Combinatorica 40, no. 3 (March 5, 2020): 435–54. http://dx.doi.org/10.1007/s00493-020-4204-z.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Hyun, Jong Yoon, Jungyun Lee, and Yoonjin Lee. "Ramanujan graphs and expander families constructed from p-ary bent functions." Designs, Codes and Cryptography 88, no. 2 (November 7, 2019): 453–70. http://dx.doi.org/10.1007/s10623-019-00692-z.

Full text

APA, Harvard, Vancouver, ISO, and other styles

50

Lu, Weizhi, Weiyu Li, Wei Zhang, and Shu-Tao Xia. "Expander Recovery Performance of Bipartite Graphs With Girth Greater Than 4." IEEE Transactions on Signal and Information Processing over Networks 5, no. 3 (September 2019): 418–27. http://dx.doi.org/10.1109/tsipn.2018.2889229.

Full text

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!