Strong product of graphs: Difference between revisions

From formulasearchengine
Jump to navigation Jump to search
Newer edit →
No edit summary
 
en>Spj.jordan
corrected definition. Previous version incorrectly implied every vertex in product has self-loop.
Line 1: Line 1:
Hi  free [http://www.skullrocker.com/blogs/post/10991 online psychic] tarot card readings; [http://myfusionprofits.com/groups/find-out-about-self-improvement-tips-here/ http://myfusionprofits.com/], there. My title is Sophia Meagher although it is not the title on my birth certificate. For a whilst I've been in Alaska but I will have to move in a yr or two. Credit authorising is how she tends to make a residing. My spouse doesn't like it the way I do but what I truly like performing is caving but I don't have the time recently.<br><br>my web blog; are psychics real ([http://www.aseandate.com/index.php?m=member_profile&p=profile&id=13352970 www.aseandate.com])
'''Discrepancy of hypergraphs''' is an area of [[discrepancy theory]].
 
== Hypergraph discrepancies in two colors ==
 
In the classical setting, we aim at partitioning the [[Vertex (graph theory)|vertices]] of a [[hypergraph]] into two classes in such a way that ideally each hyperedge contains the same number of vertices in both classes. A partition into two classes can be represented by a coloring <math>\chi \rightarrow \{-1, +1\}</math>. We call -1 and +1 ''colors''. The color-classes <math>\chi^{-1}(-1)</math> and <math>\chi^{-1}(+1)</math> form the corresponding partition. For a hyperedge <math>E \in \mathcal{E}</math>, set
:<math>\chi(E) := \sum_{v\in E} \chi(v).</math>
The ''discrepancy of <math>\mathcal{H}</math> with respect to <math>\chi</math>'' and the ''discrepancy of <math>\mathcal{H}</math>'' are defined by
:<math>disc(\mathcal{H},\chi) := \max_{E \in \mathcal{E}} |\chi(E)|,</math>
:<math>disc(\mathcal{H}) := \min_{\chi:V\rightarrow\{-1,+1\}} disc(\mathcal{H}, \chi).</math>
These notions as well as the term 'discrepancy' seem to have appeared for the first time in a paper of [[József Beck|Beck]].<ref name="beck_roth_estimate">J. Beck: "Roth's estimate of the discrepancy of integer sequences is nearly sharp", page 319-325. [[Combinatorica]], 1, 1981</ref> Earlier results on this problem include the famous lower bound on the discrepancy of arithmetic progressions by Roth<ref>K. F. Roth: "Remark concerning integer sequences", pages 257–260. Acta Arithmetica 9, 1964</ref> and upper bounds for this problem and other results by [[Paul Erdős|Erdős]] and Spencer<ref>J. Spencer: "A remark on coloring integers", pages 43–44. Canad. Math. Bull. 15, 1972.</ref><ref>P. Erdős and J. Spencer: "Imbalances in k-colorations", pages 379–385. Networks 1, 1972.</ref> and Sárközi (described on p.&nbsp;39 <ref>P. Erdős and J. Spencer: "Probabilistic Methods in Combinatorics." Akadémia Kiadó, Budapest, 1974.</ref>). At that time, discrepancy problems were called quasi-[[Ramsey theory|Ramsey]] problems.
 
To get some intuition for this concept, let's have a look at a few examples.
 
* If all edges of <math>\mathcal{H}</math> intersect trivially, i.e. <math>E_1 \cap E_2 = \emptyset</math> for any two distinct edges <math>E_1, E_2 \in \mathcal{E}</math>, then the discrepancy is zero, if all edges have even cardinality, and one, if there is an odd cardinality edge.
* The other extreme is marked by the ''complete hypergraph'' <math>(V, 2^V)</math>. In this case the discrepancy is <math>\lceil \frac{1}{2} |V|\rceil</math>. Any 2-coloring will have a color class of at least this size, and this set is also an edge. On the other hand, any coloring <math>\chi</math> with color classes of size <math>\lceil \frac{1}{2} |V|\rceil</math> and <math>\lfloor \frac{1}{2} |V|\rfloor</math> proves that the discrepancy is not larger than <math>\lceil \frac{1}{2} |V|\rceil</math>. It seems that the discrepancy reflects how chaotic the hyperedges of <math>\mathcal{H}</math> intersect. Things are not that easy, however, as the following example shows.
* Set <math>n=4k</math>, <math>k \in \mathcal{N}</math> and <math>\mathcal{H}_n = ([n], \{E \subseteq [n] \mid | E \cap [2k]| = | E \setminus [2k]|\})</math>. Now <math>\mathcal{H}_n</math> has many (more than <math>\binom{n/2}{n/4}^2 = \Theta(\frac 1 n 2^n)</math>) complicatedly intersecting edges, but discrepancy zero.
 
The last example shows that we cannot expect to determine the discrepancy by looking at a single parameter like the number of hyperedges. Still, the size of the hypergraph yields first upper bounds.
 
== Theorems ==
 
* <math>disc(\mathcal{H}) \leq \sqrt{2n \ln (2m)}.</math>
with n the number of vertices and m the number of edges.
 
The proof is a simple application of the probabilistic method:
Let <math>\chi:V \rightarrow \{-1,1\}</math> be a random coloring, i.e. we have
:<math>\Pr(\chi(v) = -1) = \Pr(\chi(v) = 1) = \frac{1}{2}</math>
independently for all <math>v \in V</math>. Since <math>\chi(E) = \sum_{v \in E} \chi(v)</math> is a sum of independent -1, 1 random variables. So we have <math>\Pr(|\chi(E)|>\lambda)<2 \exp(-\lambda^2/(2n))</math> for all <math>E \subseteq V</math> and <math>\lambda \geq 0</math>. Put <math>\lambda = \sqrt{2n \ln (2m)}</math> for convenience. Then
:<math>\Pr(disc(\mathcal{H},\chi)> \lambda) \leq \sum_{E \in \mathcal{E}} \Pr(|\chi(E)| > \lambda) < 1.</math>
Since a random coloring with positive probability has discrepancy at most <math>\lambda</math>, in particular, there are colorings that have discrepancy at most <math>\lambda</math>. Hence <math>disc(\mathcal{H}) \leq \lambda. \  \Box</math>
 
* ''For any hypergraph <math>\mathcal{H}</math> such that <math>m \geq n</math> we have <math>disc(\mathcal{H}) = O(\sqrt{n}).</math>''
 
To prove this, a much more sophisticated approach using the entropy function was necessary.
Of course this particularly interesting for <math>m = O(n)</math>. In the case <math>m=n</math>, <math>disc(\mathcal{H}) \leq 6 \sqrt{n}</math> can be shown for n large enough. Therefore, this result is usually known to as 'Six Standard Deviations Suffice'. It is considered to be one of the milestones of discrepancy theory.  The entropy method has seen numerous other applications, e.g. in the proof of the tight upper bound for the arithmetic progressions of [[Jiří Matoušek (mathematician)|Matoušek]] and Spencer<ref>J. Matoušek and J. Spencer: "Discrepancy in arithmetic progressions", pages 195–204. J. Amer. Math. Soc. 9, 1996.</ref> or the upper bound in terms of the primal shatter function due to Matoušek.<ref>J. Matoušek: "Tight upper bound for the discrepancy of half-spaces", pages 593–601. Discrepancy and Computational Geometry 13, 1995.</ref>
 
* ''Assume that each vertex of <math>\mathcal{H}</math> is contained in at most t edges. Then''
:<math>disc(\mathcal{H}) < 2t</math>
 
This beautiful result is due to Beck and Fiala.<ref>J. Beck and T. Fiala: "Integer making theorems", pages 1–8. Discrete Applied Mathematics 3, 1981.</ref> They bound the discrepancy by the maximum degree of <math>\mathcal{H}</math>.
It is a famous open problem whether this bound can be improved asymptotically (modified versions of the original proof give ''2t-1'' or even ''2t-3''). Beck and Fiala conjectured that <math>disc(\mathcal{H}) = O(\sqrt t)</math>, but little progress has been made so far in this direction. Bednarchak and Helm<ref>D. Bednarchak and M. Helm: "A note on the Beck-Fiala theorem", pages 147–149. Combinatorica 17, 1997.</ref> and Helm<ref>M. Helm: "On the Beck-Fiala theorem", page 207.  Discrete Mathematics 207, 1999.</ref> improved the Beck-Fiala bound in tiny steps to <math>disc(\mathcal{H}) \leq 2t - 3</math> (for a slightly restricted situation, i.e. <math> t \geq 3 </math>). A corollary of Beck's paper<ref name="beck_roth_estimate"/> – the first time the notion of discrepancy explicitly appeared – shows <math>disc(\mathcal{H}) \leq C \sqrt{t \log m} \log n</math> for some constant C. The latest improvement in this direction is due to Banaszczyk:<ref>W. Banaszczyk: "Balancing vectors and Gaussian measure of n-dimensional convex bodies", pages 351–360. Random Structures and Algorithms 12, 1998.</ref> <math>disc(\mathcal{H}) = O(\sqrt{t \log n})</math>.
 
=== Classic theorems ===
 
* Axis-parallel rectangles in the plane ([[Klaus Roth|Roth]], Schmidt)
* Discrepancy of half-planes (Alexander, Matoušek)
* Arithmetic progressions (Roth, Sárközy, [[Jozsef Beck|Beck]], Matoušek & [[Joel Spencer|Spencer]])
* Beck-Fiala theorem
* Six Standard Deviations Suffice (Spencer)
 
== Major open problems ==
 
* Axis-parallel rectangles in dimensions three and higher (Folklore)
* Komlos conjecture
* Homogeneous arithmetic progressions ([[Paul Erdős|Erdős]], $500)
 
== Applications ==
 
* Numerical Integration: Monte Carlo methods in high dimensions.
* Computational Geometry: [[Divide and conquer algorithms]].
* Image Processing: Halftoning
 
== Notes ==
 
<references/>
 
== References ==
 
* {{Cite thesis |degree=[[Habilitation]]|title=Integral Approximation|url=http://www.mpi-inf.mpg.de/~doerr/papers/habil.pdf |last=Doerr|first=Benjamin|year=2005|publisher=[[University of Kiel]]|accessdate=April 28, 2010|oclc= 255383176}}
* {{cite book|title=Irregularities of Distribution|last1=Beck|first1=József|author1-link=József Beck|last2=Chen|first2=William W. L.|publisher=Cambridge University Press|year=2009|ISBN=0-521-09300-7}}
* {{cite book|title=Geometric Discrepancy: An Illustrated Guide|last= Matoušek|first= Jiří|author-link=Jiří Matoušek (mathematician)|publisher=Springer|year=1999|ISBN= 3-540-65528-X}}
* {{cite book|title=The Discrepancy Method: Randomness and Complexity|last=Chazelle|first=Bernard|author-link=Bernard Chazelle|publisher=Cambridge University Press|year=2000|ISBN=0-521-77093-9}}
 
{{DEFAULTSORT:Discrepancy Of Hypergraphs}}
[[Category:Diophantine approximation]]
[[Category:Unsolved problems in mathematics]]

Revision as of 21:45, 15 November 2013

Discrepancy of hypergraphs is an area of discrepancy theory.

Hypergraph discrepancies in two colors

In the classical setting, we aim at partitioning the vertices of a hypergraph into two classes in such a way that ideally each hyperedge contains the same number of vertices in both classes. A partition into two classes can be represented by a coloring χ→{−1,+1}. We call -1 and +1 colors. The color-classes χ−1(−1) and χ−1(+1) form the corresponding partition. For a hyperedge E∈ℰ, set

χ(E):=∑v∈Eχ(v).

The discrepancy of ℋ with respect to χ and the discrepancy of ℋ are defined by

disc(ℋ,χ):=maxE∈ℰ|χ(E)|,
disc(ℋ):=minχ:V→{−1,+1}disc(ℋ,χ).

These notions as well as the term 'discrepancy' seem to have appeared for the first time in a paper of Beck.[1] Earlier results on this problem include the famous lower bound on the discrepancy of arithmetic progressions by Roth[2] and upper bounds for this problem and other results by Erdős and Spencer[3][4] and Sárközi (described on p. 39 [5]). At that time, discrepancy problems were called quasi-Ramsey problems.

To get some intuition for this concept, let's have a look at a few examples.

  • If all edges of ℋ intersect trivially, i.e. E1∩E2=∅ for any two distinct edges E1,E2∈ℰ, then the discrepancy is zero, if all edges have even cardinality, and one, if there is an odd cardinality edge.
  • The other extreme is marked by the complete hypergraph (V,2V). In this case the discrepancy is ⌈12|V|⌉. Any 2-coloring will have a color class of at least this size, and this set is also an edge. On the other hand, any coloring χ with color classes of size ⌈12|V|⌉ and ⌊12|V|⌋ proves that the discrepancy is not larger than ⌈12|V|⌉. It seems that the discrepancy reflects how chaotic the hyperedges of ℋ intersect. Things are not that easy, however, as the following example shows.
  • Set n=4k, k∈𝒩 and ℋn=([n],{E⊆[n]∣|E∩[2k]|=|E∖[2k]|}). Now ℋn has many (more than (n/2n/4)2=Θ(1n2n)) complicatedly intersecting edges, but discrepancy zero.

The last example shows that we cannot expect to determine the discrepancy by looking at a single parameter like the number of hyperedges. Still, the size of the hypergraph yields first upper bounds.

Theorems

with n the number of vertices and m the number of edges.

The proof is a simple application of the probabilistic method: Let χ:V→{−1,1} be a random coloring, i.e. we have

Pr⁡(χ(v)=−1)=Pr⁡(χ(v)=1)=12

independently for all v∈V. Since χ(E)=∑v∈Eχ(v) is a sum of independent -1, 1 random variables. So we have Pr⁡(|χ(E)|>λ)<2exp⁡(−λ2/(2n)) for all E⊆V and λ≥0. Put λ=2nln⁡(2m) for convenience. Then

Pr⁡(disc(ℋ,χ)>λ)≤∑E∈ℰPr⁡(|χ(E)|>λ)<1.

Since a random coloring with positive probability has discrepancy at most λ, in particular, there are colorings that have discrepancy at most λ. Hence disc(ℋ)≤λ.◻

To prove this, a much more sophisticated approach using the entropy function was necessary. Of course this particularly interesting for m=O(n). In the case m=n, disc(ℋ)≤6n can be shown for n large enough. Therefore, this result is usually known to as 'Six Standard Deviations Suffice'. It is considered to be one of the milestones of discrepancy theory. The entropy method has seen numerous other applications, e.g. in the proof of the tight upper bound for the arithmetic progressions of Matoušek and Spencer[6] or the upper bound in terms of the primal shatter function due to Matoušek.[7]

  • Assume that each vertex of ℋ is contained in at most t edges. Then
disc(ℋ)<2t

This beautiful result is due to Beck and Fiala.[8] They bound the discrepancy by the maximum degree of ℋ. It is a famous open problem whether this bound can be improved asymptotically (modified versions of the original proof give 2t-1 or even 2t-3). Beck and Fiala conjectured that disc(ℋ)=O(t), but little progress has been made so far in this direction. Bednarchak and Helm[9] and Helm[10] improved the Beck-Fiala bound in tiny steps to disc(ℋ)≤2t−3 (for a slightly restricted situation, i.e. t≥3). A corollary of Beck's paper[1] – the first time the notion of discrepancy explicitly appeared – shows disc(ℋ)≤Ctlog⁡mlog⁡n for some constant C. The latest improvement in this direction is due to Banaszczyk:[11] disc(ℋ)=O(tlog⁡n).

Classic theorems

  • Axis-parallel rectangles in the plane (Roth, Schmidt)
  • Discrepancy of half-planes (Alexander, Matoušek)
  • Arithmetic progressions (Roth, Sárközy, Beck, Matoušek & Spencer)
  • Beck-Fiala theorem
  • Six Standard Deviations Suffice (Spencer)

Major open problems

  • Axis-parallel rectangles in dimensions three and higher (Folklore)
  • Komlos conjecture
  • Homogeneous arithmetic progressions (Erdős, $500)

Applications

  • Numerical Integration: Monte Carlo methods in high dimensions.
  • Computational Geometry: Divide and conquer algorithms.
  • Image Processing: Halftoning

Notes

  1. ↑ 1.0 1.1 J. Beck: "Roth's estimate of the discrepancy of integer sequences is nearly sharp", page 319-325. Combinatorica, 1, 1981
  2. ↑ K. F. Roth: "Remark concerning integer sequences", pages 257–260. Acta Arithmetica 9, 1964
  3. ↑ J. Spencer: "A remark on coloring integers", pages 43–44. Canad. Math. Bull. 15, 1972.
  4. ↑ P. Erdős and J. Spencer: "Imbalances in k-colorations", pages 379–385. Networks 1, 1972.
  5. ↑ P. Erdős and J. Spencer: "Probabilistic Methods in Combinatorics." Akadémia Kiadó, Budapest, 1974.
  6. ↑ J. Matoušek and J. Spencer: "Discrepancy in arithmetic progressions", pages 195–204. J. Amer. Math. Soc. 9, 1996.
  7. ↑ J. Matoušek: "Tight upper bound for the discrepancy of half-spaces", pages 593–601. Discrepancy and Computational Geometry 13, 1995.
  8. ↑ J. Beck and T. Fiala: "Integer making theorems", pages 1–8. Discrete Applied Mathematics 3, 1981.
  9. ↑ D. Bednarchak and M. Helm: "A note on the Beck-Fiala theorem", pages 147–149. Combinatorica 17, 1997.
  10. ↑ M. Helm: "On the Beck-Fiala theorem", page 207. Discrete Mathematics 207, 1999.
  11. ↑ W. Banaszczyk: "Balancing vectors and Gaussian measure of n-dimensional convex bodies", pages 351–360. Random Structures and Algorithms 12, 1998.

References

Retrieved from "https://en.formulasearchengine.com/index.php?title=Strong_product_of_graphs&oldid=17249"