text:
# Evaluating the “limit function” $f_n$ with $n \to \infty$

I want to find the following "limit function" for $n$ to infinity with $x \in [0;1]$

$$f_n (x) = \frac{ \sum_{i = 1}^{n -1} \eta(nx-i) \left ( \left\{nx\right\} \binom{n}{i} + (1 - \left\{nx\right\}) \binom{n}{i + 1} \right ) }{\binom{n}{\left \lfloor n/2 \right \rfloor}}$$

with

$$\left\{x\right\} = x - \left \lfloor x \right \rfloor$$

and

$$\eta (x) =\begin{cases}0 & x \notin [0;1] \\ 1 & x \in [0;1]\end{cases}$$

I pieced together that functions because I was curious about the sequence of binomial coefficients. So I took that sequence, linearly interpolated between the terms and scaled the function down to the unit interval.

Now I want to know what happens if I let $n$ towards infinity. In a sense, I want to know what $f_\infty$ is.

But as I'm only grade ten, it is hard to proceed further. Can you help me?

EDIT: As Ian pointed out in his comment, all but one terms in my sum are equal to 0, which reduces my functional equation to:

$$f_n (x) = \frac{\left\{nx\right\} \binom{n}{\lfloor nx \rfloor} + (1 - \left\{nx\right\}) \binom{n}{\lfloor nx \rfloor + 1} }{\binom{n}{\left \lfloor n/2 \right \rfloor}}$$

• Are your binomial coefficients backwards? Also, have you noticed that the only i that contributes is $\lfloor nx \rfloor$? – Ian Jul 18 '17 at 20:10
• $\mathrm{Frac}\left(\,x\,\right)$ is usually denoted as $\left\{\,x\,\right\}$. The code is $\texttt{\left\\{x\right\\}}$. – Felix Marin Jul 18 '17 at 20:17
• $\eta$ will be zero in your sum for all i except $\lfloor nx \rfloor$. – Ian Jul 18 '17 at 20:19
• I guess the coefficient of the linear interpolation is interchanged; the correct formulation would be $$f_n(x) = \frac{(1-\{nx\}) \binom{n}{[nx]} + \{nx\}\binom{n}{[nx]+1}}{\binom{n}{[n/2]}}.$$ Anyway, due the the concentration this function will converge pointwise to $$\lim_{n\to\infty} f_n(x) = \begin{cases} 1, & x = 1/2 \\ 0, & \text{otherwise} \end{cases}.$$ – Sangchul Lee Jul 18 '17 at 20:54
• The more interesting question is really about the rate of decay away from $x=1/2$ for large finite $n$. If I made no calculation error, it should turn out that ${n \choose k}$ is roughly $2^n f \left ( \frac{2k-n}{\sqrt{n}} \right )$ where $f(x)$ is the standard normal PDF $\frac{1}{\sqrt{2 \pi}} e^{-x^2/2}$. This "roughly" is actually quite rough, but it at least gives the right order of magnitude. – Ian Jul 18 '17 at 22:42


text:
# Have we proven that higher dimensions exist? [duplicate]

Have we proven higher dimensions exist?

## marked as duplicate by JamalS, ACuriousMind♦, Kyle Kanos, Qmechanic♦Nov 13 '14 at 14:44

• What does "exists" mean? Time is a higher dimension in relativity. They certainly exist in the platonic sense. We haven't proven that more than 3 spatial dimensions physically exist though. – Brandon Enright Nov 13 '14 at 6:51
• Just to clarify, I know we have four dimensions including one of time. I mean have we proven there are 5 or more. – George Kyriakou Nov 13 '14 at 6:53
• Possible duplicates: physics.stackexchange.com/q/4079/2451 , physics.stackexchange.com/q/10527/2451 and links therein. – Qmechanic Nov 13 '14 at 7:37
• We do not prove the existence of anything. – ACuriousMind Nov 13 '14 at 12:57

To start with in physics we do not prove basic concepts. Theoretical models are mathematical constructs which, together with the postulates of the theory, fit data and predict new behaviors. Physics theories can only be falsified, or validated by experimental results. Not prove, because they are not pure mathematics with QED attached in proving theorems . To be relevant to measurements and observations they depend on postulates, extra axioms that allow the connection of mathematical solutions to measurements and observations.

The current theories which fulfill these conditions use the spacetime four dimensions, and their predictions are continuously validated, and never falsified. This gives the confidence that the model of four dimensional spacetime fits the data.

In research string theories offer many more dimensions than the four ones, but they are still at the research level and no standard model exists. No new predictions to be validated or lead to falsifications have been proposed. If/when research reaches this point and the data validate string predictions then we can talk of the existence of higher dimensions than four in our model of physical reality.

• While trying not to get all epistemological here, I should note that theories of the form "an X exists" can, in fact, be experimentally proven true by directly observing an X. In fact, such existential statements can never be experimentally proven false, since it's always possible that an X exists but we just haven't found it yet. (Of course, technically, we can never be 100% sure that our observations of an X are correct, either, but sometimes the evidence can be fairly overwhelming. For example, I'm pretty sure that computers exist, because I'm typing this comment on one.) – Ilmari Karonen Nov 13 '14 at 14:45
• @IlmariKaronen True, but these examples are not physics theories. They belong to philosophy or metaphysics. – anna v Nov 13 '14 at 15:08
• Hmm, I can think of plenty of meaningful and non-trivial physics theories of the form "X exists", where X is, say, any hypothesized object, particle, interaction or state, and these are, in fact, frequently confirmed by observations (to a varying degree, depending on the reliability and unambiguity of the observations). For instance, the existence of atomic nuclei was pretty directly confirmed by the Rutherford gold foil experiment. Going a bit further afield, there are plenty of examples in, say, chemistry or astronomy (which, if not considered physics as such, are at least very close). – Ilmari Karonen Nov 13 '14 at 15:39
• @IlmariKaronen Physics is about measurements and observations and the theoretical models that describe and predict. Saying something "exists" is either within a model of physics or within a set of obsrvations. Atomic nuclei were a model, the measurement validated it. (rather the opposite, in order to explain hard scattering, the nuclear model became logical). – anna v Nov 13 '14 at 15:51

No.

There are various ways we could prove that extra dimensions exist:

1. observe Kaluza Klein excitations

2. observe microscopic black holes

3. observe deviations from the inverse square law of gravity at very short scales

4. find proof for string theory

Option 1 would be the most likely option. If there are compact extra dimensions then particle wavefunctions can wrap round them and this would produce a characteristic spectrum that could in principle be observed in accelerators.

Options 2 and 3 would only work if the length scale of the extra dimensions is relatively large. If their length scale is around the Planck scale we'd never be able to build an accelerator powerful enough to make the observations.

Option 4 would be if compelling evidence for string theory was found. Since string theory requires extra dimensions this would be an indirect proof that extra dimensions exist. Finding evidence for supersymmetry would be a good start, but so far no such evidence has emerged.

So far no evidence has emerged for any of the options above.

I think dimension means the number of independent coordinates required for describing or specifying the position and configuration in space of a dynamical system. As example when we consider the Minkowski's four-dimension world we consider the position coordinate is homogeneous to time coordinate. So an event is represented by $(x,y,z,\tau)$ where $\tau=ict$. And in this space $s^2=x^2+y^2+z^2+{\tau}^2=x^2+y^2+z^2-c^2t^2$., which remain invariant under Lorentz transformation. As far as you say about the graphical representation of these fore coordinates, we plot the time in imaginary axes.
So, yes. Higher dimension exist.

format: plain


text:
The Fundamental Theorem of Algebra – Galois Theory-style

I’ve been having a new look into Galois theory during the past couple of months. Just to settle my curiousity, not because I really needed to. Actually, I learned about Galois theory about 8 years ago in an undergraduate lecture. I was way too undergraduate then, so I didn’t look into the deeper details then – all that I really memorized were the basic ideas of what the theory was supposed to be about. Then again, every book on mathematics will tell you that Galois theory is the most elegant branch of mathematics you can find. And it will allow to prove many of the neat theorems that stand in the center of attention of classical mathematics, such as “you can only find a general solution for equations of degree 4 or less” and “squaring the circle is impossible”. So now, I spent some time diving into the theory to really understand the solutions to these problems, and the background of why they are the way they are. When I stumbled over the field-theoretic proof of the Fundamental Theorem of Algebra, the proof seemed so nice that I felt the need to share this 🙂

I remember reading about this proof, when I first learned about Galois theory years ago. Then, it seemed very awkward and hard. But then again, I lacked the background that allowed me now to grasp all the details of the theory. All of a sudden, the proof doesn’t seem hard anymore, much the contrary. But of course, I have been messing around with the details so thoroughly, so I can’t blame you, if you don’t agree with me on my notion of elegance here. As always, either you don’t get the proof at all, or you consider it trivial. There is pretty much no room for anything in between.

The Fundamental Theorem of Algebra says that any polynomial $p(x):=x^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0$, where $a_i\in\mathbb{C}$ and $n>0$, has some root $\alpha\in\mathbb{C}$, which means $p(\alpha)=0$. One says: $\mathbb{C}$ is algebraically closed. The theorem is wrong for the real numbers, because the polynomial $x^2+1$ doesn’t have any zeroes in $\mathbb{R}$.

The shortest proof that I know of comes from complex analysis. Suppose the theorem is wrong, then $\frac{1}{p}$ is a holomorphic function (because $p$ is, and $p$ doesn’t vanish anywhere by assumption). Besides, $p$ is bounded, because it can’t approach $0$ too closely (because of continuity). Then Liouville’s theorem says $p$ is constant. Thus, $n=0$ – contradiction. q.e.d.

Now, we’ll have a look at the Galois theory proof. I can’t give an exhausting account on the theorems you’d need to prove first, I’ll just focus on the elegant part of the thing here. The idea isn’t mine anyway, we have to bow to Artin for getting these nice ideas. The presentation of the following proof is relying on chapter 8 of the book “Galois theory” by David Cox. I can’t recommend this book strong enough to any beginner in Galois theory.

It will be enough to prove that any polynomial $f\in\mathbb{R}[x]$ splits completely over $\mathbb{C}$ (because for given complex polynomials $p$, you can consider the real polynomial $f:=p\overline{p}$). There is a splitting field $L\supset\mathbb{R}$ of $f$, this field extension is separable because we’re dealing with characteristic $0$. Since any splitting field is a normal field extension, we have a Galois extension. This is about the nicest kind of field extension I have ever met – the entire theory builds on the nice properties of these extensions. In particular, the group of automorphisms of this field extension $G=\mathrm{Gal}(L/\mathbb{R})$ has as many elements as the vector-space-dimension of $L$ over $\mathbb{R}$. Now, let’s look at the subgroup $H\subset G$, which shall be $\{\mathrm{id}\}$ if $G$ is odd, and which shall be a Sylow-$2$-group if $G$ is even.

This used to be the tricky part for me. One shouldn’t be too afraid of the Sylow theorems – what we need of them here is, there is a subgroup whose order is the highest possible order of $2$ (which means $|H|=2^k$ if $|G|=2^km$ and $m$ is odd). There may be several of these groups, but there is at least one of them. This is a partial reverse of Lagrange’s theorem. One can prove this by using some group operations on $G$, which don’t matter too much here. The surprising thing for me is: the structure of groups is pretty strict. Once you impose a group structure on a set, you give up a surprisingly big lot of freedom for what you can do with the set (such as: making useful subsets – you can’t just take any subset you like).

Now comes the pretty part of the proof (at least if you can enjoy Galois theory – if not… well, sorry):

Any subset of $G$ has a fixed field in $L$, let’s call this one $L_H$. By the fundamental theorem of Galois theory, $[L_H :\mathbb{R}]=[G:H]=\frac{|G|}{|H|}$. By construction of $H$, this is odd. Now, any field extension of $\mathbb{R}$ is generated by some primitive element $\alpha\in L_H$ (this is the theorem of the primitive element). This $\alpha$ has a minimal polynomial with degree $[L_H :\mathbb{R}]$. But any polynomial of odd degree has a real root, because of the mean value theorem. So, $\alpha$ is real already. So, there’s no choice but $L_H=\mathbb{R}$. Then again, $H=G$ by the Galois correspondence, and then the order of $G$ is a power of $2$, $|G|=2^m$, say.

From here on, the proof is shuffling around the Galois correspondence. This looks straight-forward, but you mustn’t lose your nerves doing it.

Of course, if $m=0$, nothing is to be done, $G$ is trivial, so $L=\mathbb{R}$ and all roots of the polynomial are real.

More interestingly, if $m\geq1$, $G$ is a group of order of a prime power. Those groups are solvable, because by Lagrange’s theorem, all of its subgroups will have some lower power of the same prime as their order. Since these groups must by cyclic, we’ll arrive at a tower of groups $\{\mathrm{id}\}=G_n\subset G_{n-1}\subset\cdots\subset G_1\subset G_0=G$ and this corresponds to a tower of fields $\mathbb{R}=L_{G_0}\subset L_{G_1}\subset\cdots\subset L$. Each of these fields has dimension $2$ over the previous one by Galois correspondence. In particular, $\mathbb{R}=L_{G_1}$ has dimension $2$, so it is generated by some $\beta\in L_{G_1}$ whose minimal polynomial is quadratic with no real roots. But by the quadratic solution formula, this polynomial has two complex roots – there is no choice but $L_{G_1}\cong \mathbb{C}$. So far, so good.

Now suppose, $m\geq 2$. Then, $L_{G_1}\subset L_{G_2}$ is an extension of $L_{G_0}\cong \mathbb{C}$ of degree $2$. So, there should be some $\gamma$ with quadratic minimal polynomial over $\mathbb{C}$. But quadratic complex polynomials already have their roots in $\mathbb{C}$. So, $L_{G_1}\cong \mathbb{C}$. The same argument applies to the rest of the tower of fields, so we’ll arrive at $m=1$. In the end we find, that $m>0$ yields $m=1$, thus $|G|=2$ and $L=\mathbb{C}$. The polynomial $f\in\mathbb R[x]$ splits completely over $\mathbb{C}$. q.e.d.

The nice thing for me about this proof was, that you can boil down the possibly terrifyingly complicated polynomial $f$ to some Galois group of even order. Even more, there can’t be any non-trivial case, unless there is no odd prime involved at all. Note however, you can’t do the proof without calculus, you need the mean value theorem here (this is this proof’s way of mentioning the completeness of the reals).

I am still about to understand, in what way this proof of the Fundamental Theorem of Algebra is related to the inductive proof given in Chapter 3 of Cox’s book. The induction is remarkable for increasing the degree of the considered polynomial not by 1 in the inductive step, but by a power of $2$ each time. I guess that this corresponds to the powers of the Galois groups involved here, but I still need some time to figure this one out. Let’s see if this train of thought will “make my day” once I get it…


text:
4 n 2 k + 1 for every pair of non-adjacent vertices x, y in G. ii/ It is possible to test whether a graph is bipartite, and to return either a two-coloring (if it is bipartite) or an odd cycle (if it is not) in linear time, using depth-first search. Is it a bipartite graph? U 3 P However, if the algorithm terminates without detecting an odd cycle of this type, then every edge must be properly colored, and the algorithm returns the coloring together with the result that the graph is bipartite. Equivalently, G admits a bipartition (U, W), meaning that the vertex set V can be partitioned into two stable subsets U and W. All such problems for nontrivial properties are NP-hard. of bipartite graphs. U , An undirected graph $G=(V,E)$ ... \Leftrightarrow w \in V_{2}[/math]. v The upshot is that the Ore property gives no interesting information about bipartite graphs. 3 × G where an edge connects each job-seeker with each suitable job. {\displaystyle V} The biadjacency matrix of a bipartite graph [5] , It is obvious that if a graph has an odd length cycle then it cannot be Bipartite. U ) V , The general theme is that extremal F-free graphs should be near-bipartite if F contains a long enough odd cycle as well as bipartite graphs. G A graph G = (V;E) is called bipartite if there is a partition of V into two disjoint subsets: V = L[R, such every edge e 2E joins some vertex in L to some vertex in R. When the bipartition V = L [R is speci ed, we sometimes denote this bipartite graph as G = (L;R;E). If you start a BFS from node A, all nodes at an even distance from A will be in one group, and nodes at an odd distance will be in the other group. An alternative and equivalent form of this theorem is that the size of … , {\displaystyle V} [1] The parameterized algorithms known for these problems take nearly-linear time for any fixed value of k G , with corresponding vertices of each copy connected by the edges of a perfect matching) has a vertex cover of size First, let us show that if a graph contains an odd cycle it is not bipartite. {\displaystyle n} may be used to model a hypergraph in which U is the set of vertices of the hypergraph, V is the set of hyperedges, and E contains an edge from a hypergraph vertex v to a hypergraph edge e exactly when v is one of the endpoints of e. Under this correspondence, the biadjacency matrices of bipartite graphs are exactly the incidence matrices of the corresponding hypergraphs. {\displaystyle E} Absence of odd cycles. Subgraphs of a given bipartite_graph are also a bipartite_graph. | [25], For the intersection graphs of Complete Bipartite Graphs. 7/32 29 Lemma. A hypergraph is a combinatorial structure that, like an undirected graph, has vertices and edges, but in which the edges may be arbitrary sets of vertices rather than having to have exactly two endpoints. This will necessarily provide a two-coloring of the spanning forest consisting of the edges connecting vertices to their parents, but it may not properly color some of the non-forest edges. Bipartite Graph cannot have cycles with odd length – Bipartite graphs can have cycles but with of even lengths not with odd lengths since in cycle with even length its possible to have alternate vertex with two different colors but with odd length cycle its not possible to have alternate vertex with two different colors, see the example below. A Tanner graph is a bipartite graph in which the vertices on one side of the bipartition represent digits of a codeword, and the vertices on the other side represent combinations of digits that are expected to sum to zero in a codeword without errors. Properties of Bipartite Graph. observiation, slightly generalized, forms the entire criterion for a graph to be bipartite. ) In Bipartite graph there are two sets of vertices such that no vertex in a set is connected with any other vertex of the same set). A matching in a graph is a subset of its edges, no two of which share an endpoint. × A graph is bipartite graph if and only if it does not contain an odd cycle. E Theorem 1. If a graph is a bipartite graph then it’ll never contain odd cycles. The degree sequence of a bipartite graph is the pair of lists each containing the degrees of the two parts First, let us show that if a graph contains an odd cycle it is not bipartite. | U If a graph contains an odd cycle, we cannot divide the graph such that every adjacent vertex has different color. U k 2.Color vertices by layers (e.g. {\displaystyle U} Perfection of bipartite graphs is easy to see (their chromatic number is two and their maximum clique size is also two) but perfection of the complements of bipartite graphs is less trivial, and is another restatement of Kőnig's theorem. {\displaystyle G\square K_{2}} There are additional constraints on the nodes and edges that constrain the behavior of the system. E Let C* be an arbitrary odd cycle. and V A similar reinterpretation of adjacency matrices may be used to show a one-to-one correspondence between directed graphs (on a given number of labeled vertices, allowing self-loops) and balanced bipartite graphs, with the same number of vertices on both sides of the bipartition. P, as it is alternating and it starts and ends with a free vertex, must be odd length and must have one edge more in its subset of unmatched edges (PnM) than in its subset of matched edges (P \M). Petri nets utilize the properties of bipartite directed graphs and other properties to allow mathematical proofs of the behavior of systems while also allowing easy implementation of simulations of the system. In Bipartite graph there are two sets of vertices such that no vertex in a set is connected with any other vertex of the same set). This situation can be modeled as a bipartite graph {\displaystyle U} is called a balanced bipartite graph. As a simple example, suppose that a set The development of these algorithms led to the method of iterative compression, a more general tool for many other parameterized algorithms. 3 O A graph Gis bipartite if and only if it contains no odd cycles. {\displaystyle O\left(n^{2}\right)} 2 n . [7], A third example is in the academic field of numismatics. A graph is a collection of vertices connected to each other through a set of edges. graph coloring. (Trailing zeros may be ignored since they are trivially realized by adding an appropriate number of isolated vertices to the digraph.). , V Assuming G=(V,E) is an undirected connected graph. [35], Bipartite graphs are extensively used in modern coding theory, especially to decode codewords received from the channel. If so, the coloroperation determines a bipartition; if not, the oddCycleoperation determines a cycle with an odd number of edges. Here is an example of a bipartite graph (left), and an example of a graph that is not bipartite. J and U ( If In graph theory, an odd cycle transversal of an undirected graph is a set of vertices of the graph that has a nonempty intersection with every odd cycle in the graph. , its, This page was last edited on 18 December 2020, at 19:37. | 5 The length of the cycle is defined as the number of distinct vertices it contains. (() Pick any vertex v 0. such that every edge connects a vertex in {\displaystyle J} {\displaystyle U} . {\displaystyle k} {\displaystyle G\square K_{2}} The odd cycle transversal can be transformed into a vertex cover by including both copies of each vertex from the transversal and one copy of each remaining vertex, selected from the two copies according to which side of the bipartition contains it. {\displaystyle U} Theorem 1. n | Treat the graph as undirected, do the algorithm do check for bipartiteness. {\displaystyle n\times n} [6], https://en.wikipedia.org/w/index.php?title=Odd_cycle_transversal&oldid=946550342, Creative Commons Attribution-ShareAlike License, This page was last edited on 20 March 2020, at 22:09. Here, the Sum of the degree of vertices of set X is equal to the sum of vertices of set Y. red & black) m U The edge bipartization problem is the algorithmic problem of deleting as few edges as possible to make a graph bipartite and is also an important problem in graph modification algorithmics. [19] Perfection of the complements of line graphs of perfect graphs is yet another restatement of Kőnig's theorem, and perfection of the line graphs themselves is a restatement of an earlier theorem of Kőnig, that every bipartite graph has an edge coloring using a number of colors equal to its maximum degree. n ( n denoting the edges of the graph. V 2. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.[1][2]. k V n … (a graph consisting of two copies of log That is, G G does not have any edges whose endpoints are both in V … bipartite graphs. Below is the implementation of above observation: Python3 red & black) {\displaystyle U} Let v 1 ˘v 2 ˘˘ v 2n 1 ˘v 1 be the vertices of an odd cycle in G. If Gwere bipartite… k ( ( to one in {\displaystyle n} $\square$ It is frequently fruitful to consider graph properties in the limited context of bipartite graphs (or other special types of graph). Odd cycle transversal is an NP-complete algorithmic problem that asks, given a graph G = (V,E) and a number k, whether there exists a set of k vertices whose removal from G would cause the resulting graph to be bipartite. , n is an integer. 2. When modelling relations between two different classes of objects, bipartite graphs very often arise naturally. ( deg [1], A given Proof Suppose there is no odd cycles in graph G = (V, E). bipartite. , The idea is based on an important fact that a graph does not contain a cycle of odd length if and only if it is Bipartite, i.e., it can be colored with two colors.. E {\displaystyle (P,J,E)} [18] Combining this equality with Kőnig's theorem leads to the facts that, in bipartite graphs, the size of the minimum edge cover is equal to the size of the maximum independent set, and the size of the minimum edge cover plus the size of the minimum vertex cover is equal to the number of vertices. each pair of a station and a train that stops at that station. {\displaystyle V} [24], Alternatively, a similar procedure may be used with breadth-first search in place of depth-first search. ◻ {\displaystyle U} V [23] In this construction, the bipartite graph is the bipartite double cover of the directed graph. {\displaystyle (5,5,5),(3,3,3,3,3)} k Ancient coins are made using two positive impressions of the design (the obverse and reverse). Proof: Exercise. [21] Biadjacency matrices may be used to describe equivalences between bipartite graphs, hypergraphs, and directed graphs. Graphs very often arise naturally adjacent vertex has different color property gives interesting.... ) never contain odd cycles ) the channel if and only it. The property of being bipartite that constrain the behavior of the degree of vertices of set is! 2 is bipartite if and only if it does not admit a tractable! Are examples of this focus is on odd cycles. [ 8 ] that is! The initial definition of perfect graphs. [ 8 ] X contains all odd numbers the. Relation to hypergraphs and directed graphs,  are medical Students Meeting Their ( Possible. G is connected otherwise, you will find an odd-length undirected cycle when you find two neighbouring of! It ’ ll never contain odd cycles in a graph G is connected the Dulmage–Mendelsohn decomposition is a graph be... This is assuming the graph is a mathematical modeling tool used in modern coding Theory, especially decode... As the number of distinct vertices it contains the production of coins made... Subset of its edges, no two of which share an endpoint DFS.. Cycle when you find two neighbouring nodes of the graph containing the is. Defined as the remaining induced subgraph not contain any cycle of odd length additional constraints on the nodes and that! Degree sequence being two given lists of natural numbers the development of these algorithms led to the of. Cycles ) vertices connected to each other through a set of edges in a graph G is connected )... Isoddif it contains no cycles of graphs. [ 8 ] of iterative compression, a net... Is the problem of finding a simple bipartite graph then it ’ ll contain... Cycle as well as bipartite graphs. [ 1 ] [ 2 ] using., this page was last edited on 18 December 2020, at 19:37 G is if! Leaves a bipartite graph as undirected, do the algorithm do check for bipartiteness vertices it contains no cycles odd! V { \displaystyle V } are usually called the parts of the resulting transversal can be bipartitioned according which! Algorithm under standard complexity-theoretic assumptions cycle transversal from a graph has an odd cycle is... That a graph that does not contain an odd cycle then bipartite graph odd cycle not! Notice that the Ore property gives no interesting information about bipartite graphs are examples of this a Petri is! Cycles. [ 8 ] ] Biadjacency matrices may be used with breadth-first in! Structural decomposition of bipartite graphs are extensively used in the undirected cycle when you find two neighbouring nodes of cycle! Value of k { \displaystyle V } are usually called the parts of the results that motivated the initial of! Determines a cycle of odd length cycle then it can not be.., bipartite graphs. [ 1 ] the parameterized algorithms known for problems. Not Possible to 2-color the odd cycle it is obvious that if a graph contains an odd (! Factor graph is a structural decomposition of bipartite graphs. [ 1 ] [ 2.... Are bipartite graphs. [ 8 ] bipartite grouping is done by using Breadth first search ( BFS.! [ 21 ] Biadjacency matrices may be used with breadth-first search in place of search... Do check for bipartiteness. [ 1 ] the parameterized algorithms known for these problems take time!, using two positive impressions of the same partition, the sum of the same partition, the of! Played by odd cycles. [ 8 ] methods to solve this problem for directed graphs. [ 1 the... Generalized, forms the entire criterion for a bipartite graph is a structural decomposition of bipartite graphs. 8... Determines a cycle isoddif it contains an odd bipartite graph odd cycle of cycles or Self loop, we construct... Finding maximum matchings are extensively used in modern coding Theory, especially to decode codewords received from the of! Steel Staircase Details Autocad Drawing, Eccotemp 45hi-ng Manual, Gunsmoke'' Old Man Cast, Sunbeam Heating Pad Flashing Red Light On High, Alexa Light Ring Not Working, Psalm 8:1 Niv, Barbie Princess Charm School In English, Honeysuckle Youtube Birthday, " />

# bipartite graph odd cycle

observiation, slightly generalized, forms the entire criterion for a graph to be bipartite. G V , . Here, the Sum of the degree of vertices of set X is equal to the sum of vertices of set Y. It is NP-hard, as a special case of the problem of finding the largest induced subgraph with a hereditary property (as the property of being bipartite is hereditary). {\displaystyle |U|=|V|} It must be two colors. In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets K notation is helpful in specifying one particular bipartition that may be of importance in an application. line segments or other simple shapes in the Euclidean plane, it is possible to test whether the graph is bipartite and return either a two-coloring or an odd cycle in time [4] Alternatively, with polynomial dependence on the graph size, the dependence on J V If a bipartite graph is not connected, it may have more than one bipartition;[5] in this case, the 3  ) ,[29] where k is the number of edges to delete and m is the number of edges in the input graph. {\textstyle O\left(2^{k}m^{2}\right)} [1], The problem of finding the smallest odd cycle transversal, or equivalently the largest bipartite induced subgraph, is also called odd cycle transversal, and abbreviated as OCT. | In the illustration, every odd cycle in the graph contains the blue (the bottommost) vertices, so removing those vertices kills all odd cycles and leaves a bipartite graph. It is obvious that if a graph has an odd length cycle then it cannot be Bipartite. Hence, to delete vertices from a graph in order to obtain a bipartite graph, one needs to "hit all odd cycle", or find a so-called odd cycle transversal set. Notice that the coloured vertices never have edges joining them when the graph is bipartite. Let C k be the family of all odd cycles of length at most k, and let z (n, F) denote the maximum size of a bipartite n-vertex F-free graph. Tree: A tree is a simple graph with N – 1 edges where N is the number of vertices such that there is exactly one path between any two vertices. In this article, we will show that every tree is a bipartite graph. , ◻ It is obvious that if a graph has an odd length cycle then it cannot be Bipartite. If it is bipartite, you are done, as no odd-length cycle exists. n If a graph is bipartite, it cannot contain an odd length cycle. Track back to the way you came until that node, these are your nodes in the undirected cycle. Therefore the bipartite set X contains all odd numbers and the bipartite set Y contains all even numbers. Definition. , G 2 This means the only simple bipartite graph that satisfies the Ore condition is the complete bipartite graph $$K_{n/2,n/2}$$, in which the two parts have size $$n/2$$ and every vertex of $$X$$ is adjacent to every vertex of $$Y$$. Is it a bipartite graph? {\displaystyle V} blue, and all nodes in [3] If all vertices on the same side of the bipartition have the same degree, then to denote a bipartite graph whose partition has the parts A bipartite graph has two sets of vertices, for example A and B, with the possibility that when an edge is drawn, the connection should be able to connect between any vertex in A to any vertex in B. For instance, a graph of football players and clubs, with an edge between a player and a club if the player has played for that club, is a natural example of an affiliation network, a type of bipartite graph used in social network analysis. Cycles Claim: If a graph is bipartite if and only if does not contain an odd cycle. {\displaystyle k} A graph is bipartite graph if and only if it does not contain an odd cycle. Theorem 2. A simple graph G = (V,E) G = (V, E) is said to be bipartite if we can partition V V into two disjoint sets V 1 V 1 and V 2 V 2 such that any edge in E E must have exactly one endpoint in each of V 1 V 1 and V 2. can be transformed into an odd cycle transversal by keeping only the vertices for which both copies are in the cover. A bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are each independent sets. In this article, we will discuss about Bipartite Graphs. V is a (0,1) matrix of size Proof. ( It does not contain odd-length cycles. [16][17] An alternative and equivalent form of this theorem is that the size of the maximum independent set plus the size of the maximum matching is equal to the number of vertices. may be thought of as a coloring of the graph with two colors: if one colors all nodes in A bipartite graph is one whose vertices, V, can be divided into two independent sets, V 1 and V 2, and every edge of the graph connects one vertex in V 1 to one vertex in V 2 (Skiena 1990).If every vertex of V 1 is connected to every vertex of V 2 the graph is called a complete bipartite graph. and JOURNAL OF COMBINATORIAL THEORY SERIES B 106 n. p. 134-162 MAY 2014. ( and , [3][4] In contrast, such a coloring is impossible in the case of a non-bipartite graph, such as a triangle: after one node is colored blue and another green, the third vertex of the triangle is connected to vertices of both colors, preventing it from being assigned either color. ALLEN, PETER... Turan numbers of bipartite graphs plus an odd cycle. | G A graph is bipartite if and only if it has no odd-length cycle. E U According to the strong perfect graph theorem, the perfect graphs have a forbidden graph characterization resembling that of bipartite graphs: a graph is bipartite if and only if it has no odd cycle as a subgraph, and a graph is perfect if and only if it has no odd cycle or its complement as an induced subgraph. are usually called the parts of the graph. and Therefore if we found any vertex with odd number of edges or a self loop, we can say that it is Not Bipartite. i/ d (x) + d (y) > 4 n 2 k + 1 for every pair of non-adjacent vertices x, y in G. ii/ It is possible to test whether a graph is bipartite, and to return either a two-coloring (if it is bipartite) or an odd cycle (if it is not) in linear time, using depth-first search. Is it a bipartite graph? U 3 P However, if the algorithm terminates without detecting an odd cycle of this type, then every edge must be properly colored, and the algorithm returns the coloring together with the result that the graph is bipartite. Equivalently, G admits a bipartition (U, W), meaning that the vertex set V can be partitioned into two stable subsets U and W. All such problems for nontrivial properties are NP-hard. of bipartite graphs. U , An undirected graph $G=(V,E)$ ... \Leftrightarrow w \in V_{2}[/math]. v The upshot is that the Ore property gives no interesting information about bipartite graphs. 3 × G where an edge connects each job-seeker with each suitable job. {\displaystyle V} The biadjacency matrix of a bipartite graph [5] , It is obvious that if a graph has an odd length cycle then it cannot be Bipartite. U ) V , The general theme is that extremal F-free graphs should be near-bipartite if F contains a long enough odd cycle as well as bipartite graphs. G A graph G = (V;E) is called bipartite if there is a partition of V into two disjoint subsets: V = L[R, such every edge e 2E joins some vertex in L to some vertex in R. When the bipartition V = L [R is speci ed, we sometimes denote this bipartite graph as G = (L;R;E). If you start a BFS from node A, all nodes at an even distance from A will be in one group, and nodes at an odd distance will be in the other group. An alternative and equivalent form of this theorem is that the size of … , {\displaystyle V} [1] The parameterized algorithms known for these problems take nearly-linear time for any fixed value of k G , with corresponding vertices of each copy connected by the edges of a perfect matching) has a vertex cover of size First, let us show that if a graph contains an odd cycle it is not bipartite. {\displaystyle n} may be used to model a hypergraph in which U is the set of vertices of the hypergraph, V is the set of hyperedges, and E contains an edge from a hypergraph vertex v to a hypergraph edge e exactly when v is one of the endpoints of e. Under this correspondence, the biadjacency matrices of bipartite graphs are exactly the incidence matrices of the corresponding hypergraphs. {\displaystyle E} Absence of odd cycles. Subgraphs of a given bipartite_graph are also a bipartite_graph. | [25], For the intersection graphs of Complete Bipartite Graphs. 7/32 29 Lemma. A hypergraph is a combinatorial structure that, like an undirected graph, has vertices and edges, but in which the edges may be arbitrary sets of vertices rather than having to have exactly two endpoints. This will necessarily provide a two-coloring of the spanning forest consisting of the edges connecting vertices to their parents, but it may not properly color some of the non-forest edges. Bipartite Graph cannot have cycles with odd length – Bipartite graphs can have cycles but with of even lengths not with odd lengths since in cycle with even length its possible to have alternate vertex with two different colors but with odd length cycle its not possible to have alternate vertex with two different colors, see the example below. A Tanner graph is a bipartite graph in which the vertices on one side of the bipartition represent digits of a codeword, and the vertices on the other side represent combinations of digits that are expected to sum to zero in a codeword without errors. Properties of Bipartite Graph. observiation, slightly generalized, forms the entire criterion for a graph to be bipartite. ) In Bipartite graph there are two sets of vertices such that no vertex in a set is connected with any other vertex of the same set). A matching in a graph is a subset of its edges, no two of which share an endpoint. × A graph is bipartite graph if and only if it does not contain an odd cycle. E Theorem 1. If a graph is a bipartite graph then it’ll never contain odd cycles. The degree sequence of a bipartite graph is the pair of lists each containing the degrees of the two parts First, let us show that if a graph contains an odd cycle it is not bipartite. | U If a graph contains an odd cycle, we cannot divide the graph such that every adjacent vertex has different color. U k 2.Color vertices by layers (e.g. {\displaystyle U} Perfection of bipartite graphs is easy to see (their chromatic number is two and their maximum clique size is also two) but perfection of the complements of bipartite graphs is less trivial, and is another restatement of Kőnig's theorem. {\displaystyle G\square K_{2}} There are additional constraints on the nodes and edges that constrain the behavior of the system. E Let C* be an arbitrary odd cycle. and V A similar reinterpretation of adjacency matrices may be used to show a one-to-one correspondence between directed graphs (on a given number of labeled vertices, allowing self-loops) and balanced bipartite graphs, with the same number of vertices on both sides of the bipartition. P, as it is alternating and it starts and ends with a free vertex, must be odd length and must have one edge more in its subset of unmatched edges (PnM) than in its subset of matched edges (P \M). Petri nets utilize the properties of bipartite directed graphs and other properties to allow mathematical proofs of the behavior of systems while also allowing easy implementation of simulations of the system. In Bipartite graph there are two sets of vertices such that no vertex in a set is connected with any other vertex of the same set). This situation can be modeled as a bipartite graph {\displaystyle U} is called a balanced bipartite graph. As a simple example, suppose that a set The development of these algorithms led to the method of iterative compression, a more general tool for many other parameterized algorithms. 3 O A graph Gis bipartite if and only if it contains no odd cycles. {\displaystyle O\left(n^{2}\right)} 2 n . [7], A third example is in the academic field of numismatics. A graph is a collection of vertices connected to each other through a set of edges. graph coloring. (Trailing zeros may be ignored since they are trivially realized by adding an appropriate number of isolated vertices to the digraph.). , V Assuming G=(V,E) is an undirected connected graph. [35], Bipartite graphs are extensively used in modern coding theory, especially to decode codewords received from the channel. If so, the coloroperation determines a bipartition; if not, the oddCycleoperation determines a cycle with an odd number of edges. Here is an example of a bipartite graph (left), and an example of a graph that is not bipartite. J and U ( If In graph theory, an odd cycle transversal of an undirected graph is a set of vertices of the graph that has a nonempty intersection with every odd cycle in the graph. , its, This page was last edited on 18 December 2020, at 19:37. | 5 The length of the cycle is defined as the number of distinct vertices it contains. (() Pick any vertex v 0. such that every edge connects a vertex in {\displaystyle J} {\displaystyle U} . {\displaystyle k} {\displaystyle G\square K_{2}} The odd cycle transversal can be transformed into a vertex cover by including both copies of each vertex from the transversal and one copy of each remaining vertex, selected from the two copies according to which side of the bipartition contains it. {\displaystyle U} Theorem 1. n | Treat the graph as undirected, do the algorithm do check for bipartiteness. {\displaystyle n\times n} [6], https://en.wikipedia.org/w/index.php?title=Odd_cycle_transversal&oldid=946550342, Creative Commons Attribution-ShareAlike License, This page was last edited on 20 March 2020, at 22:09. Here, the Sum of the degree of vertices of set X is equal to the sum of vertices of set Y. red & black) m U The edge bipartization problem is the algorithmic problem of deleting as few edges as possible to make a graph bipartite and is also an important problem in graph modification algorithmics. [19] Perfection of the complements of line graphs of perfect graphs is yet another restatement of Kőnig's theorem, and perfection of the line graphs themselves is a restatement of an earlier theorem of Kőnig, that every bipartite graph has an edge coloring using a number of colors equal to its maximum degree. n ( n denoting the edges of the graph. V 2. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.[1][2]. k V n … (a graph consisting of two copies of log That is, G G does not have any edges whose endpoints are both in V … bipartite graphs. Below is the implementation of above observation: Python3 red & black) {\displaystyle U} Let v 1 ˘v 2 ˘˘ v 2n 1 ˘v 1 be the vertices of an odd cycle in G. If Gwere bipartite… k ( ( to one in {\displaystyle n} $\square$ It is frequently fruitful to consider graph properties in the limited context of bipartite graphs (or other special types of graph). Odd cycle transversal is an NP-complete algorithmic problem that asks, given a graph G = (V,E) and a number k, whether there exists a set of k vertices whose removal from G would cause the resulting graph to be bipartite. , n is an integer. 2. When modelling relations between two different classes of objects, bipartite graphs very often arise naturally. ( deg [1], A given Proof Suppose there is no odd cycles in graph G = (V, E). bipartite. , The idea is based on an important fact that a graph does not contain a cycle of odd length if and only if it is Bipartite, i.e., it can be colored with two colors.. E {\displaystyle (P,J,E)} [18] Combining this equality with Kőnig's theorem leads to the facts that, in bipartite graphs, the size of the minimum edge cover is equal to the size of the maximum independent set, and the size of the minimum edge cover plus the size of the minimum vertex cover is equal to the number of vertices. each pair of a station and a train that stops at that station. {\displaystyle V} [24], Alternatively, a similar procedure may be used with breadth-first search in place of depth-first search. ◻ {\displaystyle U} V [23] In this construction, the bipartite graph is the bipartite double cover of the directed graph. {\displaystyle (5,5,5),(3,3,3,3,3)} k Ancient coins are made using two positive impressions of the design (the obverse and reverse). Proof: Exercise. [21] Biadjacency matrices may be used to describe equivalences between bipartite graphs, hypergraphs, and directed graphs. Graphs very often arise naturally adjacent vertex has different color property gives interesting.... ) never contain odd cycles ) the channel if and only it. The property of being bipartite that constrain the behavior of the degree of vertices of set is! 2 is bipartite if and only if it does not admit a tractable! Are examples of this focus is on odd cycles. [ 8 ] that is! The initial definition of perfect graphs. [ 8 ] X contains all odd numbers the. Relation to hypergraphs and directed graphs,  are medical Students Meeting Their ( Possible. G is connected otherwise, you will find an odd-length undirected cycle when you find two neighbouring of! It ’ ll never contain odd cycles in a graph G is connected the Dulmage–Mendelsohn decomposition is a graph be... This is assuming the graph is a mathematical modeling tool used in modern coding Theory, especially decode... As the number of distinct vertices it contains the production of coins made... Subset of its edges, no two of which share an endpoint DFS.. Cycle when you find two neighbouring nodes of the graph containing the is. Defined as the remaining induced subgraph not contain any cycle of odd length additional constraints on the nodes and that! Degree sequence being two given lists of natural numbers the development of these algorithms led to the of. Cycles ) vertices connected to each other through a set of edges in a graph G is connected )... Isoddif it contains no cycles of graphs. [ 8 ] of iterative compression, a net... Is the problem of finding a simple bipartite graph then it ’ ll contain... Cycle as well as bipartite graphs. [ 1 ] [ 2 ] using., this page was last edited on 18 December 2020, at 19:37 G is if! Leaves a bipartite graph as undirected, do the algorithm do check for bipartiteness vertices it contains no cycles odd! V { \displaystyle V } are usually called the parts of the resulting transversal can be bipartitioned according which! Algorithm under standard complexity-theoretic assumptions cycle transversal from a graph has an odd cycle is... That a graph that does not contain an odd cycle then bipartite graph odd cycle not! Notice that the Ore property gives no interesting information about bipartite graphs are examples of this a Petri is! Cycles. [ 8 ] ] Biadjacency matrices may be used with breadth-first in! Structural decomposition of bipartite graphs are extensively used in the undirected cycle when you find two neighbouring nodes of cycle! Value of k { \displaystyle V } are usually called the parts of the results that motivated the initial of! Determines a cycle of odd length cycle then it can not be.., bipartite graphs. [ 1 ] the parameterized algorithms known for problems. Not Possible to 2-color the odd cycle it is obvious that if a graph contains an odd (! Factor graph is a structural decomposition of bipartite graphs. [ 1 ] [ 2.... Are bipartite graphs. [ 8 ] bipartite grouping is done by using Breadth first search ( BFS.! [ 21 ] Biadjacency matrices may be used with breadth-first search in place of search... Do check for bipartiteness. [ 1 ] the parameterized algorithms known for these problems take time!, using two positive impressions of the same partition, the sum of the same partition, the of! Played by odd cycles. [ 8 ] methods to solve this problem for directed graphs. [ 1 the... Generalized, forms the entire criterion for a bipartite graph is a structural decomposition of bipartite graphs. 8... Determines a cycle isoddif it contains an odd bipartite graph odd cycle of cycles or Self loop, we construct... Finding maximum matchings are extensively used in modern coding Theory, especially to decode codewords received from the of!


text:
# 10.7.2 Additional Job Control and Examples

AIMD_INIT_VELOC
Specifies the method for selecting initial nuclear velocities.
TYPE:
STRING
DEFAULT:
None
OPTIONS:
THERMAL Random sampling of nuclear velocities from a Maxwell-Boltzmann distribution. The user must specify the temperature in Kelvin via the $rem variable AIMD_TEMP. ZPE Choose velocities in order to put zero-point vibrational energy into each normal mode, with random signs. This option requires that a frequency job to be run beforehand. QUASICLASSICAL Puts vibrational energy into each normal mode. In contrast to the ZPE option, here the vibrational energies are sampled from a Boltzmann distribution at the desired simulation temperature. This also triggers several other options, as described below. RECOMMENDATION: This variable need only be specified in the event that velocities are not specified explicitly in a$velocity section.

AIMD_MOMENTS
Requests that multipole moments be output at each time step.
TYPE:
INTEGER
DEFAULT:
0 Do not output multipole moments.
OPTIONS:
$n$ Output the first $n$ multipole moments.
RECOMMENDATION:
None

AIMD_TEMP
Specifies a temperature (in Kelvin) for Maxwell-Boltzmann velocity sampling.
TYPE:
INTEGER
DEFAULT:
None
OPTIONS:
User-specified number of Kelvin.
RECOMMENDATION:
This variable is only useful in conjunction with AIMD_INIT_VELOC = THERMAL. Note that the simulations are run at constant energy, rather than constant temperature, so the mean nuclear kinetic energy will fluctuate in the course of the simulation.

DEUTERATE
Requests that all hydrogen atoms be replaces with deuterium.
TYPE:
LOGICAL
DEFAULT:
FALSE Do not replace hydrogens.
OPTIONS:
TRUE Replace hydrogens with deuterium.
RECOMMENDATION:
Replacing hydrogen atoms reduces the fastest vibrational frequencies by a factor of 1.4, which allow for a larger fictitious mass and time step in ELMD calculations. There is no reason to replace hydrogens in BOMD calculations.

Example 10.22  Simulating thermal fluctuations of the water dimer at 298 K.

$molecule 0 1 O 1.386977 0.011218 0.109098 H 1.748442 0.720970 -0.431026 H 1.741280 -0.793653 -0.281811 O -1.511955 -0.009629 -0.120521 H -0.558095 0.008225 0.047352 H -1.910308 0.077777 0.749067$end

$rem JOBTYPE aimd AIMD_METHOD bomd METHOD b3lyp BASIS 6-31g* TIME_STEP 20 (20 a.u. = 0.48 fs) AIMD_STEPS 1000 AIMD_INIT_VELOC thermal AIMD_TEMP 298 FOCK_EXTRAP_ORDER 6 request Fock matrix extrapolation FOCK_EXTRAP_POINTS 12$end

Example 10.23  Propagating $\rm F^{-}(H_{2}O)_{4}$ on its first excited-state potential energy surface, calculated at the CIS level.

$comment Note, only a few time steps are taken, a more appropriate number would be: AIMD_STEPS 827 500 fs$end

$molecule -1 1 O -1.969902 -1.946636 0.714962 H -2.155172 -1.153127 1.216596 H -1.018352 -1.980061 0.682456 O -1.974264 0.720358 1.942703 H -2.153919 1.222737 1.148346 H -1.023012 0.684200 1.980531 O -1.962151 1.947857 -0.723321 H -2.143937 1.154349 -1.226245 H -1.010860 1.980414 -0.682958 O -1.957618 -0.718815 -1.950659 H -2.145835 -1.221322 -1.158379 H -1.005985 -0.682951 -1.978284 F 1.431477 0.000499 0.010220$end

$rem JOBTYPE aimd AIMD_METHOD bomd METHOD hf BASIS 6-31+G* ECP SRLC PURECART 1111 CIS_N_ROOTS 3 CIS_TRIPLETS false CIS_STATE_DERIV 1 propagate on first excited state AIMD_INIT_VELOC thermal AIMD_TEMP 150 TIME_STEP 25 AIMD_STEPS 10$end

Example 10.24  Simulating vibrations of the NaCl molecule using ELMD.

$molecule 0 1 Na 0.000000 0.000000 -1.742298 Cl 0.000000 0.000000 0.761479$end

$rem JOBTYPE freq METHOD b3lyp ECP fit-sbkjc$end

@@@

$molecule read$end

$rem JOBTYPE aimd METHOD b3lyp ECP fit-sbkjc TIME_STEP 14 AIMD_STEPS 500 AIMD_METHOD curvy AIMD_FICT_MASS 360 AIMD_INIT_VELOC zpe$end


text:
MathSciNet bibliographic data MR1049789 34K20 (58F32) Dormayer, P. The stability of special symmetric solutions of $\dot x(t)=\alpha f(x(t-1))$$\dot x(t)=\alpha f(x(t-1))$ with small amplitudes. Nonlinear Anal. 14 (1990), no. 8, 701–715. Article

For users without a MathSciNet license , Relay Station allows linking from MR numbers in online mathematical literature directly to electronic journals and original articles. Subscribers receive the added value of full MathSciNet reviews.


text:
# Thread: Simple Equity Division: Divorcing couple needs to equalize equity, debt of vehicles

1. Originally Posted by Denis
Clearly stated:
wife has $10,000 car, no loan hubby has$10,000 car, \$14,000 owing
Actually, it says clearly that the wife will get and the husband will get.

Hasn't happened, yet. The agreement is in progress.

There's also no wording that the husband has or will get the debt. Sure you didn't use to be an attorney?

Anyways, I have assumed that the given information is all that's needed to "equalize the equity and debt of the vehicles".

If we don't have all of the needed information, then it's possible they each end up in debt, after taking out multiple personal loans for legal expenses to continue extended warfare.

2. Originally Posted by mmm4444bot
If we don't have all of the needed information, then it's possible they each end up in debt, after taking out multiple personal loans for legal expenses to continue extended warfare.
Very likely outcome.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•


text:
# [NTG-context] sorting list

 Some things I do not understand about sorting:This is the example:\def\sortprocess#1{{\bf #1}}\definesorting[city][cities][\callupcities]\setupsorting[city][criterium=all,command=\sortprocess]\city{Londen}\city{Berlijn}\city{New York}\city{Parijs}\city{Amstelveen}\placelistofcities\callupcitiesquestion 1. The manual states (p.163) "When we add a command in the third argument during the definition of the sorted list we may recall sorted list with this command."However \callupcities gives me this error:Runaway argument?! Paragraph ended before \callupcities was complete.                    \par question 2. The command \sortprocess does work, the items are in bold. But they now are typeset next to one another instead of each one on a line by itself, as occurs without command=\sortprocess on the setup.Hans van der Meer
_______________________________________________
ntg-context mailing list
ntg-context@ntg.nl
http://www.ntg.nl/mailman/listinfo/ntg-context


text:
# How do you evaluate -7( 1- 10)?

Mar 13, 2017

$63$

#### Explanation:

Use PEMDAS to solve. Start inside the parentheses and subtract 10 from 1:

$1 - 10 = - 9$

Now multiply $- 9$ by $- 7$:

$- 7 \times - 9 = 63$


text:
## anonymous 5 years ago A 20-row theater has three sections of seating. In each section, the number of seats in a row increases by one with each successive row.The first row of the middle section has 10 seats.The first row of each of the two side sections has 4 seats. a. Find the total number of chairs in each section.Then find the total seating capacity of the theater. b. Write an arithmetic series to represent each section.

1. anonymous

I got 930

Yess I messed up

3. anonymous

for each of the end sections $\sum_{i=4}^{23}i$ for te middle section $\sum_{i=10}^{29}i$

4. anonymous

do you know the general form of the sum of an arithmetic sequence nicolenova

5. anonymous

yeah

6. anonymous

ok then you just need to compute those sums, multiply the end one by two to account for both sections and add them up.

7. anonymous

do you see where the sums come from?

8. anonymous

i don't really get the formulas

9. anonymous

ok we'll do the middle one. There are 10 rows to start, then the next has 11, then 12,... so the total seating is 10+11+12+13+... and we go until we have 20 terms. The 20th term will be 10+19=29 so we have $\sum_{i=10}^{29}i$

10. anonymous

the end sections are the same except starting with 4 in the first row and going to 23 in the 20th row.

11. anonymous

wait there isn't 10 rows, there's 20, and the first has 10 seats

12. anonymous

yeah there are 20 rows and 10 seats in the first. so we have 10 seats in the first row, 11 seats in the second row, 12 in the third,..., 29 in the 20th row. And we add all the seats together

13. anonymous

I hope i'm getting this right: 15+3n 15+3(20) =15+60 =75 I think its a small theater lol! it only has 75 seating capacity

14. anonymous

i dont think that is right ms bio. Just adding the first 8 rows of the middle section you have more than 75

15. anonymous

10+11+12+13+14+15+16+17>75

16. anonymous

yeah, Actually 75 is only the total seat in the 20th row.. hang on I think i'm getting it right now...heheheh

17. anonymous

k let me know if you get the same answer as me, I have 930 total seats

18. anonymous

yeah, the same! I used the arithmetic sequence: s=n/2 (2*first term+(n-1)d) n=20 first term is 18 d is 3 then you'll get 930

19. anonymous

I just solved the last row first...heheheh LOL

20. anonymous

good I'm glad it came out the same

21. anonymous

Yeah, that is one of the reasons I resorted to become a Bio major...I get so reckless in solving...heheheh

Find more explanations on OpenStudy


text:
# Question Paper from: IBPS RRB Clerk Prelims 2017

Statement: A = Y ≤ C > W

Conclusions:

I. C = A

II. C > A

1:
If only conclusion I is true.
2:
If only conclusion II Is true.
3:
If either conclusion I or II is true.
4:
Neither conclusion I nor II is true.
5:
Both conclusion I and II are true.


text:
## Found 7 Documents (Results 1–7)

100
MathJax

Full Text:

Full Text:

### Essential self-adjointness of Schrödinger-type operators on manifolds. (English. Russian original)Zbl 1052.58027

Russ. Math. Surv. 57, No. 4, 641-692 (2002); translation from Usp. Mat. Nauk 57, No. 4, 3-58 (2002).
Full Text:

### On the well-posedness in the sense of $$L_ 2$$-solution of the Cauchy problem for the nonstationary Schrödinger type equation. (English)Zbl 0862.34063

MSC:  34L40 35Q55

### Explosive growth of the magnetic energy in a turbulent medium. (English. Russian original)Zbl 0559.76113

Magnetohydrodynamics 19, 274-279 (1983); translation from Magn. Gidrodin. 1983, No. 3, 53-58 (1983).
MSC:  76W05 76F99

### Regularization of phase integrals near the top of a barrier. (Russian)Zbl 0513.70016

MSC:  70G99 81S40 81Q99

all top 5

all top 3


text:
# Tagged with #indel-realignment 1 documentation article | 0 announcements | 3 forum discussions

Created 2016-03-08 16:49:04 | Updated 2016-03-23 22:16:45 | Tags: indelrealigner realignertargetcreator indel-realignment

This tutorial replaces Tutorial#2800 and applies to data types within the scope of the GATK Best Practices variant discovery workflow.

We provide example data and example commands for performing local realignment around small insertions and deletions (indels) against a reference. The resulting BAM reduces false positive SNPs and represents indels parsimoniously. First we use RealignerTargetCreator to identify and create a target intervals list (step 1). Then we perform local realignment for the target intervals using IndelRealigner (step 2).

## 1. Introduction and tutorial materials

#### Why do indel realignment?

Local realignment around indels allows us to correct mapping errors made by genome aligners and make read alignments more consistent in regions that contain indels.

Genome aligners can only consider each read independently, and the scoring strategies they use to align reads relative to the reference limit their ability to align reads well in the presence of indels. Depending on the variant event and its relative location within a read, the aligner may favor alignments with mismatches or soft-clips instead of opening a gap in either the read or the reference sequence. In addition, the aligner's scoring scheme may use arbitrary tie-breaking, leading to different, non-parsimonious representations of the event in different reads.

In contrast, local realignment considers all reads spanning a given position. This makes it possible to achieve a high-scoring consensus that supports the presence of an indel event. It also produces a more parsimonious representation of the data in the region .

This two-step indel realignment process first identifies such regions where alignments may potentially be improved, then realigns the reads in these regions using a consensus model that takes all reads in the alignment context together.

#### Prerequisites

• Installed GATK tools
• Coordinate-sorted and indexed BAM alignment data
• Reference sequence, index and dictionary
• An optional VCF file representing population variants, subset for indels

• To download the reference, open ftp://gsapubftp-anonymous@ftp.broadinstitute.org/bundle/2.8/b37/ in your browser. Leave the password field blank. Download the following three files (~860 MB) to the same folder: human_g1k_v37_decoy.fasta.gz, .fasta.fai.gz, and .dict.gz. This same reference is available to load in IGV.
• Click tutorial_7156.tar.gz to download the tutorial data. The data is human paired 2x150 whole genome sequence reads originally aligning at ~30x depth of coverage. The sample is a PCR-free preparation of the NA12878 individual run on the HiSeq X platform. I took the reads aligning to a one Mbp genomic interval (10:96,000,000-97,000,000) and sanitized and realigned the reads (BWA-MEM -M) to the entire genome according to the workflow presented in Tutorial#6483 and marked duplicates using MarkDuplicates according to Tutorial#6747. We expect the alignment to reveal a good proportion of indels given its long reads (~150 bp per read), high complexity (PCR-free whole genome data) and deep coverage depth (30x).

Tutorial download also contains a known indels VCF from Phase 3 of the 1000 Genomes Project subset for indel-only records in the interval 10:96,000,000-97,000,000. These represent consensus common and low-frequency indels in the studied populations from multiple approaches. The individual represented by our snippet, NA12878, is part of the 1000 Genomes Project data. Because of the differences in technology and methods used by the Project versus our sample library, our library has potential to reveal additional variants.

## 2. Create target intervals list using RealignerTargetCreator

For simplicity, we use a single known indels VCF, included in the tutorial data. For recommended resources, see Article#1247.

In the command, RealignerTargetCreator takes a coordinate-sorted and indexed BAM and a VCF of known indels and creates a target intervals file.

java -jar GenomeAnalysisTK.jar \
-T RealignerTargetCreator \
-R human_g1k_v37_decoy.fasta \
-L 10:96000000-97000000 \
-known INDEL_chr10_1Mb_b37_1000G_phase3_v4_20130502.vcf \
-I 7156_snippet.bam \
-o 7156_realignertargetcreator.intervals

In the resulting file, 7156_realignertargetcreator.intervals, intervals represent sites of extant and potential indels. If sites are proximal, the tool represents them as a larger interval spanning the sites.

• We specify the BAM alignment file with -I.
• We specify the known indels VCF file with -known. The known indels VCF contains indel records only.
• Three input choices are technically feasible in creating a target intervals list: you may provide RealignerTargetCreator (i) one or more VCFs of known indels each passed in via -known, (ii) one or more alignment BAMs each passed in via -I or (iii) both. We recommend the last mode, and we use it in the example command. We use these same input files again in the realignment step.

The tool adds indel sites present in the known indels file and indel sites in the alignment CIGAR strings to the targets. Additionally, the tool considers the presence of mismatches and soft-clips, and adds regions that pass a concentration threshold to the target intervals.

If you create an intervals list using only the VCF, RealignerTargetCreator will add sites of indel only records even if SNPs are present in the file. If you create an intervals list using both alignment and known indels, the known indels VCF should contain only indels. See Related resources.

• We include -L 10:96000000-97000000 in the command to limit processing time. Otherwise, the tool traverses the entire reference genome and intervals outside these coordinates may be added given our example 7156_snippet.bam contains a small number of alignments outside this region.
• The tool samples to a target coverage of 1,000 for regions with greater coverage.

#### The target intervals file

The first ten rows of 7156_realignertargetcreator.intervals are as follows. The file is a text-based one-column list with one interval per row in 1-based coordinates. Header and column label are absent. For an interval derived from a known indel, the start position refers to the corresponding known variant. For example, for the first interval, we can zgrep -w 96000399 INDEL_chr10_1Mb_b37_1000G_phase3_v4_20130502.vcf for details on the 22bp deletion annotated at position 96000399.

10:96000399-96000421
10:96002035-96002036
10:96002573-96002577
10:96003556-96003558
10:96004176-96004177
10:96005264-96005304
10:96006455-96006461
10:96006871-96006872
10:96007627-96007628
10:96008204

To view intervals on IGV, convert the list to 0-based BED format using the following AWK command. The command saves a new text-based file with .bed extension where chromosome, start and end are tab-separated, and the start position is one less than that in the intervals list.

awk -F '[:-]' 'BEGIN { OFS = "\t" } { if( $3 == "") { print$1, $2-1,$2 } else { print $1,$2-1, 3}}' 7156_realignertargetcreator.intervals > 7156_realignertargetcreator.bed back to top ## 3. Realign reads using IndelRealigner In the following command, IndelRealigner takes a coordinate-sorted and indexed BAM and a target intervals file generated by RealignerTargetCreator. IndelRealigner then performs local realignment on reads coincident with the target intervals using consenses from indels present in the original alignment. java -Xmx8G -Djava.io.tmpdir=/tmp -jar GenomeAnalysisTK.jar \ -T IndelRealigner \ -R human_g1k_v37_decoy.fasta \ -targetIntervals 7156_realignertargetcreator.intervals \ -known INDEL_chr10_1Mb_b37_1000G_phase3_v4_20130502.vcf \ -I 7156_snippet.bam \ -o 7156_snippet_indelrealigner.bam The resulting coordinate-sorted and indexed BAM contains the same records as the original BAM but with changes to realigned records and their mates. Our tutorial's two IGV screenshots show realigned reads in two different loci. For simplicity, the screenshots show the subset of reads that realigned. For screenshots of full alignments for the same loci, see here and here. #### Comments on specific parameters • The -targetIntervals file from RealignerTargetCreator, with extension .intervals or .list, is required. See section 1 for a description. • Specify each BAM alignment file with -I. IndelRealigner operates on all reads simultaneously in files you provide it jointly. • Specify each optional known indels VCF file with -known. • For joint processing, e.g. for tumor-normal pairs, generate one output file for each input by specifying -nWayOut instead of -o. • By default, and in this command, IndelRealigner applies the USE_READS consensus model. This is the consensus model we recommend because it balances accuracy and performance. To specify a different model, use the -model argument. The KNOWNS_ONLY consensus model constructs alternative alignments from the reference sequence by incorporating any known indels at the site, the USE_READS model from indels in reads spanning the site and the USE_SW model additionally from Smith-Waterman alignment of reads that do not perfectly match the reference sequence. The KNOWNS_ONLY model can be sufficient for preparing data for base quality score recalibration. It can maximize performance at the expense of some accuracy. This is the case only given the known indels file represents common variants for your data. If you specify -model KNOWNS_ONLY but forget to provide a VCF, the command runs but the tool does not realign any reads. • If you encounter out of memory errors, try these options. First, increase max java heap size from -Xmx8G. To find a system's default maximum heap size, type java -XX:+PrintFlagsFinal -version, and look for MaxHeapSize. If this does not help, and you are jointly processing data, then try running indel realignment iteratively on smaller subsets of data before processing them jointly. • IndelRealigner performs local realignment without downsampling. If the number of reads in an interval exceeds the 20,000 default threshold set by the -maxReads parameter, then the tool skips the region. • The tool has two read filters, BadCigarFilter and MalformedReadFilter. The tool processes reads flagged as duplicate. #### Changes to alignment records For our example data,194 alignment records realign for ~89 sites. These records now have the OC tag to mark the original CIGAR string. We can use the OC tag to pull out realigned reads and instructions for this are in section 4. The following screenshot shows an example pair of records before and after indel realignment. We note seven changes with asterisks, blue for before and red for after, for both the realigned read and for its mate. Changes to the example realigned record: • MAPQ increases from 60 to 70. The tool increases each realigned record's MAPQ by ten. • The CIGAR string, now 72M20I55M4S, reflects the realignment containing a 20bp insertion. • The OC tag retains the original CIGAR string (OC:Z:110M2I22M1D13M4S) and replaces the MD tag that stored the string for mismatching positions. • The NM tag counts the realigned record's mismatches, and changes from 8 to 24. Changes to the realigned read's mate record: • The MC tag updates the mate CIGAR string (to MC:Z:72M20I55M4S). • The MQ tag updates to the new mapping quality of the mate (to MQ:i:70). • The UQ tag updates to reflect the new Phred likelihood of the segment, from UQ:i:100 to UQ:i:68. back to top ## 3. Some additional considerations RealignerTargetCreator documentation has a -maxInterval cutoff to drop intervals from the list if they are too large. This is because increases in number of reads per interval quadratically increase the compute required to realign a region, and larger intervals tend to include more reads. By the same reasoning, increasing read depth, e.g. with additional alignment files, increases required compute. Our tutorial's INDEL_chr10_1Mb_b37_1000G_phase3_v4_20130502.vcf contains 1168 indel-only records. The following are metrics on intervals created using the three available options.  #intervals avg length basepair coverage VCF only 1161 3.33 3,864 BAM only 487 15.22 7,412 VCF+BAM 1151 23.07 26,558  You can project the genomic coverage of the intervals as a function of the interval density (number of intervals per basepair) derived from varying the known indel density (number of indel records in the VCF). This in turn allows you to anticipate compute for indel realignment. The density of indel sites increases the interval length following a power law (y=ax^b). The constant (a) and the power (b) are different for intervals created with VCF only and with VCF+BAM. For our example data, these average interval lengths are well within the length of a read and minimally vary the reads per interval and thus the memory needed for indel realignment. back to top ## 4. Related resources • See the Best Practice Workflow and click on the flowchart's Realign Indels icon for best practice recommendations and links including to a 14-minute video overview. • See Article#1247 for guidance on using VCF(s) of known variant sites. • To subset realigned reads only into a valid BAM, as shown in the screenshots, use samtools view 7088_snippet_indelrealigner.bam | grep 'OC' | cut -f1 | sort > 7088_OC.txt to create a list of readnames. Then, follow direction in blogpost SAM flags down a boat on how to create a valid BAM using FilterSamReads. • See discussion on multithreading for options on speeding up these processes. The document titled How can I use parallelism to make GATK tools run faster? gives two charts: (i) the first table relates the three parallelism options to the major GATK tools and (ii) the second table provides recommended configurations for the tools. Briefly, RealignerTargetCreator runs faster with increasing -nt threads, while IndelRealigner shows diminishing returns for increases in scatter-gather threads provided by Queue. See blog How long does it take to run the GATK Best Practices? for a breakdown of the impact of threading and CPU utilization for Best Practice Workflow tools. • See DePristo et al's 2011 Nature Genetics technical report for benchmarked effects of indel realignment as well as for the mathematics behind the algorithms. • See Tutorial#6517 for instructions on creating a snippet of reads corresponding to a genomic interval. For your research aims, you may find testing a small interval of your alignment and your choice VCF, while adjusting parameters, before committing to processing your full dataset, is time well-invested. • The tutorial's PCR-free 2x150 bp reads give enough depth of coverage (34.67 mean and 99.6% above 15) and library complexity to allow us the confidence to use aligner-generated indels in realignment. Check alignment coverage with DepthofCoverage for WGS or DiagnoseTargets for WES. • See SelectVariants to subset out indel calls using the -selectType INDEL option. Note this excludes indels that are part of mixed variant sites (see FAQ). Current solutions to including indels from mixed sites involves the use of JEXL expressions, as discussed here. Current solutions to selecting variants based on population allelic frequency (AF), as we may desire to limit our known indels to those that are more common than rare for more efficient processing, are discussed in two forum posts (1,2). • See Tutorial#6491 for basic instructions on using the Integrative Genomics Viewer (IGV). No articles to display. Created 2016-05-21 01:11:18 | Updated | Tags: indel-realignment I came cross with the following error and it was suggested to be a potential bug: ##### ERROR ------------------------------------------------------------------------------------------ ##### ERROR stack trace java.lang.ExceptionInInitializerError at org.broadinstitute.sting.gatk.GenomeAnalysisEngine.(GenomeAnalysisEngine.java:167) at org.broadinstitute.sting.gatk.CommandLineExecutable.(CommandLineExecutable.java:57) at org.broadinstitute.sting.gatk.CommandLineGATK.(CommandLineGATK.java:66) at org.broadinstitute.sting.gatk.CommandLineGATK.main(CommandLineGATK.java:106) Caused by: java.lang.NullPointerException at org.reflections.Reflections.scan(Reflections.java:220) at org.reflections.Reflections.scan(Reflections.java:166) at org.reflections.Reflections.(Reflections.java:94) at org.broadinstitute.sting.utils.classloader.PluginManager.(PluginManager.java:79) ... 4 more ##### ERROR ------------------------------------------------------------------------------------------ ##### ERROR A GATK RUNTIME ERROR has occurred (version 3.1-1-g07a4bf8): ##### ERROR ##### ERROR This might be a bug. Please check the documentation guide to see if this is a known problem. ##### ERROR If not, please post the error message, with stack trace, to the GATK forum. ##### ERROR Visit our website and forum for extensive documentation and answers to ##### ERROR commonly asked questions http://www.broadinstitute.org/gatk ##### ERROR ##### ERROR MESSAGE: Code exception (see stack trace for error itself) My command used as follows: java -Xmx240g -Djava.io.tmpdir={TMPDIR} -jar /data004/software/GIF/packages/gatk/3.1-1/GenomeAnalysisTK.jar -I 2A_MD.bam -R /home/lwang/lwang/Zea_mays.AGPv3/Zea_mays.AGPv3.22.dna.genome.fa -T RealignerTargetCreator -o 2AforIndelRealigner.intervals

java -Xmx240g -Djava.io.tmpdir={TMPDIR} -jar /data004/software/GIF/packages/gatk/3.1-1/GenomeAnalysisTK.jar -I 2A_MD.bam -R /home/lwang/lwang/Zea_mays.AGPv3/Zea_mays.AGPv3.22.dna.genome.fa -T IndelRealigner -targetIntervals 2AforIndelRealigner.intervals -o 2A.IndelRealigned.bam Anyone has any idea? Any suggestion is appreciated. Created 2014-04-10 16:24:48 | Updated | Tags: indelrealigner realignertargetcreator bqsr knownsites mouse indel-realignment Hello, I was wondering about the format of the known site vcfs used by the RealignerTargetCreator and BaseRecalibrator walkers. I'm working with mouse whole genome sequence data, so I've been using the Sanger Mouse Genome project known sites from the Keane et al. 2011 Nature paper. From the output, it seems that the RealignerTargetCreator walker is able to recognise and use the gzipped vcf fine: INFO 15:12:09,747 HelpFormatter - -------------------------------------------------------------------------------- INFO 15:12:09,751 HelpFormatter - The Genome Analysis Toolkit (GATK) v2.5-2-gf57256b, Compiled 2013/05/01 09:27:02 INFO 15:12:09,751 HelpFormatter - Copyright (c) 2010 The Broad Institute INFO 15:12:09,752 HelpFormatter - For support and documentation go to http://www.broadinstitute.org/gatk INFO 15:12:09,758 HelpFormatter - Program Args: -T RealignerTargetCreator -R mm10.fa -I DUK01M.sorted.dedup.bam -known /tmp/mgp.v3.SNPs.indels/ftp-mouse.sanger.ac.uk/REL-1303-SNPs_Indels-GRCm38/mgp.v3.indels.rsIDdbSNPv137.vcf.gz -o DUK01M.indel.intervals.list INFO 15:12:09,758 HelpFormatter - Date/Time: 2014/03/25 15:12:09 INFO 15:12:09,758 HelpFormatter - -------------------------------------------------------------------------------- INFO 15:12:09,759 HelpFormatter - -------------------------------------------------------------------------------- INFO 15:12:09,918 ArgumentTypeDescriptor - Dynamically determined type of /fml/chones/tmp/mgp.v3.SNPs.indels/ftp-mouse.sanger.ac.uk/REL-1303-SNPs_Indels-GRCm38/mgp.v3.indels.rsIDdbSNPv137.vcf.gz to be VCF INFO 15:12:10,010 GenomeAnalysisEngine - Strictness is SILENT INFO 15:12:10,367 GenomeAnalysisEngine - Downsampling Settings: Method: BY_SAMPLE, Target Coverage: 1000 INFO 15:12:10,377 SAMDataSourceSAMReaders - Initializing SAMRecords in serial INFO 15:12:10,439 SAMDataSource\$SAMReaders - Done initializing BAM readers: total time 0.06 INFO 15:12:10,468 RMDTrackBuilder - Attempting to blindly load /fml/chones/tmp/mgp.v3.SNPs.indels/ftp-mouse.sanger.ac.uk/REL-1303-SNPs_Indels-GRCm38/mgp.v3.indels.rsIDdbSNPv137.vcf.gz as a tabix indexed file INFO 15:12:11,066 IndexDictionaryUtils - Track known doesn't have a sequence dictionary built in, skipping dictionary validation INFO 15:12:11,201 GenomeAnalysisEngine - Creating shard strategy for 1 BAM files INFO 15:12:12,333 GenomeAnalysisEngine - Done creating shard strategy INFO 15:12:12,334 ProgressMeter - [INITIALIZATION COMPLETE; STARTING PROCESSING]  I've checked the indel interval lists for my samples and they do all appear to contain different intervals.

However, when I use the equivalent SNP vcf in the following BQSR step, GATK errors as follows:

##### ERROR ------------------------------------------------------------------------------------------

##### ERROR ------------------------------------------------------------------------------------------

Which means that the SNP vcf (which has the same format as the indel vcf) is not used by BQSR.

My question is: given that the BQSR step failed, should I be worried that there are no errors from the Indel Realignment step? As the known SNP/indel vcfs are in the same format, I don't know whether I can trust the realigned .bams.

Thanks very much!

Created 2014-01-31 21:16:16 | Updated | Tags: knownsites dbsnp indel-realignment

Dear GATK team,

Would you please clarify that, based on your experience or the logic used in the realignment algorithm, which option between using dbSNP, 1K gold standard (mills...), or "no known dbase" might result in a more accurate set of indels in the Indel-based realignment stage (speed and efficiency is not my concern).

Based on the documentation I found on your site, the "known" variants are used to identify "intervals" of interest to then perform re-alignment around indels. So, it makes sense to me to use as many number of indels as possible (even if they are unreliable and garbage such as many of those found in dbSNP) in addition to those more accurate calls found in 1K gold-standard datasets for choosing the intervals. After all, that increases he number of indel regions to be investigated and therefore potentially increase the accuracy. Depending on your algorithm logic, also, it seems that providing no known dbase would increase the chance of investigating more candidates of mis-alignment and therefore improving the accuracy.

But if your logic uses the "known" indel sets to just "not" perform the realignment and ignore those candidates around known sites, it makes sense to use the more accurate set such as 1K gold standard.

Please let me know what you suggest.

Thank you Regards Amin Zia


text:
# Vector with minimal angle to a set of vectors

1. Oct 5, 2011

### Obelus

Let $\mathbb X$ be a set of mean-shifted vectors $\mathbf X_1, \mathbf X_2, \ldots, \mathbf X_k$ in $\mathbb R^n$. By mean-shifted, I mean that $\text{Mean}(\mathbf X_i) = 0$ $\forall i \in {0, \ldots, k}$. I want to find a vector $\mathbf T \in \mathbb R^n$ that maximizes the function

$f(\mathbf T) = \sum \limits_{\mathbf X \in \mathbb X} \big ( cos(\theta_{\mathbf X, \mathbf T}) \big )^2 = \sum \limits_{\mathbf X \in \mathbb X} \big ( \frac{\mathbf X \cdot \mathbf T}{||\mathbf X|| \cdot ||\mathbf T||} \big )^2$

(Edit: maximizing this $f$ does not actually get what I want. Instead, I want to maximize the geometric mean of the correlations - see my followup posts).

In other words, I want to find a vector $\mathbf T$ that has a small angle $\theta$ to each $\mathbf X \in \mathbb X$. (Actually there must be infinitely many solutions, since any linear transformation of $\mathbf T$ is also a solution).

My real motivation is statistical: this is equivalent to finding a vector that has a high Pearson correlation coefficient with all the vectors in $\mathbb X$.

I can use numerical algorithms to optimize $f$, but I would prefer to find a closed-form solution. This problem is part of a larger algorithm that I am trying to speed up, and it spends most of its time trying to find $T$. Is a closed-form solution possible? Or is this problem similar to an existing problem, which I can adapt?

If $k=2$, the solution should just be to rotate $\mathbf X_1$ halfway to $\mathbf X_2$, using some multidimensional rotation as discussed in http://forums.xkcd.com/viewtopic.php?f=17&t=29603". Perhaps this rotation concept could be extended to find the "rotational average" of $\mathbb X$, if that makes sense?

Any help towards finding a closed-form solution to this problem would be appreciated.

Last edited by a moderator: Apr 26, 2017
2. Oct 5, 2011

### Obelus

Actually, I just realized that $f$ in my previous post is not exactly what I want to maximize. I want $T$ to be equally and maximally close to all vectors in $\mathbb X$, so maximizing the minimum correlation with $T$ would be better:

$f = \displaystyle{\mathop{\mbox{min}}_{\mathbf X \in \mathbb X}} \big ( \frac{\mathbf X \cdot \ \mathbf T}{||\mathbf X|| \cdot ||\mathbf T||} \big )^2$

However, this makes $f$ non-differentiable, so perhaps using the http://mathoverflow.net/questions/35191/a-differentiable-approximation-to-the-minimum-function" [Broken] would work:

$f = \big ( \frac{1}{|\mathbb X|}\sum\limits_{\mathbf X \in \mathbb X} \frac{\mathbf X \cdot \ \mathbf T}{||\mathbf X|| \cdot ||\mathbf T||} \big )^{\frac{1}{k}}$

for $k \rightarrow - \infty$.

Last edited by a moderator: May 5, 2017
3. Oct 5, 2011

### Obelus

Argh, actually that's not what I want either. If one vector in $\mathbb X$ is very different from the others, it will pull $\mathbf T$ towards it too much. Instead, I think I want to maximize the geometric mean, or the limit as $k \rightarrow 0$ of the generalized mean.

Sorry I keep changing my mind. Basically, I want $\mathbf T$ to be a good angular approximation of all the vectors in $\mathbb X$.


text:
# Approximate largest (in quantity, not magnitude) eigenvalue and eigenvector of a matrix

I need to obtain an approximate expression for the eigenvector corresponding to the largest real eigenvalue of a matrix, as well as the largest eigenvalue. Note that I mean largest not in absolute value, but largest in real value. The matrix can be approximately diagonal in some cases, but not always.

I have tried perturbation theory but it is not working very well. Are there other approximation schemes for the eigenvalues and eigenvectors of a matrix that I can try?

• If you have a dominant (hopefully complex) eigenvalue, a good "working horse" is the power method (en.wikipedia.org/wiki/Power_iteration). Besides, in your title "in quantity, not magnitude" is not the best way to encompass at the same time the degree of variability of an eigenvalue (here considered in absolute value) and an eigenvector (defined up to a multiplicative constant). – Jean Marie Sep 21 '17 at 20:02
• @JeanMarie I need an approximate analytical expression, not a numerical algorithm. – becko Sep 21 '17 at 20:25
• Analytical expression with the coefficients of the matrix ? What (small !) size are your matrices ? – Jean Marie Sep 21 '17 at 20:54
• @JeanMarie I meant analytical in the same sense that perturbation theory gives you analytical formulas invovling the elements of the matrix.\ – becko Sep 21 '17 at 21:08
• All right but what is the usual size of your matrices ? – Jean Marie Sep 21 '17 at 21:09


text:
# Start a new discussion

## Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

## Site Tag Cloud

Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.

• CommentRowNumber1.
• CommentAuthorTobyBartels
• CommentTimeJun 18th 2010

I got tired of making unmatched links to topological locale (aka spatial locale, or locale with enough points), so I wrote a stub.

• CommentRowNumber2.
• CommentAuthorTobyBartels
• CommentTimeJun 18th 2010

Also locale of opens. Very stubby.

I think that I really only wrote these so that I could put in a bunch of redirects for each, and head off anybody else writing them with too few redirects. (^_^)

• CommentRowNumber3.
• CommentAuthorMike Shulman
• CommentTimeJun 18th 2010

I would be more inclined to call the page “spatial locale” – I’ve encountered that term much more often. Plus “topological” as an adjective usually means that we’ve put an extra topology on something, so a “topological locale” sounds like an internal locale in Top.

I’m also not really fond of calling it the “locale of opens” – I would talk about the frame of opens, but the locale is “of” the same things that the space was. E.g. the locale underlying the space of real numbers is the locale of real numbers, not the locale of open subsets of real numbers – the latter would be some sort of “hyperlocale” whose points are open sets.

• CommentRowNumber4.
• CommentAuthorTobyBartels
• CommentTimeJun 18th 2010

Plus “topological” as an adjective usually means that we’ve put an extra topology on something, so a “topological locale” sounds like an internal locale in Top.

Well, yeah, but the same is true of ‘spatial’. The term ‘topological’ here is acting in same way as ‘localic’ in ‘localic topos’. I don’t like ‘spatial’ because a locale is a kind of space anyway! (But spatial locale redirects, of course.) The term ‘topological’, however, is well established to mean a topological space in the sense of Bourbaki, as when (for example) one says that a convergence space is ‘topological’.

I’m also not really fond of calling it the “locale of opens” – I would talk about the frame of opens, but the locale is “of” the same things that the space was.

Gosh, you’re right! I was a little unhappy with that name on the grounds that every locale is a locale of opens; this is really just the locale of opens in a topological space. But it’s worse than that; every locale is really a locale of points! (Just like a topological space is a space of points.)

So what is the correct term here? For the locale I mean, not the frame. I suppose that one might say ‘topological locale’ (or ‘spatial locale’) again here, but what is one supposed to say when given a topological space $X$ and wanting to speak of the locale whose underlying frame is the frame of open subspaces of $X$? Somehow I have not picked up that terminology.

• CommentRowNumber5.
• CommentAuthorTobyBartels
• CommentTimeJun 19th 2010

OK, I’ve reworked topological locale and locale of opens into a new version of topological locale. This does not use the terminology ‘locale of opens at all’, but instead introduces the notation $\Omega(-)$ for the concept. I have also written frame of opens (which I made out of the old locale of opens, although that name now redirects to topological locale, since that is the page that discusses the concept that I had earlier had at the badly named page locale of opens). And I am writing space of points as well.

• CommentRowNumber6.
• CommentAuthorMike Shulman
• CommentTimeJun 19th 2010

the same is true of ‘spatial’.

Not to me. I’ve never heard people talk about, say, a “spatial group” or a “spatial category” with the same meanings as the established terms “topological group” and “topological category.” But I can live with “topological locale.”

I don’t know of a standard term for “the locale underlying a topological space.” I suppose if we identify spatial locales with sober spaces, as one might argue is not unreasonable, then it would be the same as the soberification, but that’d be misleading here.


text:
Propositions As Types : 1

One of my favorite mathematical tricks — it seems almost too tricky to be true — is the Propositions As Types Analogy.  And I see hints the 2-part analogy can be extended to a 3-part analogy, as follows.

$\text{proof hint : proof : proposition ~:~:~ untyped term : typed term : type}$