Archive for the ‘Mathematics’ Category

My notes on a brilliant connectome paper

September 25, 2016

Here are my (short, first-draft full of mistakes) notes for the brilliant paper

“Closures and Cavities in the Human Connectome”

by Ann Sizemore, Chad Giusti, Richard F. Betzel, and Danielle S. Bassett.

Link

Does the brain contain arithmetic progressions?

February 20, 2016

(version 2, will try to expand)

Imagine that you have an alphabet consisting of some symbols \lbrace a,b,c, \dots \rbrace . Now imagine another symbol; call it *. Let us say that I know how to construct words; i.e., know how to construct sequences of letters, using only letters from the alphabet. Now a friend of mine can interrupt me at any point of the sequence by shouting *. Suppose now that I only know the letters \lbrace d,o,r,s \rbrace and each time I try to spell a 5-letter word using these letters a friend of mine interrupts me by shouting the letter *. If she is really aggressive, the outcome could be something like ***** . If not I could say something like door*. A word containing at least one interruption is called a root.
Now imagine that someone else listens to us. If I start saying the word ‘door’ and my friend interrupts me the listener can guess the following:

  1. I said dooro
  2. I said doors
  3. I said doorr
  4. I said doord

This set is called the combinatorial line of the root door*.
Making the previous a little bit more mathematical, let A be a finite symbol alphabet. Let * be the new symbol. Words are considered as sequences of symbols of the alphabets without containing the letter * . Sequences containing at least one * symbol are called roots. If in each such root we replace the * with each symbol of the alphabet, we get a collection of words rooted by the specific root. A combinatorial line is the set of words that stems from simultaneous replacement each time of the symbol * by one of the alphabet symbols.

Exercise: Suppose that there exists an alphabet consisting of 0 and 1. Calculate the number of combinatorial lines for sequences of length n .
(Solution Here)

Brain parcellation
In order for neuroscientists to study the properties of each area in the brain (either neurophysiological or, if someone considers mathematical models of nodes and edges in the brain, topological properties), they use some specific parcellation where each area has specific coordinates in a standard space.

What I will do here is play a little bit with combinatorial lines and the extended-AAL atlas coordinates. These coordinates characterize a set of cortical and subcortical areas as well as areas of the cerebellum, commonly used in fMRI. In short, cortical ROIs are from the FSL Harvard-Oxford Atlas maximum likelihood cortical atlas, subcortical ROIs are from the FSL Harvard-Oxford Atlas maximum likelihood subcortical atlas, and cerebellar parcellation is from the AAL Atlas. Here, I used the labels and coordinates (excluding the final 8 “Vermis” areas) as found in the Conn toolbox (https://www.nitrc.org/projects/conn/).

Binary encoding and combinatorial lines
I will encode these areas based on a specific binary encoding. Therefore, in this case our alphabet A consists of two symbols: 0 or 1. They way to assign each area to the aforementioned encoding is completely arbitrary.
For example, I can have something like this:

      000 ; Hippocampus

 

      001 ; Posterior Cingulate

 

      010 ; …

 

      011

 

      100

 

      101

 

      110

 

      111

The pair 010, 111 can be considered as a combinatorial line (with root *1*) whereas the pair 010,101 cannot. Now, for every entry in the encoding, we are going to search all other entries and see if, as a pair, they become a combinatorial line.

What I did for this post is to encode the areas (121 in total) based on their Euclidean distance from a reference point. For each area, I calculated the Euclidean distance between its xyz coordinates and the (0,0,0) point. Then, I sorted them in an ascending order and used a 8 bit binary encoding. Therefore the 00000000 will be the area with smallest distance from (0,0,0) the 00000001 will be the area with somewhat bigger distance and so on.
What I did afterwards was to find all the combinatorial lines in this encoding for each area. Remember that, since we are using binary encoding, a combinatorial line will be a pair of areas; for example, 00000000 and 00000001 could be the combinatorial line with root 0000000* (there can be other roots for this pair). Eventually, for each area, I found all the combinatorial lines (pairs that include the respective area) that also belong to the encoding.

Results
Having all the combinatorial lines for each area, I tried to plot some of them! In the next pictures (you may need to click and zoom for a better resolution), I depict as the big yellow node the area that I considered. The other nodes stand for the areas that the combinatorial lines of the considered area consist of.

Here is the left angular gyrus.
Left angular combinatorial lines

Here is the right angular gyrus.
Right angular combinatorial lines

(I was hoping for a default-mode network but didn’t see a clear picture of it : )).

Discussion
What I described previously is an attempt to encode brain areas and find combinatorial lines within this encoding.

Combinatorial lines can be viewed as geometrical lines in a A^n dimensional cube of words, where A is the set of symbols for the alphabet. An interesting aspect is whether, given a specific alphabet and some categorization (in terms of each word belonging to a category), there exist combinatorial lines that are in the same category.

The Hales-Jewett theorem claims that there is a length of words (or dimension of the cube) such that every coloring on words induces a monochromatic combinatorial line.

Theorem (Hales-Jewett, 1963)

Given r distinct colors and a finite alphabet A of t =|A| symbols, there is a dimension n := HJ(r,t) \in \mathbb{N} such that, for every r- coloring of the cube A^n , there exists a monochromatic combinatorial line.

One can think of this as a game. If each color corresponds to a player’s move, there exists a dimension (that depends on the number of the symbols used in the game and the number of players) such that a player can obtain a multi-dimensional line of her own color (pretty much win).

My line of thought is the following:

In recent years, neuroimaging studies have adopted network models in order to analyze patterns of correlations between the neurophysiological signals of each brain area. For example, a standard methodology assumes that each area is a node in the network and edges between them exist if there is a significant correlation between the time course of their blood-oxygenated-dependent signals. Above and beyond this, one might explore the properties of each node in the network using standard network techniques.
Now, suppose that colors correspond to properties of the network. For example, each node (word) in the cube is assigned to a color based on some specific topological property (for example the number of shortest paths in the network that pass through it).

Question: If we know that, given a specific number of colors and symbols, there exists a dimension that induces monochromatic combinatorial lines, can these lines correspond to areas of the brain that share these properties by using  “suitable” color definitions and encoding each area?

In other words, can the fact that some brain areas share similar topological properties be interpreted in terms of the existence of monochromatic combinatorial lines in a suitable brain area encoding (for example encoding based on their distance from a reference point like before or their neurotransmitters density and regarding specific topological properties)?

One can go beyond this and, using the Hales-Jewett theorem, can argue that the existence of monochromatic combinatorial lines in a set imply arithmetic progressions of specific length.

The following theorem exists regarding the existence of monochromatic arithmetic progressions and can be proved using the Hales-Jewett theorem.

Theorem (Van der Waerden, 1927)
Given r distinct colors and t \in \mathbb{N} , there exists a N := W(r,t) such that for every coloring r- coloring of the set \lbrace 1, \dots, N \rbrace , there exists at least one monochromatic arithmetic progression of t terms:
\lbrace 1, \dots, \alpha, \dots, \alpha + d, \dots, \alpha + 2d, \dots, \alpha + (t-1)d, \dots, N \rbrace .

I would love to argue that areas that share the same properties can be viewed as parts of monochromatic arithmetic progressions.

General methodological question: Is there any connection between the topology of brain networks and combinatorial theories that argue about whether the size of the structure implies a specific property?

That’s all for now but I will try to expand more in later posts.

Paper of the day 03/31/15

April 1, 2015

Paper of the day:

Representations of real numbers as sums and products Liouville Numbers

by P . Erdős

Monte Carlo Methods

March 25, 2015

https://www.cs.cmu.edu/~ggordon/MCMC/ggordon.MCMC-tutorial.pdf

The Krein-Milman Theorem

January 14, 2015

Nirakar Neo's Blog

1. The Krein-Milman theorem in Locally Convex Spaces

My project work this semester focuses to understand the paper the Krein-Milman Theorem in Operator Convexity by Corran Webster and Soren Winkler, which appeared in the Transactions of the AMS [Vol 351, #1, Jan 99, 307-322]. But before reading the paper, it is imperative to understand the (usual) Krein-Milman theorem which is proved in the context of locally convex spaces. My understanding of this part follows the book A Course in Functional Analysis by J B Conway. To begin with we shall collect the preliminaries that we shall need to understand the Krein-Milman theorem.

1.1. Convexity

Let $latex {mathbb{K}}&fg=000000$ denote the real($latex {mathbb{R}}&fg=000000$) or the complex($latex {mathbb{C}}&fg=000000$) number fields. Let $latex {X}&fg=000000$ be a vector space over $latex {mathbb{K}}&fg=000000$. A subset of a vector space is called convex if for any two points in the subset, the line segment joining them…

View original post 3,073 more words

Paper of the day: 01/05/15

January 6, 2015

ROTH TYPE THEOREMS IN FINITE GROUPS, JOZSEF SOLYMOSI, 2012

http://arxiv.org/pdf/1201.3670.pdf

Paper of the day: 12/03/14

January 3, 2015

“ON THE MAXIMUM OF THE FUNDAMENTAL FUNCTIONS OF THE ULTRASPHERICAL POLYNOMIALS”, P. ERDOS, 1944

http://www.renyi.hu/~p_erdos/1944-05.pdf

Main theorem of the paper:
Let { -1 \leq x_1 < x_2 < \dots < x_n \leq 1 } be the roots of the ultraspherical polynomial {P_n^{(\alpha)}(x) } with { 0 \leq \alpha \leq 3/2 }. Let { l_k^{(n)}(x) = \dfrac{P_n^{(\alpha)}(x)}{P_n^{'(\alpha)}(x_k) (x-x_k)} } be the fundamental polynomial of the Lagrange interpolation. Then { max_{k = 1,2, \dots, n, -1 \leq x \leq 1} | l_k^{(n)}(x)| =l_1^{(k)}(-1) =l_n^{(n)}(-1)}.

.

Analysing Escher

August 17, 2013

Complex Projective 4-Space

I have just been involved in the production of an action thriller about the International Mathematical Olympiad. Since certain intervals of time were inactive and unthrilling, I decided to pass the time by writing a few cp4space articles, amongst other things. This particular one was distributed across an evening and several train journeys.

Anyway, when I was at the actual IMO a few years ago, the opportunity presented itself to visit the M. C. Escher museum in The Hague. In the process, I acquired five postcards featuring the art of M. C. Escher, which I intend to put to good use in the immediate future. Until then, however, I shall merely analyse them:

Snakes, 1969

This was Escher’s final print, and has always been particularly aesthetically pleasing. However, until now I haven’t analysed it in great detail. Ignoring the snakes themselves, which are intertwined throughout the structure in a strikingly…

View original post 1,359 more words

Logical Graphs : 1

July 29, 2013

An extremely interesting post regarding logical graphs.

Inquiry Into Inquiry

Moving Pictures of Thought

A logical graph is a graph-theoretic structure in one of the styles of graphical syntax that Charles Sanders Peirce developed for logic.

Introduction

A logical graph is a special type of graph-theoretic structure in any one of several systems of graphical syntax that Charles Sanders Peirce developed for logic.

In his papers on qualitative logic, entitative graphs, and existential graphs, Peirce developed several versions of a graphical formalism, or a graph-theoretic formal language, designed to be interpreted for logic.

In the century since Peirce initiated this line of development, a variety of formal systems have branched out from what is abstractly the same formal base of graph-theoretic structures. This article examines the common basis of these formal systems from a bird’s eye view, focusing on those aspects of form that are shared by the entire family of algebras, calculi, or languages, however they…

View original post 2,111 more words

Graph regularity

July 29, 2013

Excellent post on regularity lemma and triangle removal lemma.

Yufei Zhao

In this blog post I will give a brief introduction to Szemerédi’s Regularity Lemma, a powerful tool in graph theory. The post is based on a talk I gave earlier today at a graduate student lunch seminar.

Consider the following problem. Suppose you’re given a very large graph. The graph has so many vertices that you won’t be able to access all of them. But nevertheless you want to find out certain things about the graph. These situations come up in real world applications. Perhaps we would like to know something about a social network, e.g., Facebook, but we don’t have the resource to go through every single node, as there are simply too many of them. For the purpose of this blog post though, we won’t talk about applications and instead stick to the mathematics.

Suppose we are interested answering the following question about the very large graph:

View original post 2,610 more words