Source author record

Jonathan Cutler

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

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

7works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Homomorphisms into loop-threshold graphs

Many problems in extremal graph theory correspond to questions involving homomorphisms into a fixed image graph. Recently, there has been interest in maximizing the number of homomorphisms from graphs with a fixed number of vertices and edges into small image graphs. For the image graph $H_{\text{ind}}$ , the graph on two adjacent vertices, one of which is looped, each homomorphism from $G$ to $H_{\text{ind}}$ corresponds to an independent set in $G$ . It follows from the Kruskal-Katona theorem that the number of homomorphisms to $H_{\text{ind}}$ is maximized by the lex graph, whose edges form an initial segment of the lex order. A \emph{loop-threshold graph} is a graph built recursively from a single vertex, which may be looped or unlooped, by successively adding either a looped dominating vertex or an unlooped isolated vertex at each stage. Thus, the graph $H_{\text{ind}}$ is a loop-threshold graph. We survey known results for maximizing the number of homomorphisms into small loop-threshold image graphs. The only extremal homomorphism problem with a loop-threshold image graph on at most three vertices not yet solved is $H_{\text{ind}}\cup E_1$ , where extremal graphs are the union of a lex graph and an empty graph. The only question that remains is the size of the lex component of the extremal graph. While we cannot give an exact answer for every number of vertices and edges, we establish the significance of and give a bound for $\ell(m)$ , the number of vertices in the lex component of the extremal graph with $m$ edges and at least $m+1$ vertices.

preprint2016arXiv

Minimizing the number of independent sets in triangle-free regular graphs

Recently, Davies, Jenssen, Perkins, and Roberts gave a very nice proof of the result (due, in various parts, to Kahn, Galvin-Tetali, and Zhao) that the independence polynomial of a $d$ -regular graph is maximized by disjoint copies of $K_{d,d}$ . Their proof uses linear programming bounds on the distribution of a cleverly chosen random variable. In this paper, we use this method to give lower bounds on the independence polynomial of regular graphs. We also give new bounds on the number of independent sets in triangle-free regular graphs.

preprint2015arXiv

Counting dominating sets and related structures in graphs

We consider some problems concerning the maximum number of (strong) dominating sets in a regular graph, and their weighted analogues. Our primary tool is Shearer's entropy lemma. These techniques extend to a reasonably broad class of graph parameters enumerating vertex colorings satisfying conditions on the multiset of colors appearing in (closed) neighborhoods. We also generalize further to enumeration problems for what we call existence homomorphisms. Here our results are substantially less complete, though we do solve some natural problems.

preprint2014arXiv

A note on the values of independence polynomials at $-1$

The independence polynomial $I(G;x)$ of a graph $G$ is $I(G;x)=\sum_{k=1}^{α(G)} s_k x^k$ , where $s_k$ is the number of independent sets in $G$ of size $k$ . The decycling number of a graph $G$ , denoted $ϕ(G)$ , is the minimum size of a set $S\subseteq V(G)$ such that $G-S$ is acyclic. Engström proved that the independence polynomial satisfies $|I(G;-1)| \leq 2^{ϕ(G)}$ for any graph $G$ , and this bound is best possible. Levit and Mandrescu provided an elementary proof of the bound, and in addition conjectured that for every positive integer $k$ and integer $q$ with $|q|\leq 2^k$ , there is a connected graph $G$ with $ϕ(G)=k$ and $I(G;-1)=q$ . In this note, we prove this conjecture.

preprint2014arXiv

Maximal-clique partitions and the Roller Coaster Conjecture

A graph $G$ is {\em well-covered} if every maximal independent set has the same cardinality $q$ . Let $i_k(G)$ denote the number of independent sets of cardinality $k$ in $G$ . Brown, Dilcher, and Nowakowski conjectured that the independence sequence $(i_0(G), i_1(G), \ldots, i_q(G))$ was unimodal for any well-ordered graph $G$ with independence number $q$ . Michael and Traves disproved this conjecture. Instead they posited the so-called ``Roller Coaster" Conjecture: that the terms $i_{\left\lceil\frac{q}2\right\rceil}(G), i_{\left\lceil\frac{q}2\right\rceil+1}(G), \ldots, i_q(G)$ could be in any specified order for some well-covered graph $G$ with independence number $q$ . Michael and Traves proved the conjecture for $q<8$ and Matchett extended this to $q<12$ . In this paper, we prove the Roller Coaster Conjecture using a construction of graphs with a property related to that of having a maximal-clique partition. In particular, we show, for all pairs of integers $1\le k<q$ and positive integers $m$ , that there is a well-covered graph $G$ with independence number $q$ for which every independent set of size $k+1$ is contained in a unique maximal independent set, but each independent set of size $k$ is contained in at least $m$ distinct independent sets.

preprint2014arXiv

The maximum number of complete subgraphs of fixed size in a graph with given maximum degree

In this paper, we make progress on a question related to one of Galvin that has attracted substantial attention recently. The question is that of determining among all graphs $G$ with $n$ vertices and $Δ(G)\leq r$ , which has the most complete subgraphs of size $t$ , for $t\geq 3$ . The conjectured extremal graph is $aK_{r+1}\cup K_b$ , where $n=a(r+1)+b$ with $0\leq b\leq r$ . Gan, Loh, and Sudakov proved the conjecture when $a\leq 1$ , and also reduced the general conjecture to the case $t=3$ . We prove the conjecture for $r\leq 6$ and also establish a weaker form of the conjecture for all $r$ .

preprint2013arXiv

The maximum number of complete subgraphs in a graph with given maximum degree

Extremal problems involving the enumeration of graph substructures have a long history in graph theory. For example, the number of independent sets in a $d$ -regular graph on $n$ vertices is at most $(2^{d+1}-1)^{n/2d}$ by the Kahn-Zhao theorem. Relaxing the regularity constraint to a minimum degree condition, Galvin conjectured that, for $n\geq 2d$ , the number of independent sets in a graph with $δ(G)\geq d$ is at most that in $K_{d,n-d}$ . In this paper, we give a lower bound on the number of independent sets in a $d$ -regular graph mirroring the upper bound in the Kahn-Zhao theorem. The main result of this paper is a proof of a strengthened form of Galvin's conjecture, covering the case $n\leq 2d$ as well. We find it convenient to address this problem from the perspective of $\complement{G}$ . In other words, we give an upper bound on the number of complete subgraphs of a graph $G$ on $n$ vertices with $Δ(G)\leq r$ , valid for all values of $n$ and $r$ .

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.

Jonathan Cutler

Research overview

Is this your work?

7 publications

Homomorphisms into loop-threshold graphs

Minimizing the number of independent sets in triangle-free regular graphs

Counting dominating sets and related structures in graphs

A note on the values of independence polynomials at $-1$

Maximal-clique partitions and the Roller Coaster Conjecture

The maximum number of complete subgraphs of fixed size in a graph with given maximum degree

The maximum number of complete subgraphs in a graph with given maximum degree

See the researcher in context

Building this map preview

Jonathan Cutler

Research overview

Is this your work?

7 publications

Homomorphisms into loop-threshold graphs

Minimizing the number of independent sets in triangle-free regular graphs

Counting dominating sets and related structures in graphs

A note on the values of independence polynomials at −1-1−1

Maximal-clique partitions and the Roller Coaster Conjecture

The maximum number of complete subgraphs of fixed size in a graph with given maximum degree

The maximum number of complete subgraphs in a graph with given maximum degree

See the researcher in context

Building this map preview

A note on the values of independence polynomials at $-1$