We study the problems of bounding the number weak and strong independent sets in $r$-uniform, $d$-regular, $n$-vertex linear hypergraphs with no cross-edges. In the case of weak independent sets, we provide an upper bound that is tight up to the firs
t order term for all (fixed) $rge 3$, with $d$ and $n$ going to infinity. In the case of strong independent sets, for $r=3$, we provide an upper bound that is tight up to the second-order term, improving on a result of Ordentlich-Roth (2004). The tightness in the strong independent set case is established by an explicit construction of a $3$-uniform, $d$-regular, cross-edge free, linear hypergraph on $n$ vertices which could be of interest in other contexts. We leave open the general case(s) with some conjectures. Our proofs use the occupancy method introduced by Davies, Jenssen, Perkins, and Roberts (2017).
Let $H_{mathrm{WR}}$ be the path on $3$ vertices with a loop at each vertex. D. Galvin conjectured, and E. Cohen, W. Perkins and P. Tetali proved that for any $d$-regular simple graph $G$ on $n$ vertices we have $$hom(G,H_{mathrm{WR}})leq hom(K_{d+1}
,H_{mathrm{WR}})^{n/(d+1)}.$$ In this paper we give a short proof of this theorem together with the proof of a conjecture of Cohen, Perkins and Tetali. Our main tool is a simple bijection between the Widom-Rowlinson model and the hard-core model on another graph. We also give a large class of graphs $H$ for which we have $$hom(G,H)leq hom(K_{d+1},H)^{n/(d+1)}.$$ In particular, we show that the above inequality holds if $H$ is a path or a cycle of even length at least $6$ with loops at every vertex.
Catalan numbers arise in many enumerative contexts as the counting sequence of combinatorial structures. In this work, we consider natural Markov chains on some of the realizations of the Catalan sequence. While our main result is in deriving an $O(n
^2 log n)$ bound on the mixing time in $L_2$ (and hence total variation) distance for the random transposition chain on Dyck paths, we raise several open questions, including the optimality of the above bound. The novelty in our proof is in establishing a certain negative correlation property among random bases of lattice path matroids, including the so-called Catalan matroid which can be defined using Dyck paths.
We formulate and prove inverse mixing lemmas in the settings of simplicial complexes and k-uniform hypergraphs. In the hypergraph setting, we extend results of Bilu and Linial for graphs. In the simplicial complex setting, our results answer a question of Parzanchevski et al.
Using data from the Spitzer Space Telescope, we analyze the mid-infrared (3-70 micron) spectral energy distributions of dry merger candidates in the Bootes field of the NOAO Deep Wide-Field Survey. These candidates were selected by previous authors t
o be luminous, red, early-type galaxies with morphological evidence of recent tidal interactions. We find that a significant fraction of these candidates exhibit 8 and 24 micron excesses compared to expectations for old stellar populations. We estimate that a quarter of dry merger candidates have mid-infrared-derived star formation rates greater than ~1 MSun/yr. This represents a frosting on top of a large old stellar population, and has been seen in previous studies of elliptical galaxies. Further, the dry merger candidates include a higher fraction of starforming galaxies relative to a control sample without tidal features. We therefore conclude that the star formation in these massive ellipticals is likely triggered by merger activity. Our data suggest that the mergers responsible for the observed tidal features were not completely dry, and may be minor mergers involving a gas-rich dwarf galaxy.
