analytics

Friday, March 29, 2013

T list of a graph


So to create this list T, you first label all nodes of a graph as 1 in the first step. Then in the second step each vertex becomes the sum of it's label in step 1 summed with the label of each node it's connected to in the first graph. Then this process iterates until the number of steps equals the diameter of the graph, which is the max number of edges one has to cross between any two points on the graph. For example the point labeled 43 in the bottom right graph was labeled so because it had a label of 12 in the bottom left graph and it was connected to 16 and 15. 43 = 12+15+16. 
Then the list T is just the value of the vertices listed in increasing order: T={23,36,38,39,40,43,47,55,59,67}

So I believe that isomorphic graphs yield the same list, but I'm conjecturing that the only graphs that produce the same list are isometries. 

But even if this doesn't end up true there is an interesting use for this T list: I can say whatever graph you have and whatever labeling to pick one of the vertices with the lowest value in the T list. Because I believe that if two vertices have the same value in the T list if the graph looks the same from either of those two points... Then this gives a way to distinguish one point on any graph. Or at least one of the points that the rest of the graph looks the same from. So no matter how they have a graph labeled or drawn this gives a way to specify a vertex. 

***
The last thing I said doesn't necessarily apply if you have for instance a graph with two disconnected subgraphs, then you might have two vertices that end up with the same number but the graph doesn't look the same from their two perspectives...

Thursday, March 21, 2013

estimating Gauss's circle problem series

Just something I noticed that:

The average of the exterior square's number of grid points and the diagonally set interior square's dots and gridpoints come out close to the number of grid points withing the circle.

For a circle of radius 46 this calculation above is within ~3%, not sure if it stays close indefinitely...

Wednesday, March 20, 2013

A solution to Gauss's circle problem

This I'll put forward as the solution to Gauss's circle problem, a previously unsolved problem. See:
http://en.wikipedia.org/wiki/Gauss%27s_circle_problem

This formula tells how many integer points are inside or on a boundary of a circle of radius r.
for instance at r = 10 it outputs 317 which is the right answer. 

Basically it adds infinitely tall infinitely narrow functions at all the integer points from 0 to the radius in the y direction. Then integrates from 0 to the height of the circle at x for each x from 1 to the radius. This gives all the integer points within the first quadrant of the circle not counting those on x=0 or y=0 lines. Then that is multiplied by four for the four quadrants and add those on the x=0 or y=0 lines and then 1 for the center point. 

Now, the Dirac function is a logistic function but it can be considered as the limit of:
as s goes to 0. But smaller and smaller values of s can be used to make the answer my formula gives more exact. This is just if it is required of the solution to be purely algebraic.  
The function just above is just a normal curve with mean of j, so it's integral is 1, and you make the deviation smaller and smaller which doesn't change the integral but makes it taller and taller. In the limit it is just infinitely tall at only the point j. 



Finding the number of integer points on a curve

I found this function that works very well for indicating whether a number is an integer or not:

It evaluates to 1 if a number is an integer and something close to 0 if a number is not.
For instance:
f(.999999)~=0.00002+.00001I
f(1)=1
f(1.000001)~=0.000004

So you can see the transition from near 0 to 1 is very close to the integer in question. 

I think this function could be useful in a lot of situations but here is just one example. Suppose you want to know how many integer points there are on a circle on a grid like so:

you simply:

This is just plugging the equation for the circle into the function I described, and it outputs:
12 + 3*10^-30

So very close to 12. 

Indeed there are 12 integer points that lie exactly on the circle:




Monday, March 11, 2013

Extruding a polynomial


I happened to wonder whether you could take any polynomial like for example:

and write it like this, as linear factors multiplied and summed:

As it turns out with this polynomial it was possible, I just set the two equal at 20 different points and solved for the 20 variables...

And the coefficients are:

I found it interesting that all of these coefficients are real numbers, I'm not sure if it's ever necessary to use imaginary numbers or not. I called it extruding the polynomial because it reminds me of the way steel can be shaped by squeezing it through an aperture, in this case a linear factor aperture :). 

You might wonder why I didn't try to make z:
Maple wasn't able to solve this one even with so many less variables...



Saturday, March 9, 2013

Map from planar graph

I'll describe the steps I took below this picture...


Step 1: start with a planar graph
Step 2: Plot the midpoints of every line connecting points of the graph
Step 3: Connect midpoints that are connected to the same vertex of the original graph, also draw new lines around vertices on the outside of the graph. to those midpoints. This will leave some regions without a vertex from the original graph inside, color those black....
Step 4. Draw lines from the vertices of the black regions to their centroid. 
Step 5. These new lines in addition to those you had drawn around the outside of the graph complete the map. 

Tuesday, March 5, 2013

Solving a 2d heat map progression over time

Starting with the idea that the fundamental solution to the heat equation with one variable is:
\Phi(x,t)=\frac{1}{\sqrt{4\pi kt}}\exp\left(-\frac{x^2}{4kt}\right).
I've derived this equation for a kernel about the point (a,b) on the plane where M is the peak magnitude, k is a constant that depends on the material, and t is of course time.

As a check consider this kernel based around the point (0,0) with k=1 and t=1 and an initial peak of 4, one would expect the integral over the whole plane would be equal to 4 because heat can not be created or destroyed....
A graph at that point in time is:
Now I imagine that the heat over the plane starts off as a function T(x,y) let's say it is this function:
So we have a dome of heat.

I'm imagining that the amount of heat from every point on this function spreads according to the kernel and is integrated like so:
The amount of heat at point (x,y) is the sum of all the kernels of heat around every other point on the plane.
M in the equation is T(x,y) and (a,b) is anywhere within the square (v,w) (p,q)...

So if k is 1 and t is 1 and T(x,y) is the function given, then:


which Maple still can't solve for the general (x,y) so we would have to look at a particular x,y like -3,2
In my original plot some of the temperatures were negative. 

So anyway this gets pretty computationally expensive as you solve for every point on some grid of (x,y) values, but in the end you would have an approximation of the heat map after t seconds. 


Continuous matrix multiplication

I thought of this, consider two functions in x,y like for example these:

The first matrix is defined over an x range of -10..10 and the second over a y range of -10..10, so I figured as long as these match then with this formula:

We can do a continuous analogue of matrix multiplication. The height of each function at every point is the value of each matrix in each of it's infinite cells. Then the formula given sums the product of each item in the row in the first matrix with each element in the column in the second matrix just as you would with regular matrix multiplication.

The result:

I'm sure that there is an identity function for this operation, but I'm not sure if or what for example a function that rotates the original function after multiplication would look like...