text:
## Humanizing atan2

I’m sure everyone of you got livid with the return value of the atan2 functions. Here is a fix.

This is Java code, but easy to adapt for other languages. And since you are here, a little hint: Multiply the result with 180 / Math.PI to receive the angle in degrees.

## Moved to Icinga

I just installed Icinga, it was the right decision!

First of all respect to the Icinga guys, the compatibility to Nagios is great! Moving from Nagios to Icinga is mainly copy and paste. Syntax is the same, management structure also equals, you can even use all your previous installed Nagios plugins and the nagios-checker add on. Well done! Except for the web interface (looks much more professional) every feels like Nagios. So I can’t see any reason to stay with Nagios.

Here are some things I had to do:

• First of all I changed the credentials for the web interface:
• This new user needs also authorizations, so you need to edit /etc/icinga/cgi.cfg and replace icingaadmin with NewUser .
• The rights in /var/lib/icinga/rw/ were wrong, www-data wasn’t able to access the directory. So I wasn’t able to schedule manual checks via web. When I changed the permissions everything was fine:
• I added the following into the DirectoryMatch directive of /etc/icinga/apache2.conf , to force me to use SSL encryption:
• I shortened the mail subject of the notifications. By default the subject looks like:

But I’m just interested in the important parts, so I changed the following in /etc/icinga/commands.cfg :

to:

the the notifications now come with a subject like this:

All in all I’m glad that I gave Icinga this chance and recommend to test it if you are still using Nagios. Maybe I’ll test some further Icinga features and maybe we’ll migrate at the university..

## Inspecting Java startups

The developers around you might know that there are some mechanism hooked when creating an object. Lets have a look at the order of these processes.

Even beginners should know about constructors. They are called if you create an object of a class, but there are some things running before. Here is an example class:

The output is:

As you can see, first of all the static initializer is called. It’s also called exactly once, when the class is loaded. It’s clear that the class has to get loaded before the main () inside can be executed. The main () then prints a string to indicate the start of that routine and afterwards it creates the first object of the type Initializing . This calls the instance initializer before the constructor is executed. Also the creation of the second object calls first the instance initializer and then the constructor. That’s the workaround. At the first time a certain class is used the static initializer is executed, and each time an object of that class is created first the instance initializer is called and then the constructor. Btw. all of these routines are able to access members that are private, but notice that the static initializer can only access static fields.

## Stupid handycrafts

Today I had to install a new server for some biologists, they want to do some NGS. It took a whole day and all in all we’ll send it back…

These biologists ordered the server without asking us, I think the salesmen noticed that they don’t have expertise. The money is provided by the university, so no need to design for efficiency. And that is how it came that they send the hardware (2 Xeon-DP 5500, 72 GB mem) in a desktop case with a Blu-ray writer, a DVD-writer, a GPU with 2.72 TeraFLOPS (afaik they don’t want to OpenCL) and: NO CHASSIS FANS!! Ouch..

It’s as clear as daylight that this cannot work. Did they thought the hot air around the mem (18 slots, each 4GB) leaves the chassis by diffusion?? The processor cooling construction for my Athlon X2 is twice as big as all their fans together…

After setting up a Linux and installing lm-sensors the CPU’s are running at >75°C, fighting for air. Of course we immediately turned off the hardware! After half an hour we were able to start it again and took a look at the BIOS sensors for the memory. No time to get bored while the temperatures raised up to 80°C and more in less than 5 min, see figure 2… Of course time to turn it off again! Don’t want to hazard a nuclear meltdown..

They also enclosed a raid controller. I’ve googled that. Less than 100\$.. wtf… The controller came with a CD to create a driver disk. But when you boot into the small Linux on the CD it hangs with the message “Searching for CD…”. And there is no driver for us, you are only able to use this controller when you are running Win 2003/XP/Vista or a RHEL or a Suse Enterprise. Other systems are not supported.. Proprietary crap..

What should I say, I’m pissed off. A whole business day is gone for nothing… Just because of some less-than-commodity handycrafts… I strongly recommend to ask Micha before plugging such bullshit!

## Closer look to Triwave and MSE

After getting started to work with the new Synapt G2 HDMS from Waters a few questions about the working principle of this machine came up. Here I’ll try to explain where the drift time detector is located and how the software can distinguish between fragments produced in the trap and transfer cell, respectively.

As far as I know Waters is the first manufacturer who joined the IMS- and QTOF-technologies to combine all well known benefits from the QTOF instruments plus the advantages of separating ions by their shape and size.

But lets start at the beginning. As any other MS instrument the Synapt carries an ion source. Here are also some attractive innovations located, but nothing remarkable for now, so I won’t explain anything of it. The interesting magic part starts when the ions pass the quadrupole. To give you a visual feedback of my explanations I created an image of the hierarchical ion path:

Assume only one big black ion has entered the machine and found its way to the quadrupole. This ion will now follow the ion path and arrive at the Triwave cell, consisting of a trap cell, the new IMS cell and a transfer cell. Trap and transfer cell are able to fragment the ions, so you can produce fragments before and/or after separation by ion mobility. Producing fragments is nothing new, most of the MS instruments out there are able to do so.

So consider this big black ion is decayed in the trap cell into three smaller ions, a blue, a red and a green one:

As the figure indicates all fragments have different shape sizes and actually share the same velocity. They now enter the magic IMS cell and an IMS cycle starts. This cell is a combination of two chambers. One small chamber at the front of this cell is flooded with helium and operates as a gate. During an IMS cycle it is impossible that further ions can pass this gate. The main chamber of the IMS cell is filled with nitrogen. The pressures of helium and nitrogen are sensible tuned, such that nitrogen doesn’t form an counterflow for incoming ions. Here is a smart graphic of both chambers:

These nitrogen molecules represent a barrier, so the passing ions are slowed done while they have to find their way through this chamber. Here is the awesome trick located! The bigger the ion shape the bigger the braking force and the slower the ion. A heavy but compact ion might be faster than a lightweight but space consuming ion. So the drift time through the IMS cell is independent of m/z values, it separates the ions by their shape size. Back to the example the blue ion is much smaller so it is much faster, in contrast the fat green ion is inhibited a lot by this nitrogen gas:

Thence the blue fragment arrives first at the transfer cell. Here it is again fragmented in smaller components:

Each of the smaller blue ions then reaches the TOF analyzer. Here they have to fly a specific way, the required time is tracked at the TOF-detector. Heavier ions are slower, so the resulting m/z values are measured here:

The first acquired spectrum is recorded. All blue ions have the same drift time (they were all present when the pusher pushed), but are distinguished by their mass:

At the same time the red ion was able to reach the transfer cell and got also decayed again. Passing the transfer cell they reach the pusher and the next push will make them fly through the flight tube:

All red fragments also have the same drift time, but this time differs from the drift time of the blue ions. Nothing was said about their mass, the m/z isn’t determined before their flight through the TOF analyzer! So it might (and will) happen, that they are lighter than the blue ions. At this point the spectrum will look like this:

The same will happen with the green ions. Entering transfer cell, getting decayed, flying with the next push:

At the end the spectrum produced by the big black ion might look like this:

You see, the drift time is measured without any additional IMS detector! A common MS instrument is just able to record the left m/z spectrum, so if it produces the same seven fragments you are only able to identify five peaks. Since the dark blue and the light red ions have the same mass (they are called isobars) the produced peak is a merge of both ions. Same issue with the dark red and the light green ion. The new IMS technology now enables you to split this peak by the required drift time. Nice, isn’t it?

Ok, so far, back to reality! First of all I have to say the images are not true to scale, I’ve warped the elements for a better representation. The size of the IMS cell is not comparable with the size of the TOF! Fortunately the IMS cell was broken so I was able to look into the machine (figure 1). While the TOF is about 1m the IMS cell is a bit longer than half of a keyboard length, see figure 2. By the way the ions don’t fly a linear way through the TOF analyzer. The Synapt operates with reflectrons and knows two modes: V-TOF (ions are reflected once) and W-TOF (ions are reflected three times).

The energy beam transporting the ions through the IMS cell can be understood as a wave. You can define the wave height and the velocity to effectively separate your present ions. Don’t ask me why the call it height and velocity, and not amplitude and frequency, but what ever ;-) These two parameter are nevertheless very sensitive. So if they are not chosen very well, an ion might need longer then one IMS cycle to pass the cell, so it enters the transfer cell when the next cycle is still started. I don’t have any empirical knowledge yet, but it seems to be hard to find a well setting.

The complexity of this system of curse increases crucial if there isn’t only one big black ion in your machine! So analyzing is not that trivial as my images might induce. You are also able to separately enable or disable fragmentation in trap and transfer cell. So your awareness of this process is essential to understand the resulting data.

In reality one IMS cycle takes the time of 200 pushes, but the pusher isn’t synchronized with the IMS gate. What did he say? Time to get confused! If an IMS cycle takes exactly the time of 200 pushes, ions that arrive between two pushes (one push of course takes some time) should be lost every time, because they should arrive with the next IMS cycle, exactly +200 pushes, again between two pushes. This scenario would mean your sensitivity is crap. Theoretically correct, but fortunately we can’t count on our hardware. Even if you tell the pusher to push every 44 μs, the consumed time will fluctuate in the real world. So he’ll need 45 μs for one push and 43.4 μs for the following. Instead an IMS cycle will always take 44*200=8800 μs, independent of the real time the pusher needs for 200 pushes. So if an IMS cycle starts exactly with a push the next cycle will probably start within two pushes and ions that weren’t able to catch a push last time might now get pushed.

All in all you have to agree that this is an absolutely great invention. If you are interested in further information Waters provides some videos to visualize the IMS technology, and here you can find some smart pictures of the Triwave system in a Synapt.


text:
# How to make a Neural network understand that multiple inputs are related (to the same entity)?

I am not sure if this is the right place to ask this but here goes:

Sometimes times two or more inputs of a neural networks can often be related to a single "real world" entity.

E.g : Height and weight of a person to predict the probability of disease in population or price and volume of a stock to predict the market.

When a single training set contains data about a number of these entities, how can we make a neural network understand that two inputs (or more) are related to the same entity?

Amongst all the people I have asked, the general consensus seems to be:

• Neural Networks do not work this way
• It is not possible
• Such a grouping of data is not required
• Neural Networks are supposed to find the relationship amongst inputs, you are not supposed to feed it the relationships
• The training data set need to be reworked / reconfigured
• I have never heard of such a thing

So, obviously this is not in the mainstream. Has anyone heard of any research in this direction?

P.S. If you agree with the above opinion (it can't / shouldn't be done) please provide a reason why.

• The fact that the values appear in the same input vector already conveys the information that they correspond to the same instance (entity). – alto Jan 13 '14 at 16:07
• But what happens when we have the data of a population of entities to predict something about the entire population? See my (edited) eg. – Shayan RC Jan 13 '14 at 16:12
• You'll need to add more details as there are several different ways one could approach such a problem. The most important issue would probably be if the size of the population you want to make a prediction about is fixed or not. – alto Jan 13 '14 at 16:21
• I'm trying to predict stock market crashes using a neural network but I was hoping for general answer. In this case the population size is fixed. – Shayan RC Jan 13 '14 at 16:27
• You can use a network that isn't fully connected until the end result is calculated. Certain inputs get connected together down one path, while other inputs are connected down a different path, and then they fully connect to get a result. – Frobot Mar 30 '16 at 3:48

format: plain


text:
# igraph Reference Manual

For using the igraph C library

Search the manual:

# Chapter 31. Bipartite, i.e. two-mode graphs

## 1.  Bipartite networks in igraph

A bipartite network contains two kinds of vertices and connections are only possible between two vertices of different kind. There are many natural examples, e.g. movies and actors as vertices and a movie is connected to all participating actors, etc.

igraph does not have direct support for bipartite networks, at least not at the C language level. In other words the igraph_t structure does not contain information about the vertex types. The C functions for bipartite networks usually have an additional input argument to graph, called types, a boolean vector giving the vertex types.

Most functions creating bipartite networks are able to create this extra vector, you just need to supply an initialized boolean vector to them.

## 2. Create two-mode networks

### 2.1. igraph_create_bipartite — Create a bipartite graph

int igraph_create_bipartite(igraph_t *graph, const igraph_vector_bool_t *types,
const igraph_vector_t *edges,
igraph_bool_t directed);

This is a simple wrapper function to create a bipartite graph. It does a little more than igraph_create(), e.g. it checks that the graph is indeed bipartite with respect to the given types vector. If there is an edge connecting two vertices of the same kind, then an error is reported.

Arguments:

 graph: Pointer to an uninitialized graph object, the result is created here. types: Boolean vector giving the vertex types. The length of the vector defines the number of vertices in the graph. edges: Vector giving the edges of the graph. The highest vertex id in this vector must be smaller than the length of the types vector. directed: Boolean scalar, whether to create a directed graph.

Returns:

 Error code.

Time complexity: O(|V|+|E|), linear in the number of vertices and edges.

Example 31.1.  File examples/simple/igraph_bipartite_create.c

/* -*- mode: C -*-  */
/*
IGraph library.
Copyright (C) 2008-2012  Gabor Csardi <csardi.gabor@gmail.com>
334 Harvard street, Cambridge, MA 02139 USA

This program is free software; you can redistribute it and/or modify
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301 USA

*/

#include <igraph.h>

int main() {

igraph_real_t edges2[] = {0, 1, 1, 2, 3, 4, 5, 6, 6, 5, 1, 4, 1, 6, 0, 3 };
igraph_real_t edges3[] = {0, 1, 1, 2, 3, 4, 5, 6, 6, 5, 2, 4, 1, 6, 0, 3 };
igraph_t g;
igraph_vector_bool_t types;
igraph_vector_t edges;
long int i;
int ret;

igraph_vector_view(&edges, edges2, sizeof(edges2) / sizeof(igraph_real_t));
igraph_vector_bool_init(&types, igraph_vector_max(&edges) + 1);
for (i = 0; i < igraph_vector_bool_size(&types); i++) {
VECTOR(types)[i] = i % 2;
}
igraph_create_bipartite(&g, &types, &edges, /*directed=*/ 1);
igraph_write_graph_edgelist(&g, stdout);
igraph_vector_bool_destroy(&types);
igraph_destroy(&g);

/* Error handling */
igraph_set_error_handler(igraph_error_handler_ignore);

igraph_vector_view(&edges, edges3, sizeof(edges3) / sizeof(igraph_real_t));
igraph_vector_bool_init(&types, igraph_vector_max(&edges) + 1);
for (i = 0; i < igraph_vector_bool_size(&types); i++) {
VECTOR(types)[i] = i % 2;
}
ret = igraph_create_bipartite(&g, &types, &edges, /*directed=*/ 1);
if (ret != IGRAPH_EINVAL) {
return 1;
}
igraph_vector_bool_destroy(&types);
igraph_destroy(&g);

return 0;
}

### 2.2. igraph_full_bipartite — Create a full bipartite network

int igraph_full_bipartite(igraph_t *graph,
igraph_vector_bool_t *types,
igraph_integer_t n1, igraph_integer_t n2,
igraph_bool_t directed,
igraph_neimode_t mode);

A bipartite network contains two kinds of vertices and connections are only possible between two vertices of different kind. There are many natural examples, e.g. movies and actors as vertices and a movie is connected to all participating actors, etc.

igraph does not have direct support for bipartite networks, at least not at the C language level. In other words the igraph_t structure does not contain information about the vertex types. The C functions for bipartite networks usually have an additional input argument to graph, called types, a boolean vector giving the vertex types.

Most functions creating bipartite networks are able to create this extra vector, you just need to supply an initialized boolean vector to them.

Arguments:

 graph: Pointer to an igraph_t object, the graph will be created here. types: Pointer to a boolean vector. If not a null pointer, then the vertex types will be stored here. n1: Integer, the number of vertices of the first kind. n2: Integer, the number of vertices of the second kind. directed: Boolean, whether to create a directed graph. mode: A constant that gives the type of connections for directed graphs. If IGRAPH_OUT, then edges point from vertices of the first kind to vertices of the second kind; if IGRAPH_IN, then the opposite direction is realized; if IGRAPH_ALL, then mutual edges will be created.

Returns:

 Error code.

Time complexity: O(|V|+|E|), linear in the number of vertices and edges.

 igraph_full() for non-bipartite full graphs.

### 2.3. igraph_bipartite_game — Generate a bipartite random graph (similar to Erdos-Renyi)

int igraph_bipartite_game(igraph_t *graph, igraph_vector_bool_t *types,
igraph_erdos_renyi_t type,
igraph_integer_t n1, igraph_integer_t n2,
igraph_real_t p, igraph_integer_t m,
igraph_bool_t directed, igraph_neimode_t mode);

Similarly to unipartite (one-mode) networks, we can define the G(n,p), and G(n,m) graph classes for bipartite graphs, via their generating process. In G(n,p) every possible edge between top and bottom vertices is realized with probablity p, independently of the rest of the edges. In G(n,m), we uniformly choose m edges to realize.

Arguments:

graph:

Pointer to an uninitialized igraph graph, the result is stored here.

types:

Pointer to an initialized boolean vector, or a null pointer. If not a null pointer, then the vertex types are stored here. Bottom vertices come first, n1 of them, then n2 top vertices.

type:

The type of the random graph, possible values:

 IGRAPH_ERDOS_RENYI_GNM G(n,m) graph, m edges are selected uniformly randomly in a graph with n vertices. IGRAPH_ERDOS_RENYI_GNP G(n,p) graph, every possible edge is included in the graph with probability p.

n1:

The number of bottom vertices.

n2:

The number of top verices.

p:

The connection probability for G(n,p) graphs. It is ignored for G(n,m) graphs.

m:

The number of edges for G(n,m) graphs. It is ignored for G(n,p) graphs.

directed:

Boolean, whether to generate a directed graph. See also the mode argument.

mode:

Specifies how to direct the edges in directed graphs. If it is IGRAPH_OUT, then directed edges point from bottom vertices to top vertices. If it is IGRAPH_IN, edges point from top vertices to bottom vertices. IGRAPH_OUT and IGRAPH_IN do not generate mutual edges. If this argument is IGRAPH_ALL, then each edge direction is considered independently and mutual edges might be generated. This argument is ignored for undirected graphs.

Returns:

 Error code.

Time complexity: O(|V|+|E|), linear in the number of vertices and edges.

## 3. Incidence matrices

### 3.1. igraph_incidence — Create a bipartite graph from an incidence matrix

int igraph_incidence(igraph_t *graph, igraph_vector_bool_t *types,
const igraph_matrix_t *incidence,
igraph_bool_t directed,
igraph_neimode_t mode, igraph_bool_t multiple);

A bipartite (or two-mode) graph contains two types of vertices and edges always connect vertices of different types. An incidence matrix is an nxm matrix, n and m are the number of vertices of the two types, respectively. Nonzero elements in the matrix denote edges between the two corresponding vertices.

Note that this function can operate in two modes, depending on the multiple argument. If it is FALSE (i.e. 0), then a single edge is created for every non-zero element in the incidence matrix. If multiple is TRUE (i.e. 1), then the matrix elements are rounded up to the closest non-negative integer to get the number of edges to create between a pair of vertices.

This function does not create multiple edges if multiple is FALSE, but might create some if it is TRUE.

Arguments:

 graph: Pointer to an uninitialized graph object. types: Pointer to an initialized boolean vector, or a null pointer. If not a null pointer, then the vertex types are stored here. It is resized as needed. incidence: The incidence matrix. directed: Gives whether to create an undirected or a directed graph. mode: Specifies the direction of the edges in a directed graph. If IGRAPH_OUT, then edges point from vertices of the first kind (corresponding to rows) to vertices of the second kind (corresponding to columns); if IGRAPH_IN, then the opposite direction is realized; if IGRAPH_ALL, then mutual edges will be created. multiple: How to interpret the incidence matrix elements. See details below.

Returns:

 Error code.

Time complexity: O(n*m), the size of the incidence matrix.

### 3.2. igraph_get_incidence — Convert a bipartite graph into an incidence matrix

int igraph_get_incidence(const igraph_t *graph,
const igraph_vector_bool_t *types,
igraph_matrix_t *res,
igraph_vector_t *row_ids,
igraph_vector_t *col_ids);

Arguments:

 graph: The input graph, edge directions are ignored. types: Boolean vector containing the vertex types. res: Pointer to an initialized matrix, the result is stored here. An element of the matrix gives the number of edges (irrespectively of their direction) between the two corresponding vertices. row_ids: Pointer to an initialized vector or a null pointer. If not a null pointer, then the vertex ids (in the graph) corresponding to the rows of the result matrix are stored here. col_ids: Pointer to an initialized vector or a null pointer. If not a null pointer, then the vertex ids corresponding to the columns of the result matrix are stored here.

Returns:

 Error code.

Time complexity: O(n*m), n and m are number of vertices of the two different kind.

 igraph_incidence() for the opposite operation.

## 4. Project two-mode graphs

### 4.1. igraph_bipartite_projection_size — Calculate the number of vertices and edges in the bipartite projections

int igraph_bipartite_projection_size(const igraph_t *graph,
const igraph_vector_bool_t *types,
igraph_integer_t *vcount1,
igraph_integer_t *ecount1,
igraph_integer_t *vcount2,
igraph_integer_t *ecount2);

This function calculates the number of vertices and edges in the two projections of a bipartite network. This is useful if you have a big bipartite network and you want to estimate the amount of memory you would need to calculate the projections themselves.

Arguments:

 graph: The input graph. types: Boolean vector giving the vertex types of the graph. vcount1: Pointer to an igraph_integer_t, the number of vertices in the first projection is stored here. ecount1: Pointer to an igraph_integer_t, the number of edges in the first projection is stored here. vcount2: Pointer to an igraph_integer_t, the number of vertices in the second projection is stored here. ecount2: Pointer to an igraph_integer_t, the number of edges in the second projection is stored here.

Returns:

 Error code.

 igraph_bipartite_projection() to calculate the actual projection.

Time complexity: O(|V|*d^2+|E|), |V| is the number of vertices, |E| is the number of edges, d is the average (total) degree of the graphs.

Example 31.2.  File examples/simple/igraph_bipartite_projection.c

/* -*- mode: C -*-  */
/*
IGraph library.
Copyright (C) 2008-2012  Gabor Csardi <csardi.gabor@gmail.com>
334 Harvard street, Cambridge, MA 02139 USA

This program is free software; you can redistribute it and/or modify
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301 USA

*/

#include <igraph.h>
#include <stdlib.h>

int check_projection(const igraph_t *graph,
const igraph_vector_bool_t *types,
const igraph_t *proj1,
const igraph_t *proj2) {
igraph_integer_t vcount1, ecount1, vcount2, ecount2;
igraph_bipartite_projection_size(graph, types, &vcount1, &ecount1,
&vcount2, &ecount2);
if (proj1 && igraph_vcount(proj1) != vcount1) {
exit(10);
}
if (proj1 && igraph_ecount(proj1) != ecount1) {
exit(11);
}
if (proj2 && igraph_vcount(proj2) != vcount2) {
exit(12);
}
if (proj2 && igraph_ecount(proj2) != ecount2) {
exit(13);
}
return 0;
}

int main() {

igraph_t g, p1, p2, full, ring;
igraph_vector_bool_t types;
igraph_bool_t iso;
long int i, m2 = 0, w, f, t;
igraph_vector_t mult1, mult2;

/*******************************************************/
/* Full bipartite graph -> full graphs                 */
/*******************************************************/

igraph_vector_bool_init(&types, 0);
igraph_full_bipartite(&g, &types, 5, 3, /*directed=*/ 0,
/*mode=*/ IGRAPH_ALL);

/* Get both projections */
igraph_bipartite_projection(&g, &types, &p1, &p2, 0, 0, /*probe1=*/ -1);
check_projection(&g, &types, &p1, &p2);

/* Check first projection */
igraph_full(&full, igraph_vcount(&p1), /*directed=*/0, /*loops=*/0);
igraph_isomorphic_bliss(&p1, &full, 0, 0, &iso, 0, 0,
IGRAPH_BLISS_FM, 0, 0);
if (!iso) {
return 1;
}
igraph_destroy(&full);

/* Check second projection */
igraph_full(&full, igraph_vcount(&p2), /*directed=*/0, /*loops=*/0);
igraph_isomorphic_bliss(&p2, &full, 0, 0, &iso, 0, 0,
IGRAPH_BLISS_FM, 0, 0);
if (!iso) {
return 2;
}
igraph_destroy(&full);

igraph_destroy(&p1);
igraph_destroy(&p2);
igraph_destroy(&g);
igraph_vector_bool_destroy(&types);

/*******************************************************/
/* More sophisticated test                             */
/*******************************************************/

igraph_ring(&g, 100, /*directed=*/ 1, /*mutual=*/ 1,
/*circular=*/ 1);
igraph_vector_bool_init(&types, igraph_vcount(&g));
for (i = 0; i < igraph_vector_bool_size(&types); i++) {
VECTOR(types)[i] = i % 2 ? 0 : 1;
}

/* Get both projections */
igraph_bipartite_projection(&g, &types, &p1, &p2, 0, 0, /*probe1=*/ -1);
check_projection(&g, &types, &p1, &p2);

/* Check first projection */
igraph_ring(&ring, igraph_vcount(&g) / 2, /*directed=*/ 0,
/*mutual=*/ 0, /*circular=*/ 1);
igraph_isomorphic_bliss(&p1, &ring, 0, 0, &iso, 0, 0,
IGRAPH_BLISS_FM, 0, 0);
if (!iso) {
return 1;
}

/* Check second projection */
igraph_isomorphic_bliss(&p2, &ring, 0, 0, &iso, 0, 0,
IGRAPH_BLISS_FM, 0, 0);
if (!iso) {
return 2;
}
igraph_destroy(&ring);

igraph_destroy(&p1);
igraph_destroy(&p2);
igraph_destroy(&g);
igraph_vector_bool_destroy(&types);

/*******************************************************/
/* Multiplicity test                                   */
/*******************************************************/

igraph_small(&g, 10, IGRAPH_UNDIRECTED,
0, 8, 1, 8, 2, 8, 3, 8, 4, 8, 4, 9, 5, 9, 6, 9, 7, 9, 0, 9,
-1);
igraph_vector_bool_init(&types, igraph_vcount(&g));
igraph_vector_bool_fill(&types, 1);
VECTOR(types)[8] = VECTOR(types)[9] = 0;

igraph_vector_init(&mult1, 0);
igraph_vector_init(&mult2, 0);
igraph_bipartite_projection(&g, &types, &p1, &p2, &mult1, &mult2,
/*probe=*/ -1);
check_projection(&g, &types, &p1, &p2);

if (igraph_vector_size(&mult1) != igraph_ecount(&p1)) {
return 21;
}
if (igraph_vector_size(&mult2) != igraph_ecount(&p2)) {
return 22;
}
if (VECTOR(mult1)[0] != 2) {
return 23;
}
for (i = 0; i < igraph_vector_size(&mult2); i++) {
if (VECTOR(mult2)[i] != 1 && VECTOR(mult2)[i] != 2) {
return 24;
}
if (VECTOR(mult2)[i] == 2) {
m2++;
w = i;
}
}
if (m2 != 1) {
return 25;
}
f = IGRAPH_FROM(&p2, w);
t = IGRAPH_TO(&p2, w);
if (fmin(f, t) != 0 || fmax(f, t) != 4) {
return 26;
}

igraph_vector_destroy(&mult1);
igraph_vector_destroy(&mult2);
igraph_destroy(&p1);
igraph_destroy(&p2);
igraph_destroy(&g);
igraph_vector_bool_destroy(&types);

return 0;
}

### 4.2. igraph_bipartite_projection — Create one or both projections of a bipartite (two-mode) network

int igraph_bipartite_projection(const igraph_t *graph,
const igraph_vector_bool_t *types,
igraph_t *proj1,
igraph_t *proj2,
igraph_vector_t *multiplicity1,
igraph_vector_t *multiplicity2,
igraph_integer_t probe1);

Creates one or both projections of a bipartite graph.

Arguments:

 graph: The bipartite input graph. Directedness of the edges is ignored. types: Boolean vector giving the vertex types of the graph. proj1: Pointer to an uninitialized graph object, the first projection will be created here. It a null pointer, then it is ignored, see also the probe1 argument. proj2: Pointer to an uninitialized graph object, the second projection is created here, if it is not a null pointer. See also the probe1 argument. multiplicity1: Pointer to a vector, or a null pointer. If not the latter, then the multiplicity of the edges is stored here. E.g. if there is an A-C-B and also an A-D-B triple in the bipartite graph (but no more X, such that A-X-B is also in the graph), then the multiplicity of the A-B edge in the projection will be 2. multiplicity2: The same as multiplicity1, but for the other projection. probe1: This argument can be used to specify the order of the projections in the resulting list. When it is non-negative, then it is considered as a vertex ID and the projection containing this vertex will be the first one in the result. Setting this argument to a non-negative value implies that proj1 must be a non-null pointer. If you don't care about the ordering of the projections, pass -1 here.

Returns:

 Error code.

 igraph_bipartite_projection_size() to calculate the number of vertices and edges in the projections, without creating the projection graphs themselves.

Time complexity: O(|V|*d^2+|E|), |V| is the number of vertices, |E| is the number of edges, d is the average (total) degree of the graphs.

Example 31.3.  File examples/simple/igraph_bipartite_projection.c

/* -*- mode: C -*-  */
/*
IGraph library.
Copyright (C) 2008-2012  Gabor Csardi <csardi.gabor@gmail.com>
334 Harvard street, Cambridge, MA 02139 USA

This program is free software; you can redistribute it and/or modify
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301 USA

*/

#include <igraph.h>
#include <stdlib.h>

int check_projection(const igraph_t *graph,
const igraph_vector_bool_t *types,
const igraph_t *proj1,
const igraph_t *proj2) {
igraph_integer_t vcount1, ecount1, vcount2, ecount2;
igraph_bipartite_projection_size(graph, types, &vcount1, &ecount1,
&vcount2, &ecount2);
if (proj1 && igraph_vcount(proj1) != vcount1) {
exit(10);
}
if (proj1 && igraph_ecount(proj1) != ecount1) {
exit(11);
}
if (proj2 && igraph_vcount(proj2) != vcount2) {
exit(12);
}
if (proj2 && igraph_ecount(proj2) != ecount2) {
exit(13);
}
return 0;
}

int main() {

igraph_t g, p1, p2, full, ring;
igraph_vector_bool_t types;
igraph_bool_t iso;
long int i, m2 = 0, w, f, t;
igraph_vector_t mult1, mult2;

/*******************************************************/
/* Full bipartite graph -> full graphs                 */
/*******************************************************/

igraph_vector_bool_init(&types, 0);
igraph_full_bipartite(&g, &types, 5, 3, /*directed=*/ 0,
/*mode=*/ IGRAPH_ALL);

/* Get both projections */
igraph_bipartite_projection(&g, &types, &p1, &p2, 0, 0, /*probe1=*/ -1);
check_projection(&g, &types, &p1, &p2);

/* Check first projection */
igraph_full(&full, igraph_vcount(&p1), /*directed=*/0, /*loops=*/0);
igraph_isomorphic_bliss(&p1, &full, 0, 0, &iso, 0, 0,
IGRAPH_BLISS_FM, 0, 0);
if (!iso) {
return 1;
}
igraph_destroy(&full);

/* Check second projection */
igraph_full(&full, igraph_vcount(&p2), /*directed=*/0, /*loops=*/0);
igraph_isomorphic_bliss(&p2, &full, 0, 0, &iso, 0, 0,
IGRAPH_BLISS_FM, 0, 0);
if (!iso) {
return 2;
}
igraph_destroy(&full);

igraph_destroy(&p1);
igraph_destroy(&p2);
igraph_destroy(&g);
igraph_vector_bool_destroy(&types);

/*******************************************************/
/* More sophisticated test                             */
/*******************************************************/

igraph_ring(&g, 100, /*directed=*/ 1, /*mutual=*/ 1,
/*circular=*/ 1);
igraph_vector_bool_init(&types, igraph_vcount(&g));
for (i = 0; i < igraph_vector_bool_size(&types); i++) {
VECTOR(types)[i] = i % 2 ? 0 : 1;
}

/* Get both projections */
igraph_bipartite_projection(&g, &types, &p1, &p2, 0, 0, /*probe1=*/ -1);
check_projection(&g, &types, &p1, &p2);

/* Check first projection */
igraph_ring(&ring, igraph_vcount(&g) / 2, /*directed=*/ 0,
/*mutual=*/ 0, /*circular=*/ 1);
igraph_isomorphic_bliss(&p1, &ring, 0, 0, &iso, 0, 0,
IGRAPH_BLISS_FM, 0, 0);
if (!iso) {
return 1;
}

/* Check second projection */
igraph_isomorphic_bliss(&p2, &ring, 0, 0, &iso, 0, 0,
IGRAPH_BLISS_FM, 0, 0);
if (!iso) {
return 2;
}
igraph_destroy(&ring);

igraph_destroy(&p1);
igraph_destroy(&p2);
igraph_destroy(&g);
igraph_vector_bool_destroy(&types);

/*******************************************************/
/* Multiplicity test                                   */
/*******************************************************/

igraph_small(&g, 10, IGRAPH_UNDIRECTED,
0, 8, 1, 8, 2, 8, 3, 8, 4, 8, 4, 9, 5, 9, 6, 9, 7, 9, 0, 9,
-1);
igraph_vector_bool_init(&types, igraph_vcount(&g));
igraph_vector_bool_fill(&types, 1);
VECTOR(types)[8] = VECTOR(types)[9] = 0;

igraph_vector_init(&mult1, 0);
igraph_vector_init(&mult2, 0);
igraph_bipartite_projection(&g, &types, &p1, &p2, &mult1, &mult2,
/*probe=*/ -1);
check_projection(&g, &types, &p1, &p2);

if (igraph_vector_size(&mult1) != igraph_ecount(&p1)) {
return 21;
}
if (igraph_vector_size(&mult2) != igraph_ecount(&p2)) {
return 22;
}
if (VECTOR(mult1)[0] != 2) {
return 23;
}
for (i = 0; i < igraph_vector_size(&mult2); i++) {
if (VECTOR(mult2)[i] != 1 && VECTOR(mult2)[i] != 2) {
return 24;
}
if (VECTOR(mult2)[i] == 2) {
m2++;
w = i;
}
}
if (m2 != 1) {
return 25;
}
f = IGRAPH_FROM(&p2, w);
t = IGRAPH_TO(&p2, w);
if (fmin(f, t) != 0 || fmax(f, t) != 4) {
return 26;
}

igraph_vector_destroy(&mult1);
igraph_vector_destroy(&mult2);
igraph_destroy(&p1);
igraph_destroy(&p2);
igraph_destroy(&g);
igraph_vector_bool_destroy(&types);

return 0;
}

## 5. Other operations on bipartite graphs

### 5.1. igraph_is_bipartite — Check whether a graph is bipartite

int igraph_is_bipartite(const igraph_t *graph,
igraph_bool_t *res,
igraph_vector_bool_t *types);

This function simply checks whether a graph \emph{could} be bipartite. It tries to find a mapping that gives a possible division of the vertices into two classes, such that no two vertices of the same class are connected by an edge.

The existence of such a mapping is equivalent of having no circuits of odd length in the graph. A graph with loop edges cannot bipartite.

Note that the mapping is not necessarily unique, e.g. if the graph has at least two components, then the vertices in the separate components can be mapped independently.

Arguments:

 graph: The input graph. res: Pointer to a boolean, the result is stored here. types: Pointer to an initialized boolean vector, or a null pointer. If not a null pointer and a mapping was found, then it is stored here. If not a null pointer, but no mapping was found, the contents of this vector is invalid.

Returns:

 Error code.

Time complexity: O(|V|+|E|), linear in the number of vertices and edges.


text:
# Off and Onand Add Till It's Plaid

Henri Picciotto

These are two lessons on the relationship between linear equations in ax + by = c form and their graphs.

The first explores what happens when a point moves left and right, or up and down, and how it affects its relationship to the line's equation. It lays the conceptual groundwork for solving systems graphically.

The second shows what happens graphically when you combine two linear equations by addition, subtraction, and/or scaling, and leads to a strategy for solving systems.

## Off and On

Many students have learned how to graph linear equations, but are not clear on what it means to say that a certain line is the graph of (for example) 2x - y = 3. One way to throw light on this is through looking at points which are not on the line: for a point (x,y), what is 2x - y equal to? This video shows me exploring this question.

(I used this GeoGebra file on the video.)

If you want to do this exploration with your own equations, you can use this applet.
Choose values for a, b, and c (pressing enter for each one.)
Move the point, horizontally or vertically, on or off the line, and see what happens!

Say you want to solve

Graph the two equations:

As we saw in the "Off and On" video, the solution is immediately obvious at the intersection. In this case: x = 6, y = -2. But we’re just getting started.

Notice that if you graph a multiple of one of the equations, you get the same graph as the original. (For example, 4x+6y=12 will have the same graph as 2x+3y=6.) This deserves a brief discussion.

But here is where it gets interesting: if you graph a multiple of the first equation, plus a multiple of the second equation, the resulting line still passes through the original intersection. For example, by adding the two original equations, I get 3x + y = 16. Here is the graph with the additional line:

Do this many times, to make sure everyone understands what’s going on. For example, subtract the equations, or add twice the first equation to three times the second, and so on. These are called linear combinations of the two equations. Of course, you may discuss why the new line always passes through the intersection.

Now start over with a new system, and challenge the students to come up with a linear combination that will create a vertical line through their intersection, and one that will create a horizontal line through it. (One teacher I knew years ago called this activity “add till it’s plaid”.)

Graph all suggestions, until someone figures it out. Give hints if necessary. Once someone has succeeded, discuss how that feat was accomplished.

Finally do this with yet another system, but no graphing. Tada! The method that was used to get the horizontal and vertical line is one way to solve the system.

In this video, I do an abbreviated version of this lesson:

In the video, I used this GeoGebra file.

This lesson is a version of (a part of) 10.6 in Algebra: Themes, Tools, Concepts.
Yet another version, by Chris Bolognese, is available on Desmos.


text:
# Put the 10.2% Into Perspective – It’s worse than you think

This entry was posted in Economy. Bookmark the permalink.


text:
# A mathematical problem

This problem is in two parts. Part A is A-level standard; part B is more advanced.

A. Given that k > 1.0, prove that, for large n, the largest real root of

$(x+1)^{n}=kx^{n}$

approaches

$x\sim\frac{n}{\ln k}-\frac{1}{2}$

B. Given that k > 1.0, prove that, for large n, the largest real root of

$B_{n+1}(x+1)=kB_{n+1}(x)$

approaches

$x\sim\frac{n}{\ln k}+\frac{1}{k-1}+\frac{1}{2}$

Equation B is equivalent to

$(n+1)x^{n}=(k-1)B_{n+1}(x)$

The Bernoulli polynomials $B_{n}(x)$ are described in MathWorld and Wikipedia. Numbering schemes differ: this problem uses what MathWorld describes as the “new” definition, with the first few polynomials being:

$B_{0}(x)=1$

$B_{1}(x)=x-\frac{1}{2}$

$B_{2}(x)=x^{2}-x+\frac{1}{6}$


text:
# Elementary Number Theory – Helps solve this proof using the well command principle

Let $$a_1, a_2, …, a_n ∈ Bbb {N}$$ . Prove that there is $$l ∈ Bbb {N}$$ such as $$a_i | l$$ for everyone $$i ∈ {1,2, …, n }$$ and if $$x B Bbb {N}$$ is such that each $$a_i$$ Split $$x$$then $$l | x$$.

Hi, I know this proof includes a good command method method, maybe to find $$l$$. But I am very confused as to how to solve it. Especially with the second half of the question. All answers are appreciated.


text:
# Mother of all equations

1. Oct 14, 2005

### nate808

(Cr(N2H4CO)6)4(Cr(CN)6)3 + KMnO4 + H2SO4--yields-- K2Cr2O7 + MnSO4 +CO2 + KNO3 + K2SO4+ HOH under acidic conditions

this is an oxidation reduction reaction and i am using the ion-electron method to balance the equation, however, i am having trouble breaking it into its smaller equations--can some1 please lead me into the right direcction--thnx

2. Oct 14, 2005

### eNathan

Sure, first can you put your equation into latex using gamma's and what not. I posted a very long equation in ASCII and learned my lesson :O

3. Oct 14, 2005

### Gokul43201

Staff Emeritus
Nate, textbook style questions go in the Homework Help section of the Science Education Zone. Anyway, I'd like to know where you came across this equation/who gave it to you.

The only way in general, to balance such equations, is to write out the individual ionic reactions; assign multiplicative factors to each equation and solve simultaneously (using matrices/determinants if you wish) for these factors. In this case though, you will have too many such factors and solving becomes a nightmare.

The coefficients end up being in the hundreds and even in the thousands...

4. Oct 14, 2005

### nate808

this question was given 2 me by my chemistry teacher--she said that it was the hardest problem that she had ever seen on the topic, and that it took her hours to do. My guess is that she found it in a book or something. Also, i understand the process but am having a hard time breaking it up into the individual equations

5. Oct 15, 2005

### saltydog

$$\left(Cr(N_2H_4CO)_6\right)_4\left(Cr(CN)_6\right)_3+KMnO_4+H_2SO_4\rightarrow K_2Cr_2O_7+MnSO_4+CO_2+KNO_3+K_2SO_4+HOH$$

Sorry, can't bear to see this in ASCII.

Last edited: Oct 15, 2005
6. Oct 15, 2005

### Gokul43201

Staff Emeritus
First identify all the ions species that change oxidation state(OS). Let me start off with some of the easier ones. Take Mn first. In KMnO4, it has an OS of +7 and in MnSO4 it is +2. So we write :

$$Mn^{7+} + 5e^- \rightarrow Mn^{2+}~~~~---~~(1)$$

That was easy. Let's now do something a little harder, like Cr. N2H4CO is neutral and is usually co-ordinated with $Cr^{3+}$ (this is the only thing I'm a little uncertain about). That makes the first half of that complex have +12 charge. For the second half to have -12 charge, Cr(CN)6 must have a charge of +4 (since there's 3 of them). Since CN is 1-, Cr must be 2+. In dichromate, Cr has an OS of 6+ (easy to work out). This gives :

$$Cr^{3+} + Cr^{2+} \rightarrow 2Cr^{6+} + e^-~~~~--~~(2)$$

Now there's only one more equation to write (fewer than I'd initially thought) - for N. See if you can do that....

...the rest is just messy math.

Last edited: Oct 15, 2005
7. Oct 15, 2005

### nate808

so you dont need 2 take into account how many Cr or Mn there are in the initial part of the reaction?

8. Oct 15, 2005

### Gokul43201

Staff Emeritus
You don't know yet, how many there are - you only know the ratio in which they exist in different compounds in the reaction. The point of balancing the equation is to figure out how many there are. And that involves (i) matching the number of species in the LHS and RHS, and (ii) matching the number of electrons gained to the number lost.

One way to do this is through the use of unknown multipliers. Multiply eq(1) by x, eq(2) by y, eq(3) by z, etc. and write out the two conditions described above in terms of the corresponding coefficients (which are expressions in x, y, z, etc.).

9. Oct 15, 2005

### nate808

$$2N^{-1}\rightarrow 2N^{5+} + 12e^- ~~~~---~~(3)$$

Is this correct for the N

Last edited: Oct 15, 2005
10. Oct 16, 2005

### Staff: Mentor

Funny thing is, it can be balanced without halfreactions.

Largest coefficient in the equation is 1879.

Last edited by a moderator: Aug 13, 2013
11. Oct 16, 2005

### nate808

how did u do that?

12. Oct 16, 2005

### Staff: Mentor

Algebraic approach.

Generally speaking you have to solve simultaneous equations. In this case - 8 equations and 9 unknowns. It can be solved as there is an additional condition that all coefficients must be integer.

Last edited by a moderator: Aug 13, 2013
13. Oct 16, 2005

### Gokul43201

Staff Emeritus
Can't do this without a computer though. Using half-reactions, you could possibly reduce the number of unknowns to a more manageable number...

Nate : What Borek is saying is to append a coefficient to each compound in the reaction and write out simultaneous equations to make the number of individual species match.

14. Oct 16, 2005

### Staff: Mentor

Let's try simple example:

a H2 + b O2 -> c H2O

Number of atoms of every element must be identical on both sides of equation, so:

for H: 2a + 0b = 2c
for O: 0a + 2b = c

or in simplified form:

a = c
2b = c

Two equations and three unknowns, so basically it is not possible to solve this set, but let's assume c = 1. Then:

c = 1
a = 1
b = 1/2

All three coeficients must be integers, so let's multiply them by 2:

c = 2
a = 2
b = 1

and lo - our equation is balanced:

2 H2 + 1 O2 -> 2 H2O

Gokul is right, original equation needs a computer to be solved this way.

Last edited by a moderator: Aug 13, 2013
15. Oct 16, 2005

### Lapin Dormant

Sorry, Really NICE read, Thanks, by the way, is it exothermic, or indo' or is that just a Silly question?

LD
T-hink's he might just want to hear that answer, should he wait here?

16. Oct 16, 2005

### Gokul43201

Staff Emeritus
We don't post answers to homework problems...so don't wait.

From inspection (more bonds broken than formed), I would guess the reaction is endothermic, but wouldn't bet on it.

17. Oct 16, 2005

### nate808

but dont you need to take into account oxidation numbers as well and not just the atoms?

18. Oct 16, 2005

### Staff: Mentor

There are rare cases when oxidation numbers are additional information needed for balancing.

In most cases it is enough to balance atoms and charge - especially in case of net ionic equations. You treat charge the same way you treat atoms, so for example:

a Cu2+ + b Al(0) -> c Cu(0) + d Al(3+)

gives simultaneous equations:

Cu: 1a + 0b = 1c + 0d
Al: 0a + 1b = 0c + 1d
charge: 2a + 0b = 0c + 3d

then it is simple algebra at work ;)

Last edited by a moderator: Aug 13, 2013
19. Sep 19, 2007

### ardisalis

Use the matrix method.


text:
## Wednesday, November 6, 2019

### Tiny note on an explicit metric on rational lower limit topology $\tilde{\mathbb{R}_{\ell}}$

The lower limit topology on the real line $\mathbb{R}_{\ell}$ is not metrizable. However, $\displaystyle \tilde{\mathbb{R}_{\ell}}$ the rational lower limit topology on $\displaystyle \mathbb{R}$ generated by basis: $\displaystyle [q_1,q_2)$ where, $\displaystyle q_1,q_2 \in \mathbb{Q}$ is metrizable (it's regular + 2nd countable, hence the result follows by Urysohn's metrization theorem). It's interesting to actually write down the metric one gets from Urysohn's theorem.

(Source: Our Prof asked this problem during a Topology lecture in 2016.)

The key idea is to observe that for any enumeration $\{q_n\}_{n \in \mathbb{N}}$ of the rationals $\mathbb{Q}$, the countable family of continuous function $\displaystyle f_n(x) := \begin{cases} 1 & \text{ if } x \ge q_n \\ 0 & \text{ otherwise }\end{cases}$ (continuous in $\displaystyle \tilde{\mathbb{R}_{\ell}}$ topology) separates disjoint basic clopen neighborhoods.
Hence, the evaluation map $\displaystyle f: \tilde{\mathbb{R}_{\ell}} \to \{0,1\}^{\omega}$ given by $\displaystyle f(x) = (f_n(x))_{n \in \mathbb{N}}$ is an imbedding into the Cantor space $\displaystyle \{0,1\}^{\omega}$ with product topology (as it separates points and closed sets).
Thus the pullback of the metric on Cantor space v.i.a. $f$-imbedding gives us an explicit metric for $\displaystyle \tilde{\mathbb{R}_{\ell}}$: $$d(x,y) = \sum\limits_{n=1}^{\infty} \frac{|f_n(x) - f_n(y)|}{2^n} = \begin{cases} \sum\limits_{x < q_n \le y} \frac{1}{2^n} & \text{ when } x < y \\ 0 & \text{ when } x = y.\end{cases}$$
The function $\displaystyle g(x) = \sum\limits_{q_n \le x} \frac{1}{2^n}$ is monotone increasing and precisely continuous at irrationals and only right continuous at rational points in the standard $\mathbb{R}$ topology as one would expect, and has jumps of magnitude $\displaystyle \frac{1}{2^n}$ at the point $\displaystyle x = q_n$ for each $n \in \mathbb{N}$. The metric can be written as $\displaystyle d(x,y) = |g(x) - g(y)|$.

Update (06.11.2019): I recently came across this interesting post in stack where the following interesting metric was proposed for $\mathbb{Q}_\ell$ (the rational lower limit topology):
Write your rationals as "mixed fractions," that is as their integer floor plus a fractional part and define
$$d\left(a\frac{p}{q},b\frac{r}{s}\right)=\begin{cases}|a-b|,& a\neq b\\ d'\left(\frac{p}{q},\frac{r}{s}\right), &\textrm{otherwise} \end{cases}.$$
Define the distance between pure fractions separately. Assume WLOG that $\frac{p}{q}\leq \frac{r}{s}$. Then set $$d'\left(\frac{p}{q},\frac{r}{s}\right)=\max\left(\left|\frac{p}{q}-\frac{r}{s}\right|,\frac{1}{m}\right), \frac{k}{m} \in \left(\frac{p}{q},\frac{r}{s}\right].$$
Compared to the jump function $g$ mentioned earlier this metric seems to be modeled on the discontinuities of the Thomae's function. To elaborate this point let us consider the separating family of functions $(f_r)_{r \in \mathbb{Q}}$ to be $$f_r(x) := \begin{cases} 1/q & \text{ if } x \ge r \\ 0 & \text{otherwise} \end{cases}$$ where, $r = p/q \in \mathbb{Q}$ with $(p,q) = 1$. For a fixed $r \in \mathbb{Q}$ the metric $$d_r(x,y) := \begin{cases} |x-y| & \text{ if } x,y \ge r \text{ or } x,y \le r \\ \max\left(|x-y|, 1/q\right) & \text{ if } x < r \le y\end{cases}$$ precisely makes $f_r$ continuous. Modifying the above metric to incorporate jumps at all $r \in \mathbb{Q}$ which has denominator $q$ in irreducible representation followed by a factor $q$ scaling we may consider $$d_q^\prime(x,y) := \begin{cases} q|x-y| & \text{ if } x,y \in \left[\frac{p-1}{q},\frac{p}{q}\right) \text{ for some } p \in \mathbb{Z} \\ \max\left(q|x-y|, 1\right) & \text{ if } x < \frac{p}{q} \le y \end{cases}$$ which now precisely makes those $f_r$'s continuous s.t., denominator of $r \in \mathbb{Q}$ in irreducible representation is $q$. Then the product metric constructed from these $\{d_q'\}_{q \in \mathbb{N}}$ viz. $$d' := \sup_{q \in \mathbb{N}} \left(\frac{\max(d_q',1)}{q}\right)$$ gives a metric compatible to $\mathbb{Q}_{\ell}$ equivalent to the one proposed in the post. Then Thomae's function models the 'jump set' of the metric $d'$.

The underlying "big gun" that would connect both the metrics on $\mathbb{Q}_\ell$ exhibited above would be the following theorem due to Sierpinski:
Theorem (Sierpinski, 1920). A dense in itself countable metric space is homeomorphic to $Q$.
Both the metrics $d$ and $d'$ above are constructed from explicit homeomorphisms of $\mathbb{Q}_\ell$ with $\mathbb{Q}$.

## Thursday, May 25, 2017

### Re: A note on a problem from Rudin's Real and Complex Analysis

This post is a short note regarding problem 14 from Page-59 of Rudin's Real and Complex Analysis.

Problem: Let, $f$ be a real-valued Lebesgue measurable function on $\mathbb{R}^k$, prove that there exists Borel functions $g$ and $h$ such that $\mu_k(\{x \in \mathbb{R}^k: g(x) \neq h(x)\}) = 0$ and $g(x) \le f(x) \le h(x)$ for all $x \in \mathbb{R}^k$.  (where, $\mu_k$ is the Lebesgue measure on $\mathbb{R}^k$)

As stated the proposition is incorrect. Best we can do is find Borel functions $g$ and $h$ such that $g(x) = h(x)$ a.e. $[\mu_k]$ and $g(x) \le f(x) \le h(x)$ a.e. $[\mu_k]$.

To see why it's not always possible to 'approximate' a lebesgue measurable function from both above and/or below by Borel functions, we rely on a cardinality argument. Roughly speaking, there aren't enough Borel functions to account for every modification of a lebesgue measurable function in a measure zero set.

Lemma: The cardinality of real Borel measurable functions on $\mathbb{R}$ is $2^{\aleph_0}$.

Proof: Since, constant functions are Borel measurable there are atleast $2^{\aleph_0}$ Borel functions. Again, to determine a Borel function $g$ it suffices to determine the sequence of sets $g^{-1}(q,\infty)$ for each $q \in \mathbb{Q}$ (ordered by inclusion). Since, there are $2^{\aleph_0}$ (i.e., the cardinality of Borel subsets of $\mathbb{R}$)-choices for each $g^{-1}(q,\infty)$ as $q$ varies over $\mathbb{Q}$, there are atmost $\left(2^{\aleph_0}\right)^{\aleph_0} = 2^{\aleph_0}$ real Borel measurable functions on $\mathbb{R}$. $\boxed{}$

Let us index the Borel functions by $\{g_j: j \in J\}$, where, $J$ is some indexing set with cardinality $2^{\aleph_0}$.

Start with the Cantor set $C \subset \mathbb{R}$ which is a set of lebesgue measure zero. Let $C = C_1 \sqcup C_2$ be a partition into subsets such that $|C_1| = |C_2| = 2^{\aleph_0}$. Let us index the elements of $C_1 = \{x_j : j \in J\}$ and $C_2 = \{x_j' : j \in J\}$. Now, if we consider a functions $f: C \to \mathbb{Z}$ such that $f(x_j) < g_j(x_j)$ and $f(x_j') > g_j(x_j')$ for each $j \in J$ (such a $f$ is possible to construct since $\mathbb{Z}$ is an unbounded discrete subset of $\mathbb{R}$), and extend it to $\mathbb{R}$ by defining $f(x) = 0$ for $x \in \mathbb{R}\setminus C$, we have constructed a lebesgue measurable function $f$ which violates the requirement of the proposition form the book.

N.B.: If we were given the scenario that $f$ is a 'bounded' real-lebesgue measurable function on $\mathbb{R}$ (or if, $f:\mathbb{R} \to [-\infty,\infty]$ is lebesgue measurable on the extended real-line), then it is possible to construct borel functions (respectively, extended Borel functions) with the required property that is $g \le f \le h$ for all $x \in \mathbb{R}$. As long as range of $f$ has unbounded discrete subset we may modify $f$ in the above fashion inside an uncountable subset of measure zero such that it is no longer possible to be bounded by Borel functions at all points.


text:
### Partial monoids: associativity and confluencePartial monoids: associativity and confluence

Access Restriction
Open

 Author Poinsot, Laurent ♦ Duchamp, Gérard ♦ Tollu, Christophe Source arXiv.org Content type Text File Format PDF Date of Submission 2010-02-10 Language English
 Subject Domain (in DDC) Computer science, information & general works Subject Keyword Computer Science - Discrete Mathematics ♦ cs Abstract A partial monoid $P$ is a set with a partial multiplication $\times$ (and total identity $1_P$) which satisfies some associativity axiom. The partial monoid $P$ may be embedded in a free monoid $P^*$ and the product $\star$ is simulated by a string rewriting system on $P^*$ that consists in evaluating the concatenation of two letters as a product in $P$, when it is defined, and a letter $1_P$ as the empty word $\epsilon$. In this paper we study the profound relations between confluence for such a system and associativity of the multiplication. Moreover we develop a reduction strategy to ensure confluence and which allows us to define a multiplication on normal forms associative up to a given congruence of $P^*$. Finally we show that this operation is associative if, and only if, the rewriting system under consideration is confluent. Description Reference: Journal of Pure and Applied Mathematics 3, 2 (2010) 265-285 Educational Use Research Learning Resource Type Article