Potentiostat

2014-01-13T15:54:26Z

212.89.9.84: /* Main potentiostat manufacturers (non-exhaustive list) */

{{for|the friendship theorem of [[Paul Erdős]], [[Alfréd Rényi]], and [[Vera T. Sós]] characterizing graphs in which each two vertices have exactly one neighbor|friendship graph}}
[[Image:Friends strangers graph.gif|right|frame|
All the 78 possible friends-strangers graphs with 6 nodes. For each graph the red/blue nodes
shows a sample triplet of mutual friends/strangers.]]

The '''theorem on friends and strangers''' is a [[mathematical theorem]] in an area of mathematics called [[Ramsey theory]].

==Statement==
Suppose a party has six people. Consider any two of them. They might be meeting for the first time—in which case we will call them mutual strangers; or they might have met before—in which case we will call them mutual acquaintances. The theorem says:

:In any party of six people either at least three of them are (pairwise) mutual strangers or at least three of them are (pairwise) mutual acquaintances.

==Conversion to a graph-theoretic setting==
A [[mathematical proof|proof]] of the theorem requires nothing but a three-step logic. It is convenient to phrase the problem in graph-theoretic language.

Suppose a [[Graph (mathematics)|graph]] has 6 vertices and every pair of (distinct) vertices is joined by an edge. Such a graph is called a [[complete graph]] (because there cannot be any more edges). A complete graph on <math>n\,</math> vertices is denoted by the symbol <math>K_n\,</math>.

Now take a <math>K_6\,</math>. It has 15 edges in all. Let the 6 vertices stand for the 6 people in our party. Let the edges be coloured red or blue depending on whether the two people represented by the vertices connected by the edge are mutual strangers or mutual acquaintances, respectively. The theorem now asserts:

:No matter how you colour the 15 edges of a <math>K_6\,</math> with red and blue, you cannot avoid having either a red triangle—that is, a triangle all of whose three sides are red, representing three pairs of mutual strangers—or a blue triangle, representing three pairs of mutual acquaintances. In other words, whatever colours you use, at least one of those two possibilities will occur.

==Proof==
Choose any one vertex; call it ''P''. There are five edges leaving ''P''. They are each coloured red or blue. The [[pigeonhole principle]] says that at least three of them must be of the same colour; for if there are less than three of one colour, say red, then there are at least three that are blue.

Let ''A'', ''B'', ''C'' be the other ends of these three edges, all of the same colour, say blue. If any one of ''AB'', ''BC'', ''CA'' is blue, then that edge together with the two edges from P to the edge's endpoints forms a blue triangle. If none of ''AB'', ''BC'', ''CA'' is blue, then all three edges are red and we have a red triangle, namely, ''ABC''.

==Ramsey's paper==
The utter simplicity of this argument, which so powerfully produces a very interesting conclusion, is what makes the theorem appealing. In 1930, in a paper entitled 'On a Problem in Formal Logic,' [[Frank P. Ramsey]] proved a very general theorem (now known as [[Ramsey's theorem]]) of which this theorem is a simple case. This theorem of Ramsey forms the foundation of the area known as [[Ramsey theory]] in [[combinatorics]].

==Boundaries to the theorem==
[[Image:RamseyTheory K5 no mono K3.svg|frame|A 2-colouring of ''K''5 with no monochromatic ''K''3]]

The conclusion to the theorem does not hold if we replace the party of six people by a party of less than six. To show this, we give a coloring of ''K''5 with red and blue that does not contain a triangle with all edges the same color. We draw ''K''5 as a pentagon surrounding a star. We color the edges of the pentagon red and the edges of the star blue.
Thus, 6 is the smallest number for which we can claim the conclusion of the theorem. In Ramsey theory, we write this fact as:

: <math>R(3,3: 2) = 6.\,</math>

==References==
*V. Krishnamurthy. Culture, Excitement and Relevance of Mathematics, Wiley Eastern, 1990. ISBN 81-224-0272-0.

==External links==
* [http://www.cut-the-knot.org/Curriculum/Combinatorics/ThreeOrThree.shtml Party Acquaintances] at [[cut-the-knot]] (requires Java)



[[Category:Ramsey theory]]
[[Category:Theorems in discrete mathematics]]
[[Category:Articles containing proofs]]

KiteGen

2013-10-01T13:37:04Z

212.89.223.47: /* Aluminium smelter */ spelling error correction: nerby -> nearby

== Summary ==
Antialiased chessboard using the Lanczos algorithm, made by myself based on the source in File:Antialiased.png's description. This one should be relatively close to an ideal filter, primarily because I used a lot of taps (several million) for the more problematic pixels.
== Licensing: ==
{{PD-self|date=February 2009}}

Here's the source I used, written by myself. The choice of 16384x16384 might have been overkill; I cannot spot any significant differences between this and using 1024x1024 taps all over the image. The generation took about an hour on one core of an Intel Q9450. Compile and link with "gcc -O3 -o antialias antialias.c -lm -std=gnu99".

<tt>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

/*
* Do a finer sampling the higher up we get in the picture,
* since there's much more detail there.
*/
#define SAMPLES_FROM_Y(y) ((16384 * 512) / (y*y + 512))
#define MAX_SAMPLES SAMPLES_FROM_Y(0)

float weights[MAX_SAMPLES][MAX_SAMPLES];

static inline int color(double x, double y)
{
double t, z;
int i, j, k;

x = x * (1.0 / 128.0) - 0.5;
y = y * (1.0 / 2048.0);

t = 1.0 / (y + 0.001);
z = t * x;
i = floor(t);
j = floor(z);
k = i + j;
return ((k % 2) != 0);
}

static double sinc(double x)
{
static const double cutoff = 1.220703668e-4; /* sqrt(sqrt(eps)) */

if (abs(x) < cutoff) {
/* For small |x|, use Taylor series instead */
const double x2 = x * x;
const double x4 = x2 * x2;

return 1.0 - x2 / 6.0 + x4 / 120.0;
} else {
return sin(x) / x;
}
}

static double lanczos_tap(double x)
{
if (x < -3.0 || x > 3.0)
return 0.0;
if (x < 0.0)
return sinc(-x*M_PI) * sinc(-x*M_PI / 3.0);
else
return sinc(x*M_PI) * sinc(x*M_PI / 3.0);
}

static void precalculate_weights(unsigned num_samples)
{
double total = 0.0;
for (int yi = 0; yi < num_samples; ++yi) {
double sy = 6.0 * ((double)yi / num_samples - 0.5);
double wy = lanczos_tap(sy);
for (int xi = 0; xi < num_samples; ++xi) {
double sx = 6.0 * ((double)xi / num_samples - 0.5);
weights[yi][xi] = wy * lanczos_tap(sx);
total += weights[yi][xi];
}
}

double inv_total = 1.0 / total;
for (int yi = 0; yi < num_samples; ++yi) {
for (int xi = 0; xi < num_samples; ++xi) {
weights[yi][xi] *= inv_total;
}
}
}

static double antialiased_color(double x, double y, unsigned num_samples)
{
double acc = 0.0;
double delta = 6.0 / num_samples;
int xi, yi;
double sx, sy;

for (yi = 0, sy = y - 3.0; yi < num_samples; ++yi, sy += delta) {
for (xi = 0, sx = x - 3.0; xi < num_samples; ++xi, sx += delta) {
if (color(sx, sy)) {
acc += weights[yi][xi];
}
}
}
return acc;
}
</tt>

{{Copy to Wikimedia Commons|bot=Fbot|priority=true|date=March 2012}}

formulasearchengine - User contributions [en]

Potentiostat

KiteGen