Given a locally finite graph $\Gamma $, an amenable subgroup G of graph automorphisms acting freely and almost transitively on its vertices, and a G-invariant activity function $\unicode{x3bb} $, consider the free energy $f_G(\Gamma ,\unicode{x3bb} )$ of the hardcore model defined on the set of independent sets in $\Gamma $ weighted by $\unicode{x3bb} $. Under the assumption that G is finitely generated and its word problem can be solved in exponential time, we define suitable ensembles of hardcore models and prove the following: if $\|\unicode{x3bb} \|_\infty < \unicode{x3bb} _c(\Delta )$, there exists a randomized $\epsilon $-additive approximation scheme for $f_G(\Gamma ,\unicode{x3bb} )$ that runs in time $\mathrm {poly}((1+\epsilon ^{-1})\lvert \Gamma /G \rvert )$, where $\unicode{x3bb} _c(\Delta )$ denotes the critical activity on the $\Delta $-regular tree. In addition, if G has a finite index linearly ordered subgroup such that its algebraic past can be decided in exponential time, we show that the algorithm can be chosen to be deterministic. However, we observe that if $\|\unicode{x3bb} \|_\infty> \unicode{x3bb} _c(\Delta )$, there is no efficient approximation scheme, unless $\mathrm {NP} = \mathrm {RP}$. This recovers the computational phase transition for the partition function of the hardcore model on finite graphs and provides an extension to the infinite setting. As an application in symbolic dynamics, we use these results to develop efficient approximation algorithms for the topological entropy of subshifts of finite type with enough safe symbols, we obtain a representation formula of pressure in terms of random trees of self-avoiding walks, and we provide new conditions for the uniqueness of the measure of maximal entropy based on the connective constant of a particular associated graph.

We prove a surprising symmetry between the law of the size $G_n$ of the greedy independent set on a uniform Cayley tree $ \mathcal{T}_n$ of size n and that of its complement. We show that $G_n$ has the same law as the number of vertices at even height in $ \mathcal{T}_n$ rooted at a uniform vertex. This enables us to compute the exact law of $G_n$ . We also give a Markovian construction of the greedy independent set, which highlights the symmetry of $G_n$ and whose proof uses a new Markovian exploration of rooted Cayley trees that is of independent interest.

We establish the first global results for groups definable in tame expansions of o-minimal structures. Let ${\mathcal{N}}$ be an expansion of an o-minimal structure ${\mathcal{M}}$ that admits a good dimension theory. The setting includes dense pairs of o-minimal structures, expansions of ${\mathcal{M}}$ by a Mann group, or by a subgroup of an elliptic curve, or a dense independent set. We prove: (1) a Weil’s group chunk theorem that guarantees a definable group with an o-minimal group chunk is o-minimal, (2) a full characterization of those definable groups that are o-minimal as those groups that have maximal dimension; namely, their dimension equals the dimension of their topological closure, (3) as an application, if ${\mathcal{N}}$ expands ${\mathcal{M}}$ by a dense independent set, then every definable group is o-minimal.

In his seminal work on Sidon sets, Pisier found an important characterization of Sidonicity: A set is Sidon if and only if it is proportionally quasi-independent. Later, it was shown that Sidon sets were proportionally “special” Sidon in several other ways. Here, we prove that Sidon sets in torsion-free groups are proportionally $n$-degree independent, a higher order of independence than quasi-independence, and we use this to prove that Sidon sets are proportionally Sidon with Sidon constants arbitrarily close to one, the minimum possible value.

This note completes the proof of the structure theorem for pp-matroid groups which was stated in our earlier paper J. Krempa and A. Stocka [‘On sets of pp-generators of finite groups’, Bull. Aust. Math. Soc.91 (2015), 241–249].

The classes of finite groups with minimal sets of generators of fixed cardinalities, named ${\mathcal{B}}$-groups, and groups with the basis property, in which every subgroup is a ${\mathcal{B}}$-group, contain only $p$-groups and some $\{p,q\}$-groups. Moreover, abelian ${\mathcal{B}}$-groups are exactly $p$-groups. If only generators of prime power orders are considered, then an analogue of property ${\mathcal{B}}$ is denoted by ${\mathcal{B}}_{pp}$ and an analogue of the basis property is called the pp-basis property. These classes are larger and contain all nilpotent groups and some cyclic $q$-extensions of $p$-groups. In this paper we characterise all finite groups with the pp-basis property as products of $p$-groups and precisely described $\{p,q\}$-groups.

Let G be a graph of order n, and let a and b be two integers with 1≤a≤b. Let h:E(G)→[0,1] be a function. If a≤∑ e∋xh(e)≤b holds for any x∈V (G), then we call G[Fh] a fractional [a,b] -factor of G with indicator function h, where Fh ={e∈E(G):h(e)>0}. A graph G is fractional independent-set-deletable [a,b] -factor-critical (in short, fractional ID-[a,b] -factor-critical) if G−I has a fractional [a,b] -factor for every independent set I of G. In this paper, it is proved that if n≥((a+2b)(a+b−2)+1 )/b and δ(G)≥((a+b)n )/(a+2b ) , then G is fractional ID-[a,b] -factor-critical. This result is best possible in some sense, and it is an extension of Chang, Liu and Zhu’s previous result.

A unit disk graph is the intersection graphof a family of unit disks in the plane.If the disks do not overlap, it is also a unit coin graph or penny graph.It is known that finding a maximum independent setin a unit disk graph is a NP-hard problem.In this work we extend this result to penny graphs.Furthermore, we prove that finding a minimum clique partitionin a penny graph is also NP-hard, and presenttwo linear-time approximation algorithms for the computation of clique partitions:a 3-approximation algorithm for unit disk graphsand a 2-approximation algorithm for penny graphs.