Generalize to a graph-theoretic formulation - Revision history

Jbd at 16:39, 25 May 2010

2010-05-25T16:39:20Z

← Older revision		Revision as of 09:39, 25 May 2010
Line 4:		Line 4:


	~~(General formulation)~~		Define a set of nodes <math>a_1, a_2, ...</math> with sets of directed edges <math>e_j = \left \{ e_{j}^1, e_{j}^2, ... \right \}</math> such that each set of edges (with corresponding nodes) forms an acyclic path.
	Define a set of nodes <math>a_1, a_2, ...</math> with k sets of directed edges <math>e_j = \left \{ e_{j}^1, e_{j}^2, ... \right \}</math> ~~(for <math> 1 \leq j \leq k</math>)~~ such that each set of edges (with corresponding nodes) forms an acyclic path.

	Give each node a value of 1 or -1. Consider any traversal corresponding to a set <math>e_j</math> that starts at the root node; define the absolute value of the sum of the values of the nodes visited to be <math>t_j</math>.		Give each node a value of 1 or -1. Consider any traversal corresponding to a set <math>e_j</math> that starts at the root node; define the absolute value of the sum of the values of the nodes visited to be <math>t_j</math>.

	Possible conditions ~~given a set of nodes <math>a_1, a_2, ... </math> (or the finitary case <math>a_1, a_2, ... a_n</math>)~~:		Possible conditions:

	No subsets (NS): No set of edges is a subset of another set.		No subsets (NS): No set of edges is a subset of another set.

	Omega set (OS): One set of edges connects <math>a_i</math> to <math>a_i+1</math> for all i ~~(or in the finitary case, all i from 1 to n-1)~~.		Omega set (OS): One set of edges connects <math>a_i</math> to <math>a_i+1</math> for all i.

	Always increasing (AI): For any edge from <math>a_i</math> to <math>a_j</math>, i is less than j.		Always increasing (AI): For any edge from <math>a_i</math> to <math>a_j</math>, i is less than j.

	Isolated roots (IR): Each node can be the root node of only one set of edges. ~~[This condition is needed for the definition of completely multiplicative.]~~		Isolated roots (IR): Each node can be the root node of only one set of edges.


Line 24:		Line 23:
	Define an infinite set of nodes <math>a_1, a_2, ...</math> such that given a node <math>a_r</math> there is a edge in the set <math>e_r</math> from <math>a_r(n)</math> to <math>a_r(n+1)</math> for all <math>n \in \mathbb{N}</math>.		Define an infinite set of nodes <math>a_1, a_2, ...</math> such that given a node <math>a_r</math> there is a edge in the set <math>e_r</math> from <math>a_r(n)</math> to <math>a_r(n+1)</math> for all <math>n \in \mathbb{N}</math>.

	Asking if there is some fixed C that <math>t_j</math> is always bounded by is equivalent to ~~our problem~~.		Asking if there is some fixed C that <math>t_j</math> is always bounded by is equivalent to the EDP.

	---		---

Jbd at 15:12, 25 May 2010

2010-05-25T15:12:09Z

← Older revision		Revision as of 08:12, 25 May 2010
Line 5:		Line 5:

	(General formulation)		(General formulation)
	Define a set of nodes <math>a_1, a_2, ...</math> with k sets of directed edges <math>e_{1}^j, e_{2}^j, ...</math> (for <math> 1 \leq j \leq k</math>) such that each set of edges (with corresponding nodes) forms an acyclic path.		Define a set of nodes <math>a_1, a_2, ...</math> with k sets of directed edges <math>e_j = \left \{ e_{j}^1, e_{j}^2, ... \right \}</math> (for <math> 1 \leq j \leq k</math>) such that each set of edges (with corresponding nodes) forms an acyclic path.

	Give each node a value of 1 or -1. Consider any traversal corresponding to a set <math>~~e_{1}^j, e_{2}^j, ...~~</math> that starts at the root node; define the absolute value of the sum of the values of the nodes visited to be <math>t_j</math>.		Give each node a value of 1 or -1. Consider any traversal corresponding to a set <math>e_j</math> that starts at the root node; define the absolute value of the sum of the values of the nodes visited to be <math>t_j</math>.

	Possible conditions given a set of nodes <math>a_1, a_2, ..., a_n</math>:		Possible conditions given a set of nodes <math>a_1, a_2, ... </math> (or the finitary case <math>a_1, a_2, ... a_n</math>):

	No subsets (NS): No set of edges is a subset of another set.		No subsets (NS): No set of edges is a subset of another set.

	Omega set (OS): One set of edges connects <math>a_i</math> to <math>a_i+1</math> for all i from 1 to n-1.		Omega set (OS): One set of edges connects <math>a_i</math> to <math>a_i+1</math> for all i (or in the finitary case, all i from 1 to n-1).

	Always increasing (AI): For any edge from <math>a_i</math> to <math>a_j</math>, i is less than j.		Always increasing (AI): For any edge from <math>a_i</math> to <math>a_j</math>, i is less than j.

	Isolated roots (IR): Each node can be the root node of only one ~~labelled~~ set of ~~directed~~ edges. [This condition is needed for the definition of completely multiplicative.]		Isolated roots (IR): Each node can be the root node of only one set of edges. [This condition is needed for the definition of completely multiplicative.]


	---		---

	Define an infinite set of nodes <math>a_1, a_2, ...</math> such that given a node <math>~~a_i~~</math> there is a ~~directed~~ edge ~~labelled~~ <math>i</math> from <math>~~a_i~~(n)</math> to <math>~~a_i~~(n+1)</math> for all <math>n \in \mathbb{N}</math>.		Define an infinite set of nodes <math>a_1, a_2, ...</math> such that given a node <math>a_r</math> there is a edge in the set <math>e_r</math> from <math>a_r(n)</math> to <math>a_r(n+1)</math> for all <math>n \in \mathbb{N}</math>.

	~~Give each node a value 1 or -1. Consider a traversal starting at a node moving along edges with the same label a finite number of times; then the discrepancy of a given traversal~~ is ~~the absolute value of the sum of all nodes visited. If we only allow traversals to start at the root node of a particular set of labelled edges, asking if it~~ is ~~possible for the discrepancy to be~~ bounded is equivalent to our problem.		Asking if there is some fixed C that <math>t_j</math> is always bounded by is equivalent to our problem.

	~~The graph doesn’t have to follow the number system. Have a set of nodes (finite or infinite) such that there are labelled directed edges, but allow the edges to be arbitrary~~.

	---		---

Jbd at 14:55, 25 May 2010

2010-05-25T14:55:04Z

← Older revision		Revision as of 07:55, 25 May 2010
Line 13:		Line 13:
	No subsets (NS): No set of edges is a subset of another set.		No subsets (NS): No set of edges is a subset of another set.

	Omega set (OS): One ~~labelled~~ set of edges connects <math>a_i</math> to <math>a_i+1</math> for all i from 1 to n-1.		Omega set (OS): One set of edges connects <math>a_i</math> to <math>a_i+1</math> for all i from 1 to n-1.

	Always increasing (AI): For any edge from <math>a_i</math> to <math>a_j</math>, i is less than j.		Always increasing (AI): For any edge from <math>a_i</math> to <math>a_j</math>, i is less than j.

Jbd at 14:23, 25 May 2010

2010-05-25T14:23:48Z

← Older revision		Revision as of 07:23, 25 May 2010
Line 15:		Line 15:
	Omega set (OS): One labelled set of edges connects <math>a_i</math> to <math>a_i+1</math> for all i from 1 to n-1.		Omega set (OS): One labelled set of edges connects <math>a_i</math> to <math>a_i+1</math> for all i from 1 to n-1.

	~~(Needs OS)~~ Always increasing (AI): For any edge from <math>a_i</math> to <math>a_j</math>, i is less than j.		Always increasing (AI): For any edge from <math>a_i</math> to <math>a_j</math>, i is less than j.

	Isolated roots (IR): Each node can be the root node of only one labelled set of directed edges. [This condition is needed for the definition of completely multiplicative.]		Isolated roots (IR): Each node can be the root node of only one labelled set of directed edges. [This condition is needed for the definition of completely multiplicative.]

Jbd at 16:39, 11 May 2010

2010-05-11T16:39:33Z

← Older revision		Revision as of 09:39, 11 May 2010
Line 3:		Line 3:
	---		---

	Define an infinite set of nodes <math>a_1, a_2, ...</math> such that given a node <math>a_i</math> there is a directed edge labelled <math>i</math> from <math>a_i(n)</math> to <math>a_i(n+1)</math> for all <math>n \in \mathbb{N}</math>.

	Give each node a value 1 or -1. Consider a traversal starting at a node moving along edges with the same label a finite number of times; then the discrepancy of a given traversal is the absolute value of the sum of all nodes visited. If we only allow traversals to start at the root node of a particular set of labelled edges, asking if it is possible for the discrepancy to be bounded is equivalent to our problem.

	~~The graph doesn’t have to follow the number system. Have a set of nodes (finite or infinite) such that there are labelled directed edges, but allow the edges to be arbitrary.~~

	(General formulation)		(General formulation)
Line 16:		Line 11:
	Possible conditions given a set of nodes <math>a_1, a_2, ..., a_n</math>:		Possible conditions given a set of nodes <math>a_1, a_2, ..., a_n</math>:

	No ~~arbitrary start points~~: No set of edges is a subset of another set.		No subsets (NS): No set of edges is a subset of another set.

			Omega set (OS): One labelled set of edges connects <math>a_i</math> to <math>a_i+1</math> for all i from 1 to n-1.

			(Needs OS) Always increasing (AI): For any edge from <math>a_i</math> to <math>a_j</math>, i is less than j.

			Isolated roots (IR): Each node can be the root node of only one labelled set of directed edges. [This condition is needed for the definition of completely multiplicative.]


	~~Omega set: One labelled set of edges connects <math>a_i</math> to <math>a_i+1</math> for all i from 1 to n~~-1.		---

	~~(Needs omega~~ set~~) No reverses: For any~~ edge from <math>a_i</math> to <math>~~a_j~~</math>~~, i is less than j~~.		Define an infinite set of nodes <math>a_1, a_2, ...</math> such that given a node <math>a_i</math> there is a directed edge labelled <math>i</math> from <math>a_i(n)</math> to <math>a_i(n+1)</math> for all <math>n \in \mathbb{N}</math>.

	~~One root per~~ node~~: Each~~ node ~~can be~~ the root node of ~~only one labelled~~ set of ~~directed~~ edges~~. [This condition~~ is ~~needed~~ for the ~~definition of completely multiplicative~~.]		Give each node a value 1 or -1. Consider a traversal starting at a node moving along edges with the same label a finite number of times; then the discrepancy of a given traversal is the absolute value of the sum of all nodes visited. If we only allow traversals to start at the root node of a particular set of labelled edges, asking if it is possible for the discrepancy to be bounded is equivalent to our problem.

	~~Should any~~ of the ~~other conditions~~ be ~~built into the main definition?~~		The graph doesn’t have to follow the number system. Have a set of nodes (finite or infinite) such that there are labelled directed edges, but allow the edges to be arbitrary.

	---		---

Jbd at 22:23, 7 May 2010

2010-05-07T22:23:06Z

← Older revision		Revision as of 15:23, 7 May 2010
Line 14:		Line 14:
	Give each node a value of 1 or -1. Consider any traversal corresponding to a set <math>e_{1}^j, e_{2}^j, ...</math> that starts at the root node; define the absolute value of the sum of the values of the nodes visited to be <math>t_j</math>.		Give each node a value of 1 or -1. Consider any traversal corresponding to a set <math>e_{1}^j, e_{2}^j, ...</math> that starts at the root node; define the absolute value of the sum of the values of the nodes visited to be <math>t_j</math>.

	~~Necessary condition?: No~~ set of ~~edges is a subset of another set~~.		Possible conditions given a set of nodes <math>a_1, a_2, ..., a_n</math>:

	~~---~~		No arbitrary start points: No set of edges is a subset of another set.

	~~While it’s fun~~ to ~~think about the completely general version of the structure (for example, cycles of odd degree cause unbounded discrepancy),~~ for ~~the sake of the original problem it might be useful~~ to ~~set some conditions~~.		Omega set: One labelled set of edges connects <math>a_i</math> to <math>a_i+1</math> for all i from 1 to n-1.

	~~Given a~~ set ~~of nodes~~ <math>~~a_1, a_2, ..., a_n~~</math>:		(Needs omega set) No reverses: For any edge from <math>a_i</math> to <math>a_j</math>, i is less than j.

	1. One labelled set of edges ~~connects <math>a_i</math> to <math>a_i+1</math>~~ for ~~all i from 1 to n-1~~.		One root per node: Each node can be the root node of only one labelled set of directed edges. [This condition is needed for the definition of completely multiplicative.]

	~~2. For~~ any ~~edge from <math>a_i</math> to <math>a_j</math>, i is less than j.~~		Should any of the other conditions be built into the main definition?

	~~3. Given a set consisting~~ of ~~all labelled edges of a given label, any traversal starting from~~ the ~~root node of~~ the ~~set can traverse the entire set of edges.~~

	~~4. No set of edges is a subset of another set (this prevents having arbitrary start points).~~

	~~5. (Optional, but required for a~~ definition ~~of completely multiplicative) Each node can be the root node of only one labelled set of directed edges.~~

	---		---

Jbd at 16:40, 7 May 2010

2010-05-07T16:40:54Z

← Older revision		Revision as of 09:40, 7 May 2010
Line 8:		Line 8:

	The graph doesn’t have to follow the number system. Have a set of nodes (finite or infinite) such that there are labelled directed edges, but allow the edges to be arbitrary.		The graph doesn’t have to follow the number system. Have a set of nodes (finite or infinite) such that there are labelled directed edges, but allow the edges to be arbitrary.

			(General formulation)
			Define a set of nodes <math>a_1, a_2, ...</math> with k sets of directed edges <math>e_{1}^j, e_{2}^j, ...</math> (for <math> 1 \leq j \leq k</math>) such that each set of edges (with corresponding nodes) forms an acyclic path.

			Give each node a value of 1 or -1. Consider any traversal corresponding to a set <math>e_{1}^j, e_{2}^j, ...</math> that starts at the root node; define the absolute value of the sum of the values of the nodes visited to be <math>t_j</math>.

			Necessary condition?: No set of edges is a subset of another set.

	---		---

Jbd at 16:40, 23 April 2010

2010-04-23T16:40:28Z

← Older revision		Revision as of 09:40, 23 April 2010
Line 7:		Line 7:
	Give each node a value 1 or -1. Consider a traversal starting at a node moving along edges with the same label a finite number of times; then the discrepancy of a given traversal is the absolute value of the sum of all nodes visited. If we only allow traversals to start at the root node of a particular set of labelled edges, asking if it is possible for the discrepancy to be bounded is equivalent to our problem.		Give each node a value 1 or -1. Consider a traversal starting at a node moving along edges with the same label a finite number of times; then the discrepancy of a given traversal is the absolute value of the sum of all nodes visited. If we only allow traversals to start at the root node of a particular set of labelled edges, asking if it is possible for the discrepancy to be bounded is equivalent to our problem.

	The graph doesn’t have to follow the number system. Have a set of nodes (finite or infinite) such that there are labelled directed edges, but allow the edges to be arbitrary. ~~Then there are interesting questions like;~~		The graph doesn’t have to follow the number system. Have a set of nodes (finite or infinite) such that there are labelled directed edges, but allow the edges to be arbitrary.

	---		---

Jbd at 16:35, 23 April 2010

2010-04-23T16:35:02Z

← Older revision		Revision as of 09:35, 23 April 2010
Line 59:		Line 59:
	Potential questions: Given a discrepancy d, what is a minimal graph (in terms of nodes and/or edges) where the discrepancy is greater than d? What conditions cause the discrepancy to “break”?		Potential questions: Given a discrepancy d, what is a minimal graph (in terms of nodes and/or edges) where the discrepancy is greater than d? What conditions cause the discrepancy to “break”?

	Using ~~all 5~~ conditions, the minimal set of nodes where the discrepancy must be greater than 1 is 4.		Using conditions 1-4, the minimal set of nodes where the discrepancy must be greater than 1 is 4.

	Proof: Consider every possible set of edges using 3 nodes.		Proof: Consider every possible set of edges using 3 nodes.

Jbd at 16:34, 23 April 2010

2010-04-23T16:34:10Z

← Older revision		Revision as of 09:34, 23 April 2010
Line 23:		Line 23:
	4. No set of edges is a subset of another set (this prevents having arbitrary start points).		4. No set of edges is a subset of another set (this prevents having arbitrary start points).

	5. Each node can be the root node of only one labelled set of directed edges.		5. (Optional, but required for a definition of completely multiplicative) Each node can be the root node of only one labelled set of directed edges.

	---		---