User hsien-chih chang - MathOverflow

Finding a cycle of fixed length

2010-02-25T13:26:59Z

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.

Is there any better result?

Is the generalized Erdős–Heilbronn problem true for finite cyclic groups?

2010-12-15T07:37:12Z

The generalized Erdős–Heilbronn (GEH) theorem, which is proved by da Silva and Hamidoune in 1994, states that:

Theorem. 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$.

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 proved by Balister and Wheeler in 2009.

Problem 1. Is the generalized Erdős–Heilbronn problem also true for any finite groups? In particular, is it true for finite cyclic groups?

This question is inspired by the construction of a counter-example to some variants of Ramsey theorem. In the construction we may not need the full strength of the GEH, so a related question is:

Problem 2. Is there any weaker results to the GEH, which have already been proved?

Answer by Hsien-Chih Chang for Most memorable titles

2010-11-01T02:34:11Z

I always like the title "Homology flows, cohomology cuts" by Chambers, Erickson and Nayyeri, which makes analog (a general technique indeed) to the well-known theorem (for graph theorists) "Maximum flows, minimum cuts".

Upper bound for size of subsets of a finite group that contains a sum-full set

2010-10-31T06:57:31Z

Problem

I'm looking for an upper bound for the number $k(G)$ of a finite group $G$, defined as follow:

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 \}. $$

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.

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.

Motivation

The restricted Davenport number $\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 zero-sum non-empty subset $S \subseteq A$, that is,

$$ \sum_{x \in S} x = 0, $$

where $0$ is the identity in $G$. In the paper "On a conjecture of Erdos and Heilbronn", Szemeredi has proved:

$$\hat{D}(G) = O(\sqrt{|G|}). $$

Hamidoune and Zemor set a precise bound $\sqrt{2}$ on the constant of the big-O notation.

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.

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?

2010-10-28T02:02:12Z

This is the Moore graph, 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

$$ 1+d \sum_{i=0}^{k-1} (d-1)^i $$

and as you mentioned it can be shown by spectral techniques that the only possible values for $d$ are

$$ d = 2,3,7,57. $$

Example for $d=7$ is the Hoffman–Singleton graph, but for the case $d=57$ it is still open. See Theorem 8.1.5 in the book "Spectra of graphs" by Brouwer and Haemers for reference.

Answer by Hsien-Chih Chang for Suggestions for good notation

2010-10-21T02:18:56Z

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

$]a,b[$

occurred in the book "Elementary Classical Analysis" by Marsden, and we can denote half-open half-closed interval like this:

$]a,b]$ or $[a,b[$.

Is there any metric space which is separable and bounded but not totally bounded?

2010-10-04T09:08:51Z

A metric space $X$ is called separable if there is a countable dense subset $S\subseteq X$. $X$ is called bounded 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$ totally bounded 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.

My question is:

Is there any metric space which is separable and bounded but not totally bounded?

Finding a subgraph with slightly large size in planar graphs

2010-08-14T05:44:00Z

This question is related to the previous discussion here.

Due to the result 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 this paper.

There is an open problem in the result:

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?

Answer by Hsien-Chih Chang for Finding a subgraph with slightly large size in planar graphs

2010-08-24T11:10:12Z

It seems to me that the following paper solves the $k$-path problem for $k = O(\log^2 n)$ in polynomial time:

Frederic Dorn, Eelko Penninkx, Hans L. Bodlaender and Fedor V. Fomin: Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Branch Decompositions. ESA 2005

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?

Answer by Hsien-Chih Chang for An approximate algorithm for finding Steiner Forest in a graph.

2010-04-19T17:50:43Z

There is a 2-approximation algorithm, see e.g.

A General Approximation Technique For Constrained Forest Problems, Michel Goemans, David P. Williamson, SIAM Journal on Computing 1992.

For special kind of graphs, better bounds can be obtained: for planar graphs there is a PTAS,

Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth, MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Dániel Marx, STOC '10.

Number of integral solutions to multi-variable polynomials

2010-04-17T18:51:54Z

This question follows the article discussed here

Problem

Suppose we're trying to bound the number of integral solutions to a system of multi-variable polynomials, say

$$ \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 < c$ for some constant $c$.

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?

Motivation

This question arose when I'm trying to come up with some reasonable constrains with the equation in Prouhet-Tarry-Escott Problem. 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.

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!

Edited

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?

One more question: How about further restricting the solutions to be prime numbers? Does this make any difference?

Answer by Hsien-Chih Chang for Existence of a zero-sum subset

2010-03-02T16:30:56Z

A weaker result can be obtained if we do not require the solution set to be distinct:

Lemma. There exist $i_1, \ldots, i_m$ (not necessary distinct) so that $a_{i_1}+a_{i_2}+ \ldots +a_{i_m}=0$.

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

$\sum_i a_i = \sum_i (b_i+c_i)$.

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.

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$

-- Edited at 2010/03/07 --

This conjecture is related to a special case of the Rainbow conjecture, which is highly related to the Caccetta-Häggkvist conjecture; see a survey by Sullivan.

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 rainbow 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$.

The Rainbow conjecture states that,

Conjecture. For a simple digraph $G$, either

There is a rainbow (di)cycle in $G$, or

There exists a node $v$ s.t. |{$w|\exists \text{ rainbow path from } v \rightarrow w $}| $\geq \sum_{i=1}^k \delta^{+}_{i}(v)$.

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 ~~$\delta_{i}^+(v) \geq 1$ for all $i$~~$^@$, there must be a dicycle in $G$ with distinct colors, that is, a subset $U$ with distinct numbers.

@ The condition $\delta_{i}^+(v) \geq 1$ is wrong.

In the survey 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$.

Answer by Hsien-Chih Chang for What are your favorite instructional counterexamples?

2010-03-02T06:58:03Z

A counter-example in graph theory - the Petersen graph.

In many ways it is the most simple graph with many strange properties. See the article on Wiki.

Quote from our professor who teaches graph theory:

If you think you've proved any lemma about graphs, try Petersen first!

Equality of the sum of powers

2010-03-01T17:11:11Z

Hi everyone, I got a problem when proving lemmas for some combinatorial problems, and it is a question about integers.

Let

$\sum_{k=1}^m a_k^t = \sum_{k=1}^n b_k^t$

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$.

Does the equality have no solutions?

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

$1^2 + 4^2 + 6^2 + 7^2 = 2^2 + 3^2 + 5^2 + 8^2$.

For $t > 2$, similar equalities hold:

$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$,

and we can extend this trick to all $t > 2$.

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?

For $t = 2$ we can combine two Pythagorean triples, say,

$5^2 + 12^2 + 25^2 = 7^2 + 13^2 + 24^2$,

but how about the cases for $t > 2$ and $n = m$?

Comment by Hsien-Chih Chang

2011-03-21T11:02:56Z

Thank you François!

Comment by Hsien-Chih Chang

2011-03-21T10:06:49Z

I don't get it; doesn't the class R contains all the recursive languages? en.wikipedia.org/wiki/R_(complexity)

Comment by Hsien-Chih Chang

2011-02-05T15:48:54Z

@Mohsen: A related post here on cstheory: cstheory.stackexchange.com/q/3100/1800. But I guess there are much stronger properties hold on complete multipartite graphs.

Comment by Hsien-Chih Chang

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$.

Comment by Hsien-Chih Chang

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!

Comment by Hsien-Chih Chang

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?

Comment by Hsien-Chih Chang

2010-12-15T08:11:14Z

oops, they should be p. I'll edit the question.

Comment by Hsien-Chih Chang

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.

Comment by Hsien-Chih Chang

2010-11-01T02:17:19Z

When dealing with Davenport number, one usually considers Abelian groups. But I'm also interested in non-Abelian ones.

Comment by Hsien-Chih Chang

2010-11-01T02:16:17Z

Nice answer indeed. Thanks!!

Comment by Hsien-Chih Chang

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.

Comment by Hsien-Chih Chang

2010-10-28T02:12:48Z

oops a typo: at least -> at most

Comment by Hsien-Chih Chang

2010-10-22T01:22:54Z

\lcirclearrowright in MnSymbol looks ok.

Comment by Hsien-Chih Chang

2010-10-22T01:07:24Z

The "really" 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.

Comment by Hsien-Chih Chang

2010-10-22T00:58:46Z

\ullcorner and \ulrcorner are nice, I've thought about it!