# Tagged Questions

285 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 ...
663 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 ...
746 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 ...
214 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, ...
353 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 ...
632 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 ...
96 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 ...
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 ...
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 ...
785 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 ...
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 ...
990 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 ...
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 ...
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 ...
752 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. ...
618 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 ...
371 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 ...
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], ...
233 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 ...
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 ...
677 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 ...
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 ...
495 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 ...
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 ...
421 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 ...
776 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 ...