Source author record

Alexandru Malekshahian

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Data Structures and Algorithms

Catalog footprint

Research overview

2works

2topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

A refined graph container lemma and applications to the hard-core model on bipartite expanders

We establish a refined version of a graph container lemma due to Galvin and discuss several applications related to the hard-core model on bipartite expander graphs. Given a graph $G$ and $λ>0$ , the hard-core model on $G$ at activity $λ$ is the probability distribution $μ_{G,λ}$ on independent sets in $G$ given by $μ_{G,λ}(I)\propto λ^{|I|}$ . As one of our main applications, we show that the hard-core model at activity $λ$ on the hypercube $Q_d$ exhibits a `structured phase' for $λ= Ω( \log^2 d/d^{1/2})$ in the following sense: in a typical sample from $μ_{Q_d,λ}$ , most vertices are contained in one side of the bipartition of $Q_d$ . This improves upon a result of Galvin which establishes the same for $λ=Ω(\log d/ d^{1/3})$ . As another application, we establish a fully polynomial-time approximation scheme (FPTAS) for the hard-core model on a $d$ -regular bipartite $α$ -expander, with $α>0$ fixed, when $λ= Ω( \log^2 d/d^{1/2})$ . This improves upon the bound $λ=Ω(\log d/ d^{1/4})$ due to the first author, Perkins and Potukuchi. We discuss similar improvements to results of Galvin-Tetali, Balogh-Garcia-Li and Kronenberg-Spinka.

preprint2020arXiv

Strategy Stealing in Triangle Avoidance Games

In the game of $n-Sim$ , two players take it in turn to claim unclaimed edges from a complete graph on $n$ vertices, with the first person to create a triangle in his own edges being the loser. We present some strategy-stealing arguments that show that certain positions are wins for the second player. These are among the only strategy-stealing arguments that are known for misère games.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.