Repository: networkx/networkx

Issue:
wrong bound in is_regular_expander
The bound in `is_regular_expander` on [this line](https://github.com/networkx/networkx/blob/ba6744c1dc432c7beea0210584f16b80761c5fda/networkx/generators/expanders.py#L399) should be `2*np.sqrt(d-1)` not `2**np.sqrt(d-1)`  (`**` is raising 2 to power `np.sqrt(d-1)`). The Ramanujan bound is $2\sqrt{d-1}$ not $2^{\sqrt{d-1}}$ (see https://en.wikipedia.org/wiki/Expander_graph

Discussion:
vttrifonov: added a test for generating larger expanders (2000 notes) which was failing for me with d=4
vttrifonov: just noticed that the new version of networkx requires python 3.11. i am only mentioning this because i am still using python 3.10 in my projects so this created a bit of an issue when i was trying to add the fix to main so instead I add it to the nx3.4.2 commit...

not a heavy user of networkx (yet :-)) so do not have much of a skin in this game but raising the python version could create a bar for usage. just saying. maybe you guys have a good reason... could file an issue that mentions this if you think it is worth it
rossbar: > not a heavy user of networkx (yet :-)) so do not have much of a skin in this game but raising the python version could create a bar for usage. just saying. maybe you guys have a good reason... could file an issue that mentions this if you think it is worth it


The policy for which Python versions to support is governed by [SPEC 0](https://scientific-python.org/specs/spec-0000/) which is formulated via discussion across scientific Python projects. Check out the link if you're interested!

Patch:
diff --git a/networkx/generators/expanders.py b/networkx/generators/expanders.py
index fbf003246..33b2887d9 100644
--- a/networkx/generators/expanders.py
+++ b/networkx/generators/expanders.py
@@ -396,7 +396,7 @@ def is_regular_expander(G, *, epsilon=0):
     lambda2 = min(lams)
 
     # Use bool() to convert numpy scalar to Python Boolean
-    return bool(abs(lambda2) < 2 ** np.sqrt(d - 1) + epsilon)
+    return bool(abs(lambda2) < 2 * np.sqrt(d - 1) + epsilon)
 
 
 @nx.utils.decorators.np_random_state("seed")


Test patch:
diff --git a/networkx/generators/tests/test_expanders.py b/networkx/generators/tests/test_expanders.py
index 7cebc5881..cc0ca943f 100644
--- a/networkx/generators/tests/test_expanders.py
+++ b/networkx/generators/tests/test_expanders.py
@@ -80,7 +80,7 @@ def test_is_regular_expander(n):
     assert nx.is_regular_expander(G) == True, "Should be a regular expander"
 
 
-@pytest.mark.parametrize("d, n", [(2, 7), (4, 10), (4, 16)])
+@pytest.mark.parametrize("d, n", [(2, 7), (4, 10), (4, 16), (4, 2000)])
 def test_random_regular_expander(d, n):
     pytest.importorskip("numpy")
     pytest.importorskip("scipy")