theory Archives » 100% Best Unlimited Private Proxies: Fast, Cheap and Secure

complexity theory – Dividing students into 4 groups based on preferences is NP-complete

Given a set of students $H$ of size $n$, and a set $E subseteq H times H $ of pairs of students that dislike each other, we want to determine whether it’s possible to divide them into $4$ groups such that:

no two students that dislike each other end up in the same group,

the size of each group must be at least $frac{n}{5}$.

I want to prove that this problem is NP-complete. I suspect that I could use the NP-completeness of the independence set problem, yet I have some problems with finding an appropriate reduction.

Let $G = (H, E)$ an undirected graph – each edge represents two students that dislike each other.

For the groups to be of the required size, their size must be $k in left (frac{n}{5}, frac{2n}{5} right ) cap mathbb{N}$. I could then try checking whether there is an independence set of size $k$ (which would mean there are $k$ students that potentially like each other), remove its vertices, and repeat for the next $k$. However, I don’t think this would result in a polynomial number of size combinations.

Do you have any advice on constructing this reduction?

gr.group theory – Typical preimage of the commutator map

By Goto’s theorem for any compact connected semisimple Lie group $G$ of dimension $n$, any element $xin G$ is a commutator, namely $x=(y,z)$ for some $y, zin G$. Another way to say it is that the commutator map $pi:Gtimes Grightarrow G$ is surjective. By Sard’s Lemma it follows that typical element $win G$ is a regular value of $pi$ and ${pi}^{-1}(w)subset Gtimes G$ is a smooth compact submanifold of dimension $n$.

Question: what is the homeomorphic type of this manifold for typical $w$?

Of course it is tempting to suspect that ${pi}^{-1}(w)$ is homeomorphic to $G$ but somehow I have difficulty in checking it even in rather simple case of $G=SO(3)$…

at.algebraic topology – What is the current state of research in Chern-Simons theory?

I’m a PhD student in mathematical physics looking for some orientation. As asked in the title, I would like to know the current state of research in Chern-Simons theory. More specifically, what are some of the directions that people are currently pursuing in this field.

I did not ask for more general topological field theories, but this is largely due to personal interests. Of course, answers related to other TFTs are more than welcome.

I feel this question has been asked before. But since this is a question about the current state of research, I think it deserves an update.

Thank you very much.

graph theory – Counting number of special subset of vertices in a tree

As defined in this article, an ordered pair $ (X,Y) $ of disjoint subsets of the vertices of a graph $ G $ with $ vert X vert = vert Y vert =2 $, is called an odd pair if the number of edges with one endpoint in $ X $ and another in $ Y $ is odd. Denote the number of odd pairs in $ G $ by $ s(G) $ (Note that if $ X neq Y$, then $(X, Y) neq (Y, X)$).

If $ G $ is the star graph $ S_{n} $, it is easily seen that $s(G) = 0$.

If $ G $ is the graph of order $n$ with the sequence of degrees $ lbrace n-2, 2, 1, 1, ldots ,1 rbrace $, I have proved that $s(G) = 2(n-3)^{2}$. (Here, $G$ is very similar to star graph.)

Now, I guess that for every tree $T$ of order $n$ such that $T$ is not star graph, $s(T) geq 2(n-3)^{2}$. I have tested this by computer search, but I couldn’t prove that. Can anyone help? I think using induction can lead to the proof.

Thanks in advance.

elementary set theory – Prove that if $x in A$ and $x notin (B cap C^c)$, then $(x in A$ and $x notin B)$ or $(x in A$ and $x notin C^c)$

This is part of a larger proof where I am attempting to show that
$$A setminus (B setminus C) = (A setminus B) cup (A setminus C^c).$$

I have already shown that $(A setminus B) cup (A setminus C^c) subseteq A setminus (B setminus C)$.

I also know that $A setminus (B setminus C) = A setminus (B cap C^c)$. My proof so far only consists of

“If $x in A setminus (B cap C^c)$, then $x in A$ and $x notin B cap C^c$. If $x notin B cap C^c$ then $x in B$ and $x in C^c$. Thus if $x in A setminus (B cap C^c)$, then $(x in A$ and $x notin B)$ or $(x in A$ and $x notin B).$”

The problem I am having is that I can’t use the distributive properties of conjunctions and disjunctions to prove this (as we have not done them so far). I’m not quite sure how to go about showing the above without using propositional logic. Any help would be appreciated.

Number theory question involving primes

Prove that, if a, b are prime numbers (a > b), each containing at least two digits,
then (a^4 – b^4) is divisible by 240. Also prove that, 240 is the gcd of all the numbers
which arise in this way.

Looking at the prime factorisation 240=(2^4)*3*5, i know i need to prove that the given difference is divisible by each of these.

How do i proceed from here? i have no idea.
Thanks.

measure theory – Null preserving transformation

Suppose that $(Omega,mu)$ is a measure space. Let $tau:OmegatoOmega$ is a measurable map such that $mucirctau^{-1}<<mu$. Then $tau$ s said to be null preserving. I want to prove the following. If $f:Omegatomathbb R$ is measurable and $mu({fneq fcirc f})=0,$ then there exists a measurable function $f^prime$ such that $f^prime=f^prime circ tau$ and $mu(fneq f^prime)=0.$ If we define $A:={xinOmega:f(x)=f(tau(x))}.$ I can prove that $A$ is $tau$-invariant mod $mu.$ A natural way to define $f^prime$ would be $f^prime=f1_{B}$ where $B$ is $tau$-invariant and $mu(ADelta B)=0.$ But I can not really see if it works. It will work definitely if we have $Bsubseteq A.$ We can have $B$ to be the set $cup_{k=0}^infty(Asetminus cup_{k=0}^inftytau^{-k}(Asetminus tau^{-1}A)).$ Can we have that $Bsubseteq A$? Also. I want to find some intuitive idea how the construction should be.

measure theory – Is the sets in density topology Euclidean $G_delta$?

It has been shown that every Borel subset of density topology X is d-$G_delta$. I’m curious about its connection to the euclidean topology. For example, is the close/open set in the density topology a $G_delta$ set in Euclidean topology? It seems false to me; for example, pick a non-Borel set S of Lebesgue measure 0, then it’s closed in the density topology but definitely not a $G_delta$ set in Euclidean topology. But I would like to know more about the connections between sets in density topology and its euclidean counterpart. Is there any related theorem on this subject?

nt.number theory – Is this number theoretic quantity upper bounded?

It seems my thinking gets organized after posting the question.

The natural logarithm of the quantity $pi(n)!$ is near $pi(n)log(pi(n)/e) + (log(taupi(n)))/2$ (a number-theoretic use for $tau$, the circumference of a unit radius circle). Using an approximation to $pi(n)$ we get that this is less than $An$ for some $A lt 2$. But $An/(n-h)$ is bounded above by $2A$, and gets very close to $A$. So with some work the original quantity should be shown to be less than $e^A$.

Verification is still appreciated.

Gerhard “And Still Worth An Acknowledgement” Paseman, 2020.05.30.