Source author record

Amanda Redlich

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

ResearcherUnclaimed source record

math.CO Discrete Mathematics nlin.SI

Catalog footprint

Research overview

6works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2025arXiv

Hoffman-London graphs: When paths minimize $H$ -colorings among trees

Given a graph $G$ and a target graph $H$ , an $H$ -coloring of $G$ is an adjacency-preserving vertex map from $G$ to $H$ . The number of $H$ -colorings of $G$ , $\hom(G,H)$ , has been studied for many classes of $G$ and $H$ . In particular, extremal questions of maximizing and minimizing $\hom(G,H)$ have been considered when $H$ is a clique or $G$ is a tree. In this paper, we develop a new technique using automorphisms of $H$ to show that $\hom(T,H)$ is minimized by paths as $T$ varies over trees on a fixed number of vertices. We introduce the term Hoffman-London to refer to graphs that are minimal in this sense. In particular, we define an automorphic similarity matrix which is used to compute $\hom(T,H)$ and give matrix conditions under which $H$ is Hoffman-London. We then apply this technique to identify several families of graphs that are Hoffman-London, including loop threshold graphs and some with applications in statistical physics (e.g. the Widom-Rowlinson model). By combining our approach with a few other observations, we fully characterize the minimizing trees for all graphs $H$ on three or fewer vertices.

preprint2022arXiv

Non-trivial squares and Sidorenko's conjecture

Let $t(H;G)$ be the homomorphism density of a graph $H$ into a graph $G$ . Sidorenko's conjecture states that for any bipartite graph $H$ , $t(H;G)\geq t(K_2;G)^{|E(H)|}$ for all graphs $G$ . It is already known that such inequalities cannot be certified through the sums of squares method when $H$ is a so-called trivial square. In this paper, we investigate recent results about Sidorenko's conjecture and classify those involving trivial versus non-trivial squares. We then present some computational results. In particular, we categorize the bipartite graphs $H$ on at most 7 edges for which $t(H;G)\geq t(K_2;G)^{|E(H)|}$ has a sum of squares certificate. We then discuss other limitations for sums of squares proofs beyond trivial squares.

preprint2015arXiv

Graph decomposition and parity

Motivated by a recent extension of the zero-one law by Kolaitis and Kopparty, we study the distribution of the number of copies of a fixed disconnected graph in the random graph $G(n,p)$ . We use an idea of graph decompositions to give a sufficient condition for this distribution to tend to uniform modulo $q$ . We determine the asymptotic distribution of all fixed two-component graphs in $G(n,p)$ for all $q$ , and we give infinite families of many-component graphs with a uniform asymptotic distribution for all $q$ . We also prove a negative result, that no simple proof of uniform asymptotic distribution for arbitrary graphs exists.

preprint2015arXiv

Modular statistics for subgraph counts in sparse random graphs

Answering a question of Kolaitis and Kopparty, we show that, for given integer $q>1$ and pairwise nonisomorphic connected graphs $G_1...G_k$ , if $p=p(n)$ is such that $\Pr(G_{n,p}\supseteq G_i)\to 1$ $\forall i$ , then, with $ξ_i$ the number of copies of $G_i$ in $G_{n,p}$ , $(ξ_1...ξ_k)$ is asymptotically uniformly distributed on ${\bf Z}_q^k$ .

preprint2013arXiv

Remarks on Combinatorial Aspects of the KP Equation

We survey several results connecting combinatorics and Wronskian solutions of the KP equation, contextualizing the successes of a recent approach introduced by Kodama, et. al. We include the necessary combinatorial and analytical background to present a formula for generalized KP solitons, compute several explicit examples, and indicate how such a perspective could be used to extend previous research relating line-soliton solutions of the KP equation with Grassmannians.

preprint2013arXiv

Unbalanced Allocations

We consider the unbalanced allocation of $m$ balls into $n$ bins by a randomized algorithm using the "power of two choices". For each ball, we select a set of bins at random, then place the ball in the fullest bin within the set. Applications of this generic algorithm range from cost minimization to condensed matter physics. In this paper, we analyze the distribution of the bin loads produced by this algorithm, considering, for example, largest and smallest loads, loads of subsets of the bins, and the likelihood of bins having equal loads.

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.

Amanda Redlich

Research overview

Is this your work?

6 publications

Hoffman-London graphs: When paths minimize $H$ -colorings among trees

Non-trivial squares and Sidorenko's conjecture

Graph decomposition and parity

Modular statistics for subgraph counts in sparse random graphs

Remarks on Combinatorial Aspects of the KP Equation

Unbalanced Allocations

See the researcher in context

Building this map preview

Amanda Redlich

Research overview

Is this your work?

6 publications

Hoffman-London graphs: When paths minimize HHH-colorings among trees

Non-trivial squares and Sidorenko's conjecture

Graph decomposition and parity

Modular statistics for subgraph counts in sparse random graphs

Remarks on Combinatorial Aspects of the KP Equation

Unbalanced Allocations

See the researcher in context

Building this map preview

Hoffman-London graphs: When paths minimize $H$ -colorings among trees