# Tagged Questions

**5**

votes

**1**answer

300 views

### Are there number-theoretic graphs that are far from being isomorphic

I say that two graphs $G_1=(V_1,E_1)$, $G_2 = (V_2,E_2)$
with the same number of vertices, edges,
are $\epsilon$-far from being isomorphic, if for any bijection between $V_1$ and $V_2$, the fraction ...

**19**

votes

**0**answers

670 views

### Non-linear expanders?

Recall that a family of graphs (indexed by an infinite set, such as the primes, say) is called an expander family if there is a $\delta>0$ such that, on every graph in the family, the discrete ...

**9**

votes

**3**answers

757 views

### Could a perfect squared square be split into two perfect squared squares?

This is a geometric puzzle though it might conceivably
also define a special class of Pythagorean triples.
A perfect squared square PSS is a square (as a plane figure)
partitioned into smaller ...

**8**

votes

**0**answers

218 views

### Connections between Riemann hypothesis for curves over finite fields and Ramanujan property for graphs

this question relates to the beautiful construction of expander graphs using Cayley graphs of $PGL_2(\mathbb{F}_q)$, as exposited by Davidoff-Sarnak-Valette in their book, Elementary Number Theory, ...

**3**

votes

**3**answers

355 views

### random networks and prime numbers

I have been studying networks recently and accidentally came up with an heuristic approach towards the distribution of prime numbers. The prime number theorem states that
$\pi(n)\sim n/log(n)$ for ...

**16**

votes

**1**answer

645 views

### A Question on 1, 2 ,3 Conjecture

1, 2, 3 conjecture is well-known:
If $G$ is a simple graph which is not $K_2$ then one can assign a number among $1, 2, 3$ to every edge such that if we label each vertex with the sum of the numbers ...

**3**

votes

**0**answers

97 views

### What are the best bounds to date on the maximum girth of a cubic graph?

The girth of a graph is the length of its smallest cycle. Studying the maximum possible girth for a $k$-regular graph on $n$ vertices is a very well-studied problem.
In the 1988 paper "Ramanujan ...

**1**

vote

**1**answer

135 views

### What algorithms do you know for beltway reconstruction?

I've faced the beltway reconstruction problem and I've developed a simple backtrack algorithm, what algorithms do you know for this problem?
Beltway Reconstruction Problem:
Assume there is a set of ...

**30**

votes

**5**answers

2k views

### Does every bipartite graph with 512 edges have an induced subgraph with 256 edges?

Suppose we have a (simple) bipartite graph with $2^k$ edges. Is it true that there is a subset of the vertices such that their induced subgraph has exactly $2^{k-1}$ edges?
I know that the answer is ...

**7**

votes

**3**answers

800 views

### Showing non-expansion for $x\rightarrow x+1, x\rightarrow 2x.$

Construct a graph having $V=\mathbb{Z}/p\mathbb{Z}$ as its set of vertices and $\{\{x,x+1\}: x \in V\}\cup \{\{x,2x\}: x \in V\}$ as its set of edges. This graph is not an expander - quite ...

**11**

votes

**1**answer

244 views

### Automorphisms of a certain digraph defined on the set of primes? [Edited]

Define a digraph $P=(V,E)$ with $V$ equal to the set of prime numbers and an arrow from $p$ to $q$ if $p|q-1$ (definition motivated by Pratt's primality certificates).
Does $P$ indeed admit only the ...

**8**

votes

**2**answers

1k views

### Knight tour prime (conjecture)

Hello,
I have the following conjecture:
Write all numbers from $1$ to $n^2$ over an $n\times n$ board as usually. There not exists $n$ such that we can find a hamiltonian path on primes numbers with ...

**17**

votes

**3**answers

1k views

### Traversing the infinite square grid

Starting somewhere on an infinite square grid, is it possible to visit every square exactly once, if at move $n$, one must jump $a_n$ steps in one of the directions north,south,east or west, and mark ...

**14**

votes

**1**answer

637 views

### The graph of congruences between modular forms

Let $S$ be the (countable) set of holomorphic cuspidal new eigenforms of weight $\geq 2$. Any $f\in S$ has a level $N_f$ and a canonically normalized Fourier expansion ...

**-1**

votes

**1**answer

758 views

### Implication for m-cycles in Collatz-type problems.

Background
Consider Collatz-type problems of the form $an + 1$, where $a > 2$ is a positive, odd integer (e.g., $3n + 1$, $5n +1 $, $7n + 1$, etc.). For convenience, automatically divide by two.
...

**13**

votes

**1**answer

629 views

### Ideal classes and integral similarity

Matrices $A$ and $B$ are integrally equivalent if there is an invertible integer matrix $L$ and $L^{-1}AL=B$. Suppose $f(t)$ is an integer polynomial with no repeated factors. Latimer and MacDuffee ...

**3**

votes

**2**answers

373 views

### Drawing (graphs) by numbers: a minimality question

Every simple graph $G$ can be represented ("drawn") by numbers in the following way:
Assign to each vertex $v_i$ a number $n_i$ such that all $n_i$, $n_j$ are coprime whenever $i\neq j$. Let $V$ be ...

**26**

votes

**3**answers

3k views

### Bringing Number and Graph Theory Together: A Conjecture on Prime Numbers

Some MOers have been skeptic whether something like natural number graphs can be defined coherently such that every finite graph is isomorphic to such a graph. (See my previous questions [1], [2], ...

**2**

votes

**1**answer

234 views

### Uniformly computable classes of graphs

[Follow-up to Can every finite graph be represented by one prescribed sequence of natural numbers?, reformulated thanks to a hint from Jacques Carette]
Let $V(n,\nu)$ and $E(n,m,\mu)$ be ...

**0**

votes

**1**answer

629 views

### Can every finite graph be represented by one prescribed sequence of natural numbers?

(This is a follow-up to my previous question Can every finite graph be represented by an arithmetic sequence of natural numbers?)
Since it is obviously false that every finite graph can be ...

**3**

votes

**1**answer

680 views

### Can every finite graph be represented by an arithmetic sequence of natural numbers?

(This is a follow-up to my previous questions Natural models of graphs?.)
ErdÃ¶s in The Representation of a Graph by Set Intersections (1966) states:
Theorem. Let $G$ be an arbitrary
graph. Then ...

**7**

votes

**2**answers

2k views

### Lagrange four-squares theorem: efficient algorithm with units modulo a prime?

I'm looking at algorithms to construct short paths in a particular Cayley graph defined in terms of quadratic residues. This has led me to consider a variant on Lagrange's four-squares theorem.
The ...

**12**

votes

**4**answers

496 views

### Hamiltonian paths where the vertices are integer partitions

Hello,
I have been working on this problem for several months now but have not made much progress. It concerns the set of all integer partitions of n.
Let the vertices of the graph G=G(n) denote ...

**6**

votes

**1**answer

663 views

### An ubiquitous pattern of questions

There is an ubiquitous pattern of questions concerning assumedly any kind of mathematical object or structure: groups, graphs, numbers, categories, and so on. It goes like this (informally):
Can a ...

**5**

votes

**0**answers

422 views

### Natural models of graphs?

Motivation
I want to capture the notion of natural models of finite graphs: How can natural predicates and natural relations on a given natural base class $D$ be defined? If this succeeds the ...

**4**

votes

**4**answers

785 views

### Prime numbers p not of the form ab + bc + ac (0 < a < b < c ) (and related questions)

If we ask which natural numbers n are not expressible as n = ab + bc + cd (0 < a < b < c) then this is a well known open problem. Numbers not expressible in such form are called Euler's ...

**16**

votes

**3**answers

2k views

### Number theoretic spectral properties of random graphs

If G is a graph then its adjacency matrix has a distinguished Peron-Frobenius eigenvalue x. Consider the field Q(x). I'd like a result that says that if G is a "random graph" then the Galois group ...

**7**

votes

**2**answers

624 views

### How can I prove that a sequence of squares of graph norms is never cyclotomic?

The norm of a graph is the largest eigenvalue of the adjacency matrix. I'll write ||G|| for the norm of G.
Now, fix some graph ...