User hsien-chih chang - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T08:24:45Z http://mathoverflow.net/feeds/user/4248 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length Finding a cycle of fixed length Hsien-Chih Chang 2010-02-25T13:26:59Z 2011-02-23T01:40:45Z <p>Is there any result about the time complexity of finding a cycle of fixed length k in a general graph? All I know is that Noga Alon et al. use the techinique called "color-coding", which has a running time O(M(n)), where M(n) is the time of multiplying two n times n matrices.</p> <p>Is there any better result?</p> http://mathoverflow.net/questions/49494/is-the-generalized-erdsheilbronn-problem-true-for-finite-cyclic-groups Is the generalized Erdős–Heilbronn problem true for finite cyclic groups? Hsien-Chih Chang 2010-12-15T07:37:12Z 2010-12-15T18:56:17Z <p>The <a href="http://en.wikipedia.org/wiki/Restricted_sumset" rel="nofollow">generalized Erdős–Heilbronn (GEH) theorem</a>, which is proved by da Silva and Hamidoune in 1994, states that:</p> <p><strong>Theorem.</strong> If p is a prime and $X$ is a subset of $\mathbb{Z}_p$, then $|\hat{k}X| \geq \min \lbrace k|X|-k^2+1 , p \rbrace$ for $\hat{k}X = \lbrace x_1+\ldots+x_k \mid x_i \in X , x_i \neq x_j \rbrace$.</p> <p>Also, for the case that $k=2$ (which is called the Erdős–Heilbronn problem), the above statement holds for $X$ as a subset of any finite group $G$; the result is <a href="http://jeffreypaulwheeler.com/Final%20Erdos-Heilbronn_Problem.pdf" rel="nofollow">proved</a> by Balister and Wheeler in 2009.</p> <blockquote> <p><strong>Problem 1.</strong> Is the generalized Erdős–Heilbronn problem also true for any finite groups? In particular, is it true for finite cyclic groups?</p> </blockquote> <p>This question is inspired by the construction of a <a href="http://cstheory.stackexchange.com/questions/3795/extensions-of-ramseys-theorem-monochromatic-but-diverse/3803#3803" rel="nofollow">counter-example to some variants of Ramsey theorem</a>. In the construction we may not need the full strength of the GEH, so a related question is:</p> <blockquote> <p><strong>Problem 2.</strong> Is there any weaker results to the GEH, which have already been proved?</p> </blockquote> http://mathoverflow.net/questions/44326/most-memorable-titles/44406#44406 Answer by Hsien-Chih Chang for Most memorable titles Hsien-Chih Chang 2010-11-01T02:34:11Z 2010-11-01T02:34:11Z <p>I always like the title "<strong><a href="http://portal.acm.org/citation.cfm?id=1536453" rel="nofollow">Homology flows, cohomology cuts</a></strong>" by Chambers, Erickson and Nayyeri, which makes <em>analog</em> (a general technique indeed) to the well-known theorem (for graph theorists) "<strong>Maximum flows, minimum cuts</strong>".</p> http://mathoverflow.net/questions/44309/upper-bound-for-size-of-subsets-of-a-finite-group-that-contains-a-sum-full-set Upper bound for size of subsets of a finite group that contains a sum-full set Hsien-Chih Chang 2010-10-31T06:57:31Z 2010-10-31T18:02:26Z <h2>Problem</h2> <p>I'm looking for an upper bound for the number $k(G)$ of a finite group $G$, defined as follow:</p> <blockquote> <p>Let $\mathcal{F}_k$ be the family of subsets of $G$ with size $k$, and we define $k(G)$ be the minimum $k$ such that every subset $X \in \mathcal F_k$ contains a non-empty sum-full set $S$, which is a set satisfies $$S \subseteq S+S := \{ x+y \mid x,y \in S \}.$$</p> </blockquote> <p>Note that the inequality $k(G) \leq |G|$ holds trivially since there is only one subset in $\mathcal F_{|G|}$ which is $G$ itself, and $G$ is a semigroup indeed.</p> <p>Are there any papers or references about this number $k(G)$? Does it have a name? I'm interesting in particularly upper bounds of $k(G)$, but any related results are fine.</p> <hr> <h2>Motivation</h2> <p>The <strong>restricted Davenport number</strong> $\hat{D}(G)$ of a group $G$, is defined as the smallest number $d$ such that given a subset $A \in \mathcal F_d$, there exists a <strong>zero-sum</strong> non-empty subset $S \subseteq A$, that is, </p> <p>$$\sum_{x \in S} x = 0,$$</p> <p>where $0$ is the identity in $G$. In the paper "On a conjecture of Erdos and Heilbronn", Szemeredi has proved:</p> <p>$$\hat{D}(G) = O(\sqrt{|G|}).$$</p> <p>Hamidoune and Zemor set a precise bound $\sqrt{2}$ on the constant of the big-O notation.</p> <p>I'm trying to provide a link between $\hat{D}(G)$ and the number $k(G)$; it seems to me that the size of sum-full sets in $G$ may related to the zero-sum problem. I'll provide the justification in another post, which is highly related.</p> http://mathoverflow.net/questions/43923/is-there-a-7-regular-graph-on-50-vertices-with-girth-5-what-about-57-regular-on/43928#43928 Answer by Hsien-Chih Chang for Is there a 7-regular graph on 50 vertices with girth 5? What about 57-regular on 3250 vertices? Hsien-Chih Chang 2010-10-28T02:02:12Z 2010-10-28T02:14:22Z <p>This is the <a href="http://en.wikipedia.org/wiki/Moore_graph" rel="nofollow">Moore graph</a>, which is a regular graph of degree $d$ with diameter $k$, with maximum possible nodes. A calculation shows that the number of nodes $n$ is at most</p> <p>$$1+d \sum_{i=0}^{k-1} (d-1)^i$$</p> <p>and as you mentioned it can be shown by spectral techniques that the only possible values for $d$ are</p> <p>$$d = 2,3,7,57.$$</p> <p>Example for $d=7$ is the <a href="http://en.wikipedia.org/wiki/Hoffman-Singleton_graph" rel="nofollow">Hoffman–Singleton graph</a>, but for the case $d=57$ it is still open. See Theorem 8.1.5 in the book "<a href="http://homepages.cwi.nl/~aeb/math/ipm.pdf" rel="nofollow">Spectra of graphs</a>" by Brouwer and Haemers for reference.</p> http://mathoverflow.net/questions/42929/suggestions-for-good-notation/42984#42984 Answer by Hsien-Chih Chang for Suggestions for good notation Hsien-Chih Chang 2010-10-21T02:18:56Z 2010-10-21T02:18:56Z <p>Since the standard notation for open interval $(a,b)$ can be confused with the coordinates, gcd, and other stuffs (open brackets have been used A LOT!), I've seem notations like </p> <p>$]a,b[$ </p> <p>occurred in the book "Elementary Classical Analysis" by Marsden, and we can denote half-open half-closed interval like this:</p> <p>$]a,b]$ or $[a,b[$.</p> http://mathoverflow.net/questions/40998/is-there-any-metric-space-which-is-separable-and-bounded-but-not-totally-bounded Is there any metric space which is separable and bounded but not totally bounded? Hsien-Chih Chang 2010-10-04T09:08:51Z 2010-10-04T09:19:30Z <p>A metric space $X$ is called <strong>separable</strong> if there is a countable dense subset $S\subseteq X$. $X$ is called <strong>bounded</strong> if there is an $x_0 \in X$ which every other element $x \in X$ has bounded distance to $x_0$. And we called $X$ <strong>totally bounded</strong> if for every $\epsilon>0$ there is a finite set $Y\subseteq X$ such that $X\subseteq \bigcup_{y\in Y}B(y,\epsilon)$, where $B(y,\epsilon)$ is the $\epsilon$-neighborhood of $y$ in $X$. It can be shown that $X$ is totally bounded implies $X$ is separable.</p> <p>My question is:</p> <blockquote> <p>Is there any metric space which is separable and bounded but not totally bounded?</p> </blockquote> http://mathoverflow.net/questions/35560/finding-a-subgraph-with-slightly-large-size-in-planar-graphs Finding a subgraph with slightly large size in planar graphs Hsien-Chih Chang 2010-08-14T05:44:00Z 2010-08-24T11:10:12Z <p>This question is related to the previous discussion <a href="http://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length" rel="nofollow">here</a>.</p> <p>Due to the <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.3377" rel="nofollow">result</a> of Noga Alon et al., there is an $O((2k)^kn)$ algorithm for deciding whether a planar graph $G$ contains a fixed subgraph $H$ of size $k$, and the time complexity is reduced to $O(2^kn)$ if the graph $H$ is of bounded treewidth. Take $k = O(\log n)$ yields a polynomial time algorithm for the latter case, say the $k$-path problem mentioned by Ryan Williams in <a href="http://www.sciencedirect.com/science?_ob=ArticleURL&amp;_udi=B6V0F-4TX797W-1&amp;_user=7761201&amp;_coverDate=02%252F28%252F2009&amp;_rdoc=1&amp;_fmt=high&amp;_orig=search&amp;_sort=d&amp;_docanchor=&amp;view=c&amp;_searchStrId=1430356488&amp;_rerunOrigin=google&amp;_acct=C000051951&amp;_version=1&amp;_urlVersion=0&amp;_userid=7761201&amp;md5=903daeb9157174e1d0630f4b232f46e0" rel="nofollow">this paper</a>.</p> <p>There is an open problem in the <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.3377" rel="nofollow">result</a>: </p> <blockquote> <p>If we want to solve $k$-path problem in a planar graph with slightly larger $k$, say $k = O(\log^2 n)$, is there a polynomial time solution at this point? If so, what is the best time complexity at present?</p> </blockquote> http://mathoverflow.net/questions/35560/finding-a-subgraph-with-slightly-large-size-in-planar-graphs/36543#36543 Answer by Hsien-Chih Chang for Finding a subgraph with slightly large size in planar graphs Hsien-Chih Chang 2010-08-24T11:10:12Z 2010-08-24T11:10:12Z <p>It seems to me that the following paper solves the $k$-path problem for $k = O(\log^2 n)$ in polynomial time:</p> <blockquote> <p>Frederic Dorn, Eelko Penninkx, Hans L. Bodlaender and Fedor V. Fomin: <a href="http://www.springerlink.com/content/33kja2k4b1ghh12c/" rel="nofollow">Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Branch Decompositions</a>. ESA 2005</p> </blockquote> <p>The paper solved the $k$-cycle problem in time $O^*(c^{\sqrt{k}})$, which the $k$-path problem can be reduced to. Is my understanding correct?</p> http://mathoverflow.net/questions/21859/an-approximate-algorithm-for-finding-steiner-forest-in-a-graph/21865#21865 Answer by Hsien-Chih Chang for An approximate algorithm for finding Steiner Forest in a graph. Hsien-Chih Chang 2010-04-19T17:50:43Z 2010-04-19T17:50:43Z <p>There is a 2-approximation algorithm, see e.g. </p> <blockquote> <p>A General Approximation Technique For Constrained Forest Problems, Michel Goemans, David P. Williamson, SIAM Journal on Computing 1992.</p> </blockquote> <p>For special kind of graphs, better bounds can be obtained: for planar graphs there is a PTAS,</p> <blockquote> <p>Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth, MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Dániel Marx, STOC '10.</p> </blockquote> http://mathoverflow.net/questions/21683/number-of-integral-solutions-to-multi-variable-polynomials Number of integral solutions to multi-variable polynomials Hsien-Chih Chang 2010-04-17T18:51:54Z 2010-04-18T11:54:54Z <p>This question follows the article discussed <a href="http://mathoverflow.net/questions/16764/equality-of-the-sum-of-powers" rel="nofollow">here</a></p> <hr> <h2>Problem</h2> <p>Suppose we're trying to bound the number of integral solutions to a system of multi-variable polynomials, say</p> <p>$$\sum_{i=1}^n x_i^t = \sum_{i=1}^n y_i^t,$$ where each $x_i,y_i \in \mathbb N$ and for each $t &lt; c$ for some constant $c$.</p> <p>If we do not put any constrains on the solution, there are infinitely many possible solutions even when $n=C=1$. So if we put some constrains on {$x_i,y_i$} like $x_i,y_i \in$ {$0,1,\ldots,n$}, then how many possible solutions can we get? Naively there are $O(n^n)$ choices, but it seems highly unlikely that there are many solutions to the system of equations. Is there any exist bound on the number of solutions, say $O(n^k)$ for fixed $k$ or even better bounds? Are there some well-known approaches to bound the number of solutions of an equation? </p> <h2>Motivation</h2> <p>This question arose when I'm trying to come up with some reasonable constrains with the equation in <a href="http://en.wikipedia.org/wiki/Prouhet-Tarry-Escott_problem" rel="nofollow">Prouhet-Tarry-Escott Problem</a>. It seems like if we restrict the maximum value of variables, there aren't many solutions to the equation. I tried to add more constrains to get rid of the already few solutions, but it seems that there is no direct way making the solution set empty, that is, no possible solutions under such constrains.</p> <p>So I turn to find some existing bounds for the equation, but sadly nothing occurred. Can it be still hard to find such results, or there are some theorems like the Fundamental Theorem of Algebra, concerning the number of solutions to a multi-variable equation? Any information is useful. Thank you all!</p> <h2>Edited</h2> <p>According to Felipe Voloch (Thanks!), the general approach to the question is the Hardy-Littlewood method, which considers the number of solutions to an equal-power Diophantine equation. But it seems that the method gives a lower bound on the number of solutions (is this correct?), rather than an upper bound. Or there are some ways to give upper bounds by the same method?</p> <p>One more question: How about further restricting the solutions to be prime numbers? Does this make any difference?</p> http://mathoverflow.net/questions/16857/existence-of-a-zero-sum-subset/16871#16871 Answer by Hsien-Chih Chang for Existence of a zero-sum subset Hsien-Chih Chang 2010-03-02T16:30:56Z 2010-03-07T13:56:11Z <p>A weaker result can be obtained if we do not require the solution set to be distinct:</p> <blockquote> <p><strong>Lemma.</strong> There exist $i_1, \ldots, i_m$ (not necessary distinct) so that $a_{i_1}+a_{i_2}+ \ldots +a_{i_m}=0$.</p> </blockquote> <p>proof. Consider the sum of all the equations $a_i=b_i+c_i$ over all $a_i \in S$, where $b_i,c_i \in S$ guaranteed by the definition of $S$, we have</p> <p>$\sum_i a_i = \sum_i (b_i+c_i)$.</p> <p>Noticed that the multiset {$b_i,c_i$} must contain all elements in $S$, otherwise we can remove the elements in $S \setminus$ {$b_i,c_i$}, obtaining another $S^*$ which satisfies the property.</p> <p>Now since $S \subseteq$ {$b_i,c_i$}, we cancel out $\sum_i a_i$ with the same numbers in {$b_i,c_i$}, which makes the equality the form $a_{i_1}+a_{i_2}+ \ldots +a_{i_m}=0$ with $a_{i_k} \in$ {$b_i,c_i$}, i.e. $a_{i_k} \in S$. Since there are totally $2|S|$ elements in multiset {$b_i,c_i$} and $0 \notin S$, we have the lemma. $\square$</p> <hr> <p>-- Edited at 2010/03/07 --</p> <p>This conjecture is related to a special case of the <strong>Rainbow conjecture</strong>, which is highly related to the Caccetta-Häggkvist conjecture; see a <a href="http://www.aimath.org/WWN/caccetta/caccetta.pdf" rel="nofollow">survey</a> by Sullivan.</p> <p>For a digraph $G$ and edge sets $E_1, \ldots, E_k \subseteq E(G)$, denote $G_i = (V(G), E_i)$ and we say a subgraph $H$ of $G$ is <em>rainbow</em> if $|E(H) \cap E_i| \leq 1$ for each $i$ and $|E(H)| \geq 1$. Let $\delta_i^+(v)$ denote the outdegree of $v$ in graph $G_i$.</p> <p>The Rainbow conjecture states that, </p> <blockquote> <p><strong>Conjecture.</strong> For a simple digraph $G$, either</p> <ul> <li>There is a rainbow (di)cycle in $G$, or</li> <li>There exists a node $v$ s.t. |{$w|\exists \text{ rainbow path from } v \rightarrow w$}| $\geq \sum_{i=1}^k \delta^{+}_{i}(v)$.</li> </ul> </blockquote> <p>Now by constructing a digraph $G$ with directed edge $(u,v)$ in $E_w$ if $u+w = v$, there is a dicycle in $G$ iff there is a set $U$ s.t. $\sum_{x\in U} x = 0$, for $x \in S$. Since the second condition of the Rainbow conjecture can not be satisfied for $k=|S|$ and <s>$\delta_{i}^+(v) \geq 1$ for all $i$</s>$^@$, there must be a dicycle in $G$ with distinct colors, that is, a subset $U$ with distinct numbers.</p> <p>@ The condition $\delta_{i}^+(v) \geq 1$ is wrong.</p> <p>In the <a href="http://www.aimath.org/WWN/caccetta/caccetta.pdf" rel="nofollow">survey</a> by Sullivan, the conjecture is solved for the special case that $\delta_{i}^+(v) \leq 1$ for all $v$ and all $i$, which is the case since for a given $u$ and $w$, there is at most one solution to the equation $u+v=w$, which corresponds to the directed edge $(u,v) \in E_w$.</p> http://mathoverflow.net/questions/16829/what-are-your-favorite-instructional-counterexamples/16836#16836 Answer by Hsien-Chih Chang for What are your favorite instructional counterexamples? Hsien-Chih Chang 2010-03-02T06:58:03Z 2010-03-02T06:58:03Z <p>A counter-example in graph theory - the <strong>Petersen graph</strong>.</p> <p><img src="http://www.imada.sdu.dk/~btoft/GT2009/PetersenGraphEmbeddings_800.gif" alt="alt text"></p> <p>In many ways it is the most simple graph with many strange properties. See the article on <a href="http://en.wikipedia.org/wiki/Petersen_graph" rel="nofollow">Wiki</a>.</p> <p>Quote from our professor who teaches graph theory:</p> <blockquote> <p>If you think you've proved any lemma about graphs, try Petersen first!</p> </blockquote> http://mathoverflow.net/questions/16764/equality-of-the-sum-of-powers Equality of the sum of powers Hsien-Chih Chang 2010-03-01T17:11:11Z 2010-03-01T22:26:35Z <p>Hi everyone, I got a problem when proving lemmas for some combinatorial problems, and it is a question about integers.</p> <p>Let </p> <p>$\sum_{k=1}^m a_k^t = \sum_{k=1}^n b_k^t$ </p> <p>be an equation, where $m, n, t, a_i, b_i$ are positive integers, and $a_i \neq a_j$ for all $i, j$, $b_i \neq b_j$ for all $i, j$, $a_i \neq b_j$ for all $i, j$.</p> <blockquote> <p>Does the equality have no solutions?</p> </blockquote> <p>For $n \neq m$, it is easy to find solutions for $t=2$ by Pythagorean theorem, and even for $n = m$, we have solutions like </p> <p>$1^2 + 4^2 + 6^2 + 7^2 = 2^2 + 3^2 + 5^2 + 8^2$.</p> <p>For $t > 2$, similar equalities hold:</p> <p>$1^2 + 4^2 + 6^2 + 7^2 + 10^2 + 11^2 + 13^2 + 16^2 = 2^2 + 3^2 + 5^2 + 8^2 + 9^2 + 12^2 + 14^2 + 15^2$ and $1^3 + 4^3 + 6^3 + 7^3 + 10^3 + 11^3 + 13^3 + 16^3 = 2^3 + 3^3 + 5^3 + 8^3 + 9^3 + 12^3 + 14^3 + 15^3$,</p> <p>and we can extend this trick to all $t > 2$.</p> <blockquote> <p>The question is, if we introduce one more restriction, that is, $|a_i - a_j| \geq 2$ and $|b_i - b_j| \geq 2$ for all $i, j$, is it still possible to find solutions for the equation?</p> </blockquote> <p>For $t = 2$ we can combine two Pythagorean triples, say,</p> <p>$5^2 + 12^2 + 25^2 = 7^2 + 13^2 + 24^2$,</p> <p>but how about the cases for $t > 2$ and $n = m$?</p> http://mathoverflow.net/questions/59009/no-complexity-class-contains-all-recursive-languages Comment by Hsien-Chih Chang Hsien-Chih Chang 2011-03-21T11:02:56Z 2011-03-21T11:02:56Z Thank you Fran&#231;ois! http://mathoverflow.net/questions/59009/no-complexity-class-contains-all-recursive-languages Comment by Hsien-Chih Chang Hsien-Chih Chang 2011-03-21T10:06:49Z 2011-03-21T10:06:49Z I don't get it; doesn't the class R contains all the recursive languages? <a href="http://en.wikipedia.org/wiki/R_(complexity" rel="nofollow">en.wikipedia.org/wiki/R_(complexity</a>) http://mathoverflow.net/questions/54395/spectral-techniques-for-genus-of-a-graph Comment by Hsien-Chih Chang Hsien-Chih Chang 2011-02-05T15:48:54Z 2011-02-05T15:48:54Z @Mohsen: A related post here on cstheory: <a href="http://cstheory.stackexchange.com/q/3100/1800" rel="nofollow">cstheory.stackexchange.com/q/3100/1800</a>. But I guess there are much stronger properties hold on complete multipartite graphs. http://mathoverflow.net/questions/42929/suggestions-for-good-notation/45377#45377 Comment by Hsien-Chih Chang Hsien-Chih Chang 2010-12-18T15:25:49Z 2010-12-18T15:25:49Z I like $f^\rightarrow$ and $f^\leftarrow$ better, since when applying the inverse, it looks like: $(f^{-1})^\rightarrow = f^\leftarrow$. http://mathoverflow.net/questions/49494/is-the-generalized-erdsheilbronn-problem-true-for-finite-cyclic-groups/49502#49502 Comment by Hsien-Chih Chang Hsien-Chih Chang 2010-12-15T18:36:28Z 2010-12-15T18:36:28Z @Aaron: For the case of $k=2$, we have to replace $p$ with the smallest prime divided $n$, as you mentioned in the edited part. And this is indeed a great answer, many thanks for your thoughtful observations and ideas! http://mathoverflow.net/questions/49494/is-the-generalized-erdsheilbronn-problem-true-for-finite-cyclic-groups/49502#49502 Comment by Hsien-Chih Chang Hsien-Chih Chang 2010-12-15T09:46:17Z 2010-12-15T09:46:17Z Oh, so the GEH for cyclic group HAS to be weaken... Thank you for the nice example! Any idea on the weaker results? http://mathoverflow.net/questions/49494/is-the-generalized-erdsheilbronn-problem-true-for-finite-cyclic-groups Comment by Hsien-Chih Chang Hsien-Chih Chang 2010-12-15T08:11:14Z 2010-12-15T08:11:14Z oops, they should be p. I'll edit the question. http://mathoverflow.net/questions/48278/are-innermost-reductions-perpetual-in-untyped-lambda-calculus Comment by Hsien-Chih Chang Hsien-Chih Chang 2010-12-14T17:54:04Z 2010-12-14T17:54:04Z @Adam: $\lambda$-calculus is a part of theoretical computer science too. There are questions in this topic that have been answered. http://mathoverflow.net/questions/44309/upper-bound-for-size-of-subsets-of-a-finite-group-that-contains-a-sum-full-set Comment by Hsien-Chih Chang Hsien-Chih Chang 2010-11-01T02:17:19Z 2010-11-01T02:17:19Z When dealing with Davenport number, one usually considers Abelian groups. But I'm also interested in non-Abelian ones. http://mathoverflow.net/questions/44309/upper-bound-for-size-of-subsets-of-a-finite-group-that-contains-a-sum-full-set/44325#44325 Comment by Hsien-Chih Chang Hsien-Chih Chang 2010-11-01T02:16:17Z 2010-11-01T02:16:17Z Nice answer indeed. Thanks!! http://mathoverflow.net/questions/44309/upper-bound-for-size-of-subsets-of-a-finite-group-that-contains-a-sum-full-set Comment by Hsien-Chih Chang Hsien-Chih Chang 2010-10-31T07:30:54Z 2010-10-31T07:30:54Z Oops, I messed up with the definition of a semigroup. What I'm looking for is a sum-full set $A \subseteq A+A$, where a semigroup is a set with $A+A \subseteq A$. I'll modify the question. http://mathoverflow.net/questions/43923/is-there-a-7-regular-graph-on-50-vertices-with-girth-5-what-about-57-regular-on/43928#43928 Comment by Hsien-Chih Chang Hsien-Chih Chang 2010-10-28T02:12:48Z 2010-10-28T02:12:48Z oops a typo: at least -&gt; at most http://mathoverflow.net/questions/42929/suggestions-for-good-notation/42935#42935 Comment by Hsien-Chih Chang Hsien-Chih Chang 2010-10-22T01:22:54Z 2010-10-22T01:22:54Z \lcirclearrowright in MnSymbol looks ok. http://mathoverflow.net/questions/42929/suggestions-for-good-notation/43073#43073 Comment by Hsien-Chih Chang Hsien-Chih Chang 2010-10-22T01:07:24Z 2010-10-22T01:07:24Z The &quot;really&quot; big-O notation is a little bit confusing; since normally we write summation like this with $Y$ depends on the parameter $k$, but here we have the constant $C_k$ depends on it instead. http://mathoverflow.net/questions/42929/suggestions-for-good-notation/42984#42984 Comment by Hsien-Chih Chang Hsien-Chih Chang 2010-10-22T00:58:46Z 2010-10-22T00:58:46Z \ullcorner and \ulrcorner are nice, I've thought about it!