9
votes
3answers
697 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
0answers
183 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
3answers
337 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
1answer
570 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 ...
2
votes
0answers
90 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
1answer
126 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 ...
26
votes
5answers
1k 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
3answers
753 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
1answer
242 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
2answers
933 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
3answers
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
1answer
619 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
1answer
725 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. ...
12
votes
1answer
577 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
2answers
363 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 ...
23
votes
3answers
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
1answer
226 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
1answer
621 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
1answer
650 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
2answers
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
4answers
488 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
1answer
655 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
0answers
411 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
4answers
746 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
3answers
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
2answers
617 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 ...