Stack Exchange
log in

YOUSEFY

 Mathematics

Associated with Math.SE; for both general discussion & math qu...
4
YOUSEFY
Oct 28, 2019 13:57
Path cover
Given a directed graph G = (V, E), a path cover is a set of directed paths such that every vertex v ∈ V belongs to at least one path. Note that a path cover may include paths of length 0 (a single vertex).A path cover may also refer to a vertex-disjoint path cover, i.e., a set of paths such that every vertex v ∈ V belongs to exactly one path. == Properties == A theorem by Gallai and Milgram shows that the number of paths in a smallest path cover cannot be larger than the number of vertices in the largest independent set. In particular, for any graph G, there is a path cover P and an independent...
YOUSEFY
Oct 28, 2019 13:54
Here is a definition for path cover
YOUSEFY
Oct 28, 2019 13:54
Hi, I have a small question: Give G=(V,E) and |V|=n, What is the maximum number of edges of path cover [vertex-disjoint path cover] problem? I believe it is n - 1. Is it possible to be n?
YOUSEFY
Oct 14, 2019 14:57
suppose for example: n=6 and h is congruent to 10a + 20b mod 6, then how can you find a and b? I don't want to factor 6
YOUSEFY
Oct 14, 2019 14:56
Given n and h, where n = a * b and h is the following equation: h is congruent to ca + rb mod n, where c and r are positive integer and a and b are PRIMES. Now, Is there any way to find a and b, given n and h?
YOUSEFY
Oct 14, 2019 14:37
No. see this example in this site "https://math.stackexchange.com/questions/2519390/if-the-graph-g-has-an-eulerian-circuit-prove-that-its-line-graph-has-a-hamilt"
The idea is that if you have a counterexample that shows that a hamiltonian G doesn't correspond to Eulerian graph in line graph G', or NOT-hamiltonian G doesn't correspond to NOT-Eulerian graph in line graph G', then you just prove that the converse doesn't follow.
YOUSEFY
Oct 14, 2019 06:47
I have a question: Suppose given you sum and product of two integer positive numbers a and b greater than one. Now, can you know a and b? The answer is given here:
https://math.stackexchange.com/questions/171407/finding-two-numbers-given-their-sum-and-their-product
But, now suppose the a and b are positive real numbers, does this make difference?
YOUSEFY
Oct 14, 2019 06:44
@AlessandroCodenotti Thank you
YOUSEFY
Oct 13, 2019 23:27
scientificamerican.com/article/what-is-goumldels-proof
YOUSEFY
Oct 13, 2019 23:27
I mean: Godel shows that there are true statements that are unprovable. Now, What else we want to know?
YOUSEFY
Oct 13, 2019 23:26
people who are interested in the foundation of mathematics, I would like them to answer: In this article, Scientific American explained Godel's incompleteness theorem in simple words. Then they put the following unanswered question in the last of this paragraph:
[Strictly speaking, his proof does not show that mathematics is incomplete. More precisely, it shows that individual formal axiomatic mathematical theories fail to prove the true numerical statement "This statement is unprovable." These theories therefore cannot be "theories of everything" for mathematics. Is this an isolated phenom…
YOUSEFY
Oct 10, 2019 13:19
Could someone explains to me what he means by [But we humans can just "see" the truth of G(F) while computer not]? If you have question/sharing points, anyone is welcome
YOUSEFY
Oct 10, 2019 13:18
Hi, I have something not clear about issue of Godel's incompleteness theorem and their argument.
I have the following sentence from book titled, "Quantum Computing since Democritus" by Scott Aaronson, chapter 11, p.151. He writes,
[But let's start by summarizing, in a few sentences, the Godel argument itself for why human thought can't be algorithmic. How about this: The first incompleteness theorem tells us that no computer, working within a fixed formal system F such as Zermelo-Fraenkel set theory, can prove the sentence: G(F) = "This sentence cannot be proved in F" But we humans can just…
YOUSEFY
Sep 21, 2019 16:52
I mean you cannot do it. I feel I miss something
YOUSEFY
Sep 21, 2019 16:51
Hi, I have a small question. I have a theorem that says: you have n linear equations modulo 2 with three variables per equation and with at most k occurrences of each variable. So, I did not write all theorem since it is another thing. But what I want is just to give example for what it said. e.g. suppose k=3, n=4. Then I don't know how to make 4 linear equations such that each linear equation has only three variables and they appear at most 3 times?
YOUSEFY
Sep 15, 2019 16:44
Okay, I will do it Ted. Thank you so much!
YOUSEFY
Sep 15, 2019 16:39
How did you do it? Do I need to write some values of W from the domain [0,n] and see when function has its maximum value
YOUSEFY
Sep 15, 2019 16:36
Because n is the number of vertices in graph and W is the maximum weight of a tour in the graph (a tour is a walk from a vertex and ending the same vertex such that you visit all vertices exactly once) and the weight of each edge is either 1 or 2. Thus, W is maximum will be 2n.
YOUSEFY
Sep 15, 2019 16:34
If I want to ignore the condition, does this make the question easier
YOUSEFY
Sep 15, 2019 16:32
I upload the paper here:scribd.com/document/425946785/Vishwanath-an-1992
YOUSEFY
Sep 15, 2019 16:31
I'm thinking about it
YOUSEFY
Sep 15, 2019 16:28
by Vishwanathan
YOUSEFY
Sep 15, 2019 16:28
it is from: An approximation algorithm for the asymmetric Traveling salesman problem with distances one and two, page 3.
YOUSEFY
Sep 15, 2019 16:27
take a look
YOUSEFY
Sep 15, 2019 16:27
ibb.co/3crR178
YOUSEFY
Sep 15, 2019 16:27
Okay, I see the point, but I don't know why in the paper shows the following:
YOUSEFY
Sep 15, 2019 16:24
I don't know how \frac{a-cb}{a-b} is equal to 2 - c.
YOUSEFY
Sep 15, 2019 16:23
I mean prove that \frac{a-cb}{a-b} = 2 -c.
YOUSEFY
Sep 15, 2019 16:23
@TedShifrin sorry Ted
YOUSEFY
Sep 15, 2019 16:10
\frac{a-cb}{a-b}=2-c?
YOUSEFY
Sep 15, 2019 16:10
Hi, I would like to know how to calculate the following:
(a-cb)/(a-b) = 2-c?
YOUSEFY
Nov 14, 2018 10:34
I don't understand how we have only 3 colors!! for me it is uncolorable with any way; since if you choose any arbitrary color for A or B, then we always have the same color of A and B in the right side. So, we cannot color K_{2,4} with any color
YOUSEFY
Nov 14, 2018 10:32
Hi I have this example in list coloring:

Consider the complete bipartite graph G = K2,4, having six vertices A, B, W, X, Y, Z such that A and B are each connected to all of W, X, Y, and Z, and no other vertices are connected. As a bipartite graph, G has usual chromatic number 2: one may color A and B in one color and W, X, Y, Z in another and no two adjacent vertices will have the same color. On the other hand, G has list-chromatic number larger than 2, as the following construction shows: assign to A and B the lists {red, blue} and {green, black}. Assign to the other four vertices the lis…
YOUSEFY
May 13, 2018 21:21
Hi, I would like to know: What is the upper bound for number of non-leaf nodes in tree? or How many non-leaf nodes in a tree? Is there any theory about this
 

 amateur reviews

paper reviews and discussions about non-peer-reviewed or contr...
YOUSEFY
May 11, 2018 19:00
The paper you put is very old paper and it seems for me a wonderful..
YOUSEFY
May 11, 2018 18:58
@ThomasKlimpel Thank you Thomas for your points.
YOUSEFY
May 2, 2018 09:50
These days I reviewed some pages from Garey and Johnason [it is one of the primary textbook for any one who works in complexity]. Next time, I will read some and discuss with what I feel 'not understand'!
YOUSEFY
May 2, 2018 09:48
What do you think! What do you understand from "Redundancy"!!
YOUSEFY
May 2, 2018 09:48
If you see any NP-completeness reduction, you will see kind of 'repetition', so does he mean that 'redundancy' is 'repetition'!!
YOUSEFY
May 2, 2018 09:44
Garey and Johnson wrote in their famous textbook p.155-156 the following

> Researcher who have attempted to prove Graph Isomorphism is NP-complete have noted that its nature is much more constrained than that of a typical NP-complete problem, such as Subgraph Isomorphism.

he just say that Graph Isomorphism is in INP and Subgraph Isomorphism is NP-complete.

> NP-completeness proofs seem to require a bit of leeway; if the desired structure X [subset, permutation, schedule, etc.] exists, it should still exist even if certain aspects of the instance are locally altered.
YOUSEFY
May 2, 2018 09:43
Now, I have another reading session and talking about it, let's start
YOUSEFY
May 2, 2018 09:43
I told myself that I would come here and share with you information. I chatted some in theory-salon [take a look].
YOUSEFY
May 2, 2018 09:41
Hi Thomas,
 

 theory salon

theoretical computer science. highlight reel vzn1.wordpress.co...
YOUSEFY
May 3, 2018 11:21
@vzn I remember read a paper by Ryan Williams about given probabilities of some open problems in complexity theory like P vs. NP.
YOUSEFY
May 3, 2018 10:39
So, even though we can solve the primality problem in polynomial time, but we still cannot have something like 'self-reducibility' in polynomial time between decision problem and optimization problem. So, Primality test is in polynomial time doesn't make Factoring in polynomial time by some reductions, the hardness here lies on the length of the input.
YOUSEFY
May 3, 2018 10:39
@vzn Okey, when a problem is NP-hard, it is because its optimization problem. Now, when we convert it to decision problem, it becomes NP-complete problem. Now, by self-reducibility we can ensure that when decision version of NP-hard problem solvable in polynomial, then it applies that the optimization problem can be solved in polynomial time. Now, in case of problem in NPI, it has different properties, different structure.
YOUSEFY
May 2, 2018 09:40
when you read my comments: imagine that you believe NP!=P
YOUSEFY
May 2, 2018 09:38
so my question is: Is Isomorphism Graph problem a candidate for class NPI "existence, not only conjecture" or candidate for class P? If it is candidate for class P, then what else of problems that are in NPI "but not candidate to be in P or NP-complete"?
YOUSEFY
May 2, 2018 09:38
Now, by Lender's 1975 paper, it says that if P != NP, then NPI is not empty. Now, most problems in 1980s or problems that are unknown complexities such as Linear programming at that time. Now it becomes in P. Also the same follows for factoring problem and discrete problem in 2002. Now, for Isomorphism problem it has recently a quasi-polynomial time [if ETH is true, then Isomorphism problem is not in NP-complete, but I don't know what is probabilities that this problem is not NP-hard!!]
YOUSEFY
May 2, 2018 09:38
About class NPI, in wikipedia it says that factoring problem, discrete problem and graph isomorphism problem are candidate to be in this class. But they forget that factoring problem and discrete problem have both polynomial time algorithm so they are in class P.