Abstract We prove tight upper bounds on the logarithmic derivative of independence and matching polynomials ‐regular graphs. For independent sets, this theorem is a strengthening results Kahn, Galvin Tetali, Zhao showing that union copies maximizes number sets polynomial graph. matchings, shows total matchings graph are maximized by . Using we asymptotic conjecture Friedland, Krop, Lundow, Markström. In probabilistic language, our main theorems state for all graphs , occupancy fraction...

Pour Δ≥5 et q grand en fonction de Δ, nous donnons une description détaillée la transition phase du modèle composantes connexes aléatoires (i.e., le FK) sur des graphes Δ-réguliers aléatoires. En particulier, déterminons distribution limite poids phases ordonnées désordonnées au point critique prouvons décroissance exponentielle corrélations comportement gaussien fluctuations loin critique. Nos techniques sont basées l'utilisation modèles polymères l'expansion clusters pour contrôler les...

Let <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper A"> <mml:semantics> <mml:mi>A</mml:mi> <mml:annotation encoding="application/x-tex">A</mml:annotation> </mml:semantics> </mml:math> </inline-formula> be drawn uniformly at random from the set of all alttext="n times n"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>×<!-- × --></mml:mo> </mml:mrow> encoding="application/x-tex">n\times n</mml:annotation> symmetric matrices with...

We give a fully polynomial-time approximation scheme (FPTAS) and an efficient sampling algorithm for the high-fugacity hard-core model on bounded-degree bipartite expander graphs low-temperature ferromagnetic Potts graphs. The results apply, example, to random (bipartite) $\Delta$-regular graphs, which no algorithms were known these problems (with exception of Ising model) in nonuniqueness regime infinite tree. also find counting proper $q$-colorings when $q$ is sufficiently small as...

We prove an asymptotically tight lower bound on the average size of independent sets in a triangle-free graph $n$ vertices with maximum degree $d$, showing that set drawn uniformly at random from such has expected least $(1+o_d(1)) \frac {\log d}{d}n$. This gives alternative proof Shearer's upper Ramsey number $R(3,k)$. then total $d$ is $\exp \left [\left (\frac {1}{2}+o_d(1) \right ) ^2 d}{d}n ]$. The constant $1/2$ exponent best possible. In both cases, tightness exhibited by $d$-regular...

We revisit Sapozhenko's classic proof on the asymptotics of number independent sets in discrete hypercube { 0 , 1 } d and Galvin's follow-up work weighted sets. combine graph container methods with cluster expansion abstract polymer models, two tools from statistical physics, to obtain considerably sharper detailed probabilistic information about typical structure (weighted) hypercube. These results refine those Korshunov Sapozhenko Galvin, answer several questions Galvin.

We give an FPTAS and efficient sampling algorithm for the high-fugacity hard-core model on bounded-degree bipartite expander graphs low-temperature ferromagnetic Potts graphs. The results apply, example, to random (bipartite) Δ-regular graphs, which no algorithms were known these problems (with exception of Ising model) in non-uniqueness regime infinite tree.

Abstract Given graphs and a positive integer , say that is ‐ Ramsey for denoted if every ‐coloring of the edges contains monochromatic copy . The size‐Ramsey number graph defined to be Answering question Conlon, we prove that, fixed have where th power ‐vertex path (ie, with vertex set all such distance between in at most ). Our proof probabilistic, but can also made constructive.

We prove a lower bound on the entropy of sphere packings $\mathbb R^d$ density $\Theta(d \cdot 2^{-d})$. The measures how plentiful such are, and our result is significantly stronger than trivial that can be obtained from mere existence dense packing. Our method also provides new, statistical-physics-based proof $\Omega(d 2^{-d})$ maximum packing by showing expected random configuration hard model at least $(1+o_d(1)) \log(2/\sqrt{3}) d 2^{-d}$ when ratio fugacity parameter to volume covered...

Abstract Let A be an $n \times n$ symmetric matrix with $(A_{i,j})_{i\leqslant j}$ independent and identically distributed according to a subgaussian distribution. We show that $$ \begin{align*}\mathbb{P}(\sigma_{\min}(A) \leqslant \varepsilon n^{-1/2} ) C + e^{-cn},\end{align*} where $\sigma _{\min }(A)$ denotes the least singular value of constants $C,c&gt;0 $ depend only on distribution entries . This result confirms folklore conjecture lower tail such matrices is best possible up...

Abstract We prove tight upper and lower bounds on the internal energy per particle (expected number of monochromatic edges vertex) in anti‐ferromagnetic Potts model cubic graphs at every temperature for all . This immediately implies corresponding partition function. Taking zero‐temperature limit gives new results extremal combinatorics: q ‐colorings a 3‐regular graph, any , is maximized by union 's. proves d = 3 case conjecture Galvin Tetali.

Abstract For a graph and , we denote by the random sparsification of obtained keeping each edge independently, with probability . We show that there exists such if is an ‐vertex then high contains triangle factor. Both minimum degree condition condition, up to choice are tight. Our result can be viewed as common strengthening seminal theorems Corrádi Hajnal, which deals extremal for containing factors (corresponding in our result), Johansson, Kahn Vu, threshold appearance factor result). It...

Abstract We determine the asymptotics of number independent sets size $\lfloor \beta 2^{d-1} \rfloor$ in discrete hypercube $Q_d = \{0,1\}^d$ for any fixed $\beta \in (0,1)$ as $d \to \infty$ , extending a result Galvin (1-1/\sqrt{2},1)$ . Moreover, we prove multivariate local central limit theorem structural features $Q_d$ drawn according to hard-core model at fugacity $\lambda&gt;0$ In proving these results develop several general tools performing combinatorial enumeration using polymer...

Abstract By implementing algorithmic versions of Sapozhenko's graph container methods, we give new algorithms for approximating the number independent sets in bipartite graphs. Our first algorithm applies to ‐regular, graphs satisfying a weak expansion condition: when is constant, and ‐expander, obtain an FPTAS sets. Previously such result was known only much stronger conditions random The also weighted sets: with fixed, hard‐core model partition function at fugacity . Finally present that...

Abstract We demonstrate a quasipolynomial-time deterministic approximation algorithm for the partition function of Gibbs point process interacting via stable potential. This result holds all activities $\lambda$ which satisfies zero-free assumption in neighbourhood interval $[0,\lambda ]$ . As corollary, finiterange potentials, we obtain $\lambda \lt 1/(e^{B + 1} \hat C_\phi )$ where $\hat C_\phi$ is temperedness parameter and $B$ stability constant $\phi$ In special case repulsive potential...

AbstractA large class of multiplicative submonoids the natural numbers is presented, which includes congruence monoids as well numerical (by isomorphism). For in this class, important factorization property finite elasticity characterized. Additional informationNotes on contributorsMatthew JenssenMATTHEW O. JENSSEN completed his B.A. mathematics at University Cambridge 2012 and currently studying for an M.Math via Part III Mathematical Tripos. His mathematical interests include algebra,...