Many bigamy and polygamy criminal statutes in many U.S. jurisdictions are broader than you would think, and these statues have so far survived constitutional challenges. But, generally, bigamy and polygamy statues in the U.S. require the existence of at least one legally recognized marriage, even if subsequent relationships are merely instances of cohabitation, adultery, or a purported marriage. These criminal statutes generally do not apply when there are no legally recognized marriages in the polygamous family.
A good example are the relevant statutes of the State of Colorado in 2013 (I researched the issue then and I am not reviewing the law for updates in this answer, where I am using it as a typical example.)
Colorado's Revised Statutes provided at § 18-6-201, entitled "Bigamy" that:
(1) Any married person who, while still married, marries or cohabits
in this state with another commits bigamy, unless as an affirmative
defense it appears that at the time of the cohabitation or subsequent
marriage:
(a)The accused reasonably believed the prior spouse to be dead; or
(b) The prior spouse had been continually absent for a period of five
years during which time the accused did not know the prior spouse to
be alive; or
(c) The accused reasonably believed that he was legally eligible to
remarry.
(2) Bigamy is a class 6 felony.
Then, it provided in § 18-6-202 entitled "Marrying a bigamist" that:
Any unmarried person who knowingly marries or cohabits with another
in this state under circumstances known to him which would render the
other person guilty of bigamy under the laws of this state commits
marrying a bigamist, which is a class 2 misdemeanor.
And, finally, it provides in § 18-6-203, entitled "Definitions" that:
As used in sections 18-6-201 and 18-6-202, "cohabitation" means to
live together under the representation of being married.
Utah's statute on the subject at the time was similar. It stated:
A person is guilty of bigamy when, knowing he has a husband or wife or
knowing the other person has a husband or wife, the person purports
to marry another person or cohabits with another person.
Likewise, Washington State's statute, which has not been declared unconstitutional, states:
RCW 9A.64.010
Bigamy.
(1) A person is guilty of bigamy if he or she intentionally marries or
purports to marry another person when either person has a living
spouse.
(2) In any prosecution under this section, it is a defense that at the
time of the subsequent marriage or purported marriage:
(a) The actor reasonably believed that the prior spouse was dead; or
(b) A court had entered a judgment purporting to terminate or annul
any prior disqualifying marriage and the actor did not know that such
judgment was invalid; or
(c) The actor reasonably believed that he or she was legally eligible
to marry.
(3) The limitation imposed by RCW 9A.04.080 on commencing a
prosecution for bigamy does not begin to run until the death of the
prior or subsequent spouse of the actor or until a court enters a
judgment terminating or annulling the prior or subsequent marriage.
(4) Bigamy is a class C felony.
In contrast, California's bigamy statute (codified at California Penal Code Section 281) is more narrowly drafted and would probably not criminalize the conduct in the question. It appears that one would have to actually get a marriage license in another state for that statute to apply, in California one may not merely cohabitate or purport to be married, as one can in criminal prosecutions in some other states.
A constitutional challenge to the Utah statue quoted above prevailed in the trial court (the U.S. District Court fo the District of Utah) in December of 2013. The 91 page ruling in that case comprehensively reviews the relevant precedents and legal analysis.
But this ruling was reversed on appeal in the case of Brown v. Buhman, in 2016, for lack of a justiciable case or controversy and lack of standing because the DA stated that the DA would not prosecute the family seeking to have the statute declared unconstitutional under the statute. The vacated any effect of the ruling on the merits in the district court leaving the status quo that the statute is constitutional in place without regarding to the limitation that the DA expressed with regard to prosecuting this particular family. This case involved the family featured in the television show Sister Wives.
This case is also distinguishable from the facts in the original question because the man had a legally recognized marriage to one of the women in Brown v. Buhman.
The prior controlling precedents are Reynolds v. United States, 98 U.S. 145 (1879) and Late Corp. of The Church of Jesus Christ of Latter-day Saints v. United States, 136 U.S. 1 (1890), in which the U.S. Supreme Court upheld the constitutionality of a virtually identical predecessor statute against a constitutional free exercise challenge. The District Court rightly noted that this precedent could be question due to subsequent developments in constitutional law that could impliedly overruled this decision. But, no court has gone that far, and the U.S. Supreme Court, as recently as Employment Division, Department of Human Resources of Oregon v. Smith, 494 U.S. 872, 879 (1990), has continued to cite to Reynolds as good law. The Utah Supreme Court upheld the constitutionality of Utah's bigamy statute (including its co-habitation clause) in State of Utah v. Holm, 2006 UT 31, 137 P.3d 726.
No binding precedent in the U.S. holds that criminalizing bigamy or polygamy is unconstitutional, even in the case of broadly drafted statutes like those in Colorado and Utah, where affirmative legal recognition of the purported plural marriage is not sought.
The elements of the crime of bigamy under the Uniform Code of Military Justice (UCMJ) Manual for Courts-Martial, which makes bigamy a military justice offense under Article 134 of the Uniform Code of Military Justice is narrower and does not contain an express cohabitation clause as the Colorado and Utah statutes do (or at least did in 2013). A prosecution under the UCMJ for attempted bigamy would still be possible in these circumstances (in addition to prosecutions for adultery and wrongful cohabitation, which are separate UCMJ offenses under Article 134 of the UCMJ specified in the Manual for Courts-Martial) would be possible if there is at least one legally recognized marriage, but not if there isn't even one legally recognized marriage.
So what about if a few guys live together with one girl or the other
way around? What about if they call each other husband and wife but do
not get government recognition.
What laws would get them in trouble?
In some circumstances this could violate local zoning laws limiting the number of unrelated people who can share a residence, if they live together in one home. And, there have been laws that barred unmarried people from cohabiting. But most of those have been repealed and it isn't clear to what extent such laws (which are now rare) would be upheld as constitutional in the fact pattern of the original question.
