# Tag Info

8

From what I understand there are broadly two distinct applications of mathematics to neuroscience. One uses mathematics to study the biological/chemical/physical aspects of the mechanisms in the brain, such as action potentials and the interactions between neurons. The type of math used here is differential equations/dynamic systems. Relevant wikipedia ...

6

Imagine a complex pipeline with a common source and common sink. You start to pump the water up, but you can't exceed some maximum flow. Why is that? Because there is some kind of bottleneck, i.e. a subset of pipes that transfer the fluid at their maximum capacity--you can't push more through. This bottleneck will be precisely the minimum cut, i.e. the set ...

4

These notes contain a proof. The digraph used in this proof is a little more complicated than the one that you have in mind: each point of the partial order corresponds to two vertices of the digraph. Let $\langle P,\preceq\rangle$ be the partially ordered set; I’ll write $p\prec q$ to indicate that $p\preceq q$ and $p\ne q$. For each $p\in P$ the digraph ...

4

There are many ways to associate a group to a graph, some interesting, some artificial. I'm not sure what the motivation is behind the question. Given a graph $G$, the automorphisms of $G$ form a group called $\mbox{Aut}(G)$. Given a connected graph $G$, think of it as a topological space, pick a base point, and consider the fundamental group ...

4

Yes, you should increase the capacity of reverse edge by flow sent. Each time sending some flow by edge you should update its reverse edge too, so that flow passes only in one direction and the reverse edge has capacity = initial capacity + flow. http://stackoverflow.com/questions/7687732/maximum-flow-ford-fulkerson-undirected-graph ...

4

Well spotted. In a case like this, it's a good idea to check the article's history (using the "View history" link at the top). In the present case, the error was introduced only two days ago by an anonymous user in this edit (which I just reverted).

3

A side remark: it is called a skew-symmetry, because of the minus sign (source). Also, your third rule should be $$\sum_{v \in V} f(u, v) = 0, \quad \text{for all u \in V \setminus \{s,t\}},$$ because the flow between each vertex and start/target one should also be considered in the sum (see my explanation of the conservation of flow a bit lower), but it ...

3

First of all, the algorithm terminates because at least one edge is saturated in each step and there is a finite number of edges. Now let $f$ be the resulting flow, and assume $f'$ is some greater flow through the tree. For $f'$ to be a greater flow than $f$, we must have $f'(e)\gt f(e)$ for at least one edge $e$ leading away from the source. Now ...

3

What you're looking for is described on pages 247-249 of Robert Vanderbei's Linear Programming: Foundations and Extensions (2nd edition), although Vanderbei has some of his sign conventions opposite of yours. Take a close look in particular at Figure 14.4 on page 249 ("Adding a new node to accommodate an arc $(i,j)$ having an upper bound $u_{ij}$ on its ...

3

A cut set is not necessarily an edge cut. Think about it: If $X$ in the definition of cut set is not itself connected, then you need to restore more than one edge to reconnect $G$. Also, cut sets appear to be defined even for a graph that is not connected to begin with.

3

This does not compute an exact value but some rigorous upper bounds of the probability $r$ that every site in $\mathbb Z^2$ is reached, eventually. Consider the Galton-Watson branching process where the progeny of every individual has the distribution of the number of signals transmitted at time $n+1$ by any site reached at time $n$. Thus the progeny of ...

3

In the same vein as Didier's answer providing bounds on the extinction probability $q$, we can also obtain bounds on the transmission probability $p$ required for the probability of $N$ signals dying out to go to $0$ as $N\to\infty$, which is the probability required for the extinction probability $q$ not to be $1$. Didier's equation for $q$ can be ...

3

3

Probably you'll find this one very useful. Chapter 5 ($M/M/C$ queue) corresponds to your model, where it is assumed that there are $c$ servers, the service time is exponentially distributed, and so are the interarrival times (of course, with different means). Anyway, the key is $M/M/C$ (or $M/M/N$, etc.) queue.

3

Judging from your question, I think you may be misinterpreting the sums. From left to right, you're summing over: The arcs that have "s" as their tail The arcs that have "s" as their head The arcs that have "t" as their head The arcs that have "t" as their tail. In particular, the sums in the lemma do not involve any arcs that are not incident to s or t. ...

3

Other ways to associate a group (but typically infinite ones) are the following: Graph of Groups: See e.g. Serre, "Trees" or the corresponding wiki-article. These are groups arising from actions on graphs (trees). See also its generalization, called Complexes of groups (see e.g. Bridson, Haefliger, "Metric spaces of non-positive curvature" RAAGs: Right ...

3

This is not a good definition: Two graphs are equivalent if they have the same set of edges (ex. (A,B),(A,C)). It should be: Two graphs are equal if they have the same vertex set and the same set of edges. E.g. these two graphs are equal: (although they are drawn differently) and no two of these three graphs are equal: Equivalence ...

3

Commonly used models in mathematical physics for collections of neurons are so-called neural networks. Here is some general explanation of the models. Some popular models are the Hopfield model, Ashkin-Teller neural networks, Blume-Emery-Griffiths neural networks,... Techniques used to solve them involve statistical mechanics which result in partition ...

3

In your example the cut is $[\{s\},\{a,b,t\}]$; its capacity is $1$, since the only edge that is cut is $sa$. There are two min cuts in your example, $[\{s\},\{a,b,t\}]$ and $[\{s,a,b\},\{t\}]$, each with capacity $1$. The only other cut is $[\{s,a\},\{b,t\}]$, which has infinite capacity. Your ‘no edge from $S\cap T$ to $T\cap Y$’ should read ‘no edge ...

2

This is not the case. consider this(poorly drawn) counter example: let all the edges be directed from left to right. Let s, the source be the left-most vertex and t, the sink be the right-most. Then the minimum cut separates t from everything else, but adding one to the capacity of each arc changes the minimum cut to be the one that separates s from ...

2

I see now! If $f(x,y) < c(x,y)$ for some $(x,y) \in (X,\overline{X})$ or $f(x,y) = 0$ for some $(x,y) \in (\overline{X},X)$, then the value of the flow is less than the capacity of a cut. This contradicts the max-flow min-cut theorem. More precisely: Let $F$ be the value of a maximal flow, $(X,\overline{X})$ a cut, and suppose $f(x,y) < c(x,y)$ for ...

2

I did my thesis on something similar: Basically, I mapped an edge-colored graph to a subgroup of a permutation group. Suppose $|G|=n$ and label its vertices from $1$ to $n$. Then, each color used for the coloration of the edges of the graph is mapped to a transposition in $S_n$: For a color $\alpha$ used on the edges $v_{k_1}v_{k_2}, v_{k_3}v_{k_4}, \cdots, ... 2 Make a vertex that is the source of the two inputs, and connect this vertex with the input vertices in your problem. Then apply a suited algorithm. 2 Hint: Create$G'$as follows: For any$w \in V$create two vertices$w_\text{in}$and$w_\text{out}$. Connect them with an edge of zero cost. For any$e \in E$create two vertices$e_\text{in}$and$e_\text{out}$. Connect them with an edge of zero cost. For any$e = (w \to w') \in E$add edges$\{w_\text{out},e_\text{in}\}$and$\{e_\text{out}, ...

2

How to understand the conservation factors? It is clearly stated that a[u] * f_in[u] <= f_out[u] <= b[u] * f_in[u], where a[u] and b[u] are some non-negative numbers. I do not understand what is unclear here. For what I understand, if a vertex have a total in_flow of 100, and the conservation factor is 50%-80%, then the total out_flow would be ...

2

There are no graphs for which the Tutte polynomial is $0$. One thing that would go wrong if there were such a graph: The chromatic polynomial is contained within the Tutte polynomial; if the Tutte polynomial were $0$, then the graph would not be $k$-colourable for all $k \geq 0$. But this is impossible since e.g. we can colour each vertex a different ...

2

Each of the basic flows you're using should conserve flow at nodes other than s and t. For convenience, write e.g [acba] as a flow of 1 unit on the cycle $a \to b \to c \to a$, and [sat] as 1 unit on $s \to a \to t$. So you could end up with something like $\frac{3}{2} [sat] + 2 [acba] + [abta]$ (just for illustration; that's not the answer here)

2

One way to think about this is by the infamous max flow - min cut theorem which states; The maximum value of the flow from a source node s to a sink node t in a capacitated network equals the minimum capacity among all s-t cuts. [S,Sbar] Since, after multiplying all capacities by a constant C, the minimum s-t cut doesn't change, moreover the ...

2

This is a linear system; as explained here, systems of linear diophantine equations can be solved by finding their Smith normal form or Hermite normal form. (The first link explains how to use the Smith normal form in detail. Using the Hermite normal form is analogous. An online calculator for the Hermite method, using the "LLL-based algorithm of ...

2

A maximum flow is a flow that attains the highest flow value possible for the given network. A maximal flow is a flow whose value cannot be increased without decreasing the flow along some arc. All maximum flows are maximal flows. Not all maximal flows are maximum flows. Figure 3.9 in the Bang-Jensen and Gutin textbook, first edition illustrates an ...

Only top voted, non community-wiki answers of a minimum length are eligible