Source author record

Cory Palmer

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

16works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

On the number of maximal independent sets: From Moon-Moser to Hujter-Tuza

We connect two classical results in extremal graph theory concerning the number of maximal independent sets. The maximum number mis $(n)$ of maximal independent sets in an $n$ -vertex graph was determined by Moon and Moser. The maximum number mis $_\bigtriangleup(n)$ of maximal independent sets in an $n$ -vertex triangle-free graph was determined by Hujter and Tuza. We determine the maximum number mis $_t(n)$ of maximal independent sets in an $n$ -vertex graph containing no induced triangle matching of size $t+1$ . We also reprove a stability result of Kahn and Park on the maximum number mis $_{\bigtriangleup,t}(n)$ of maximal independent sets in an $n$ -vertex triangle-free graphs containing no induced matching of size $t+1$ .

preprint2021arXiv

Maximum size intersecting families of bounded minimum positive co-degree

Let $\mathcal{H}$ be an $r$ -uniform hypergraph. The \emph{minimum positive co-degree} of $\mathcal{H}$ , denoted by $δ_{r-1}^+(\mathcal{H})$ , is the minimum $k$ such that if $S$ is an $(r-1)$ -set contained in a hyperedge of $\mathcal{H}$ , then $S$ is contained in at least $k$ hyperedges of $\mathcal{H}$ . For $r\geq k$ fixed and $n$ sufficiently large, we determine the maximum possible size of an intersecting $r$ -uniform $n$ -vertex hypergraph with minimum positive co-degree $δ_{r-1}^+(\mathcal{H}) \geq k$ and characterize the unique hypergraph attaining this maximum. This generalizes the Erd\H os-Ko-Rado theorem which corresponds to the case $k=1$ . Our proof is based on the delta-system method.

preprint2020arXiv

Rainbow cycles vs. rainbow paths

An edge-colored graph $F$ is {\it rainbow} if each edge of $F$ has a unique color. The {\it rainbow Turán number} $\mathrm{ex}^*(n,F)$ of a graph $F$ is the maximum possible number of edges in a properly edge-colored $n$ -vertex graph with no rainbow copy of $F$ . The study of rainbow Turán numbers was introduced by Keevash, Mubayi, Sudakov, and Verstraëte. Johnson and Rombach introduced the following rainbow-version of generalized Turán problems: for fixed graphs $H$ and $F$ , let $\mathrm{ex}^*(n,H,F)$ denote the maximum number of rainbow copies of $H$ in an $n$ -vertex properly edge-colored graph with no rainbow copy of $F$ . In this paper we investigate the case $\mathrm{ex}^*(n,C_\ell,P_\ell)$ and give a general upper bound as well as exact results for $\ell = 3,4,5$ . Along the way we establish a new best upper bound on $\mathrm{ex}^*(n,P_5)$ . Our main motivation comes from an attempt to improve bounds on $\mathrm{ex}^*(n,P_\ell)$ , which has been the subject of several recent manuscripts.

preprint2020arXiv

Some exact results for generalized Turán problems

Fix a $k$ -chromatic graph $F$ . In this paper we consider the question to determine for which graphs $H$ does the Turán graph $T_{k-1}(n)$ have the maximum number of copies of $H$ among all $n$ -vertex $F$ -free graphs (for $n$ large enough). We say that such a graph $H$ is $F$ -Turán-good. In addition to some general results, we give (among others) the following concrete results: (i) For every complete multipartite graph $H$ , there is $k$ large enough such that $H$ is $K_k$ -Turán-good. (ii) The path $P_3$ is $F$ -Turán-good for $F$ with $χ(F) \geq 4$ . (iii) The path $P_4$ and cycle $C_4$ are $C_5$ -Turán-good. (iv) The cycle $C_4$ is $F_2$ -Turán-good where $F_2$ is the graph of two triangles sharing exactly one vertex.

preprint2020arXiv

Turán numbers for hypergraph star forests

Fix a graph $F$ . We say that a graph is {\it $F$ -free} if it does not contain $F$ as a subgraph. The {\it Turán number} of $F$ , denoted $\mathrm{ex}(n,F)$ , is the maximum number of edges possible in an $n$ -vertex $F$ -free graph. The study of Turán numbers is a central problem in graph theory. The goal of this paper is to generalize a theorem of Lidický, Liu and Palmer [{\it Electron.\ J.\ of Combin.}\ {\bf 20} (2016)] that determines $\mathrm{ex}(n,F)$ for $F$ a forest of stars. In particular, we consider generalizations of the problem to three different well-studied hypergraph settings and in each case we prove an asymptotic result for all reasonable parameters defining our "star forests".

preprint2016arXiv

On the number of cycles in a graph with restricted cycle lengths

Let $L$ be a set of positive integers. We call a (directed) graph $G$ an $L$ \emph{-cycle graph} if all cycle lengths in $G$ belong to $L$ . Let $c(L,n)$ be the maximum number of cycles possible in an $n$ -vertex $L$ -cycle graph (we use $\vec{c}(L,n)$ for the number of cycles in directed graphs). In the undirected case we show that for any fixed set $L$ , we have $c(L,n)=Θ_L(n^{\lfloor k/\ell \rfloor})$ where $k$ is the largest element of $L$ and $2\ell$ is the smallest even element of $L$ (if $L$ contains only odd elements, then $c(L,n)=Θ_L(n)$ holds.) We also give a characterization of $L$ -cycle graphs when $L$ is a single element. In the directed case we prove that for any fixed set $L$ we have $\vec{c}(L,n)=(1+o(1))(\frac{n-1}{k-1})^{k-1}$ , where $k$ is the largest element of $L$ . We determine the exact value of $\vec{c}(\{k\},n)$ for every $k$ and characterize all graphs attaining this maximum.

preprint2016arXiv

Rainbow Turán problems for paths and forests of stars

For a fixed graph $F$ , we would like to determine the maximum number of edges in a properly edge-colored graph on $n$ vertices which does not contain a {\emph rainbow copy} of $F$ , that is, a copy of $F$ all of whose edges receive a different color. This maximum, denoted by $ex^*(n,F)$ , is the {\emph rainbow Turán number} of $F$ , and its systematic study was initiated by Keevash, Mubayi, Sudakov and Verstraëte in 2007. We determine $ex^*(n,F)$ exactly when $F$ is a forest of stars, and give bounds on $ex^*(n,F)$ when $F$ is a path with $k$ edges, disproving a conjecture in Keevash et al.

preprint2016arXiv

Topological orderings of weighted directed acyclic graphs

We call a topological ordering of a weighted directed acyclic graph non-negative if the sum of weights on the vertices in any prefix of the ordering is non-negative. We investigate two processes for constructing non-negative topological orderings of weighted directed acyclic graphs. The first process is called a mark sequence and the second is a generalization called a mark-unmark sequence. We answer a question of Erickson by showing that every non-negative topological ordering that can be realized by a mark-unmark sequence can also be realized by a mark sequence. We also investigate the question of whether a given weighted directed acyclic graph has a non-negative topological ordering. We show that even in the simple case when every vertex is a source or a sink the question is NP-complete.

preprint2015arXiv

Extremal results for Berge-hypergraphs

Let $G$ be a graph and $\mathcal{H}$ be a hypergraph both on the same vertex set. We say that a hypergraph $\mathcal{H}$ is a \emph{Berge}- $G$ if there is a bijection $f : E(G) \rightarrow E(\mathcal{H})$ such that for $e \in E(G)$ we have $e \subset f(e)$ . This generalizes the established definitions of "Berge path" and "Berge cycle" to general graphs. For a fixed graph $G$ we examine the maximum possible size (i.e.\ the sum of the cardinality of each edge) of a hypergraph with no Berge- $G$ as a subhypergraph. In the present paper we prove general bounds for this maximum when $G$ is an arbitrary graph. We also consider the specific case when $G$ is a complete bipartite graph and prove an analogue of the K\H ovári-Sós-Turán theorem.

preprint2013arXiv

The biased odd cycle game

In this paper we consider biased Maker-Breaker games played on the edge set of a given graph $G$ . We prove that for every $δ>0$ and large enough $n$ , there exists a constant $k$ for which if $δ(G)\geq δn$ and $χ(G)\geq k$ , then Maker can build an odd cycle in the $(1:b)$ game for $b=O(\frac{n}{\log^2 n})$ . We also consider the analogous game where Maker and Breaker claim vertices instead of edges. This is a special case of the following well known and notoriously difficult problem due to Duffus, Łuczak and Rödl: is it true that for any positive constants $t$ and $b$ , there exists an integer $k$ such that for every graph $G$ , if $χ(G)\geq k$ , then Maker can build a graph which is not $t$ -colorable, in the $(1:b)$ Maker-Breaker game played on the vertices of $G$ ?

preprint2012arXiv

On the tree packing conjecture

The Gyárfás tree packing conjecture states that any set of $n-1$ trees $T_{1},T_{2},..., T_{n-1}$ such that $T_i$ has $n-i+1$ vertices pack into $K_n$ . We show that $t=1/10n^{1/4}$ trees $T_1,T_2,..., T_t$ such that $T_i$ has $n-i+1$ vertices pack into $K_{n+1}$ (for $n$ large enough). We also prove that any set of $t=1/10n^{1/4}$ trees $T_1,T_2,..., T_t$ such that no tree is a star and $T_i$ has $n-i+1$ vertices pack into $K_{n}$ (for $n$ large enough). Finally, we prove that $t=1/4n^{1/3}$ trees $T_1,T_2,..., T_t$ such that $T_i$ has $n-i+1$ vertices pack into $K_n$ as long as each tree has maximum degree at least $2n^{2/3}$ (for $n$ large enough). One of the main tools used in the paper is the famous spanning tree embedding theorem of Komlós, Sárközy and Szemerédi.

preprint2012arXiv

On the Turan number of forests

The Turan number of a graph H, ex(n,H), is the maximum number of edges in a graph on n vertices which does not have H as a subgraph. We determine the Turan number and find the unique extremal graph for forests consisting of paths when n is sufficiently large. This generalizes a result of Bushaw and Kettle [ Combinatorics, Probability and Computing 20:837--853, 2011]. We also determine the Turan number and extremal graphs for forests consisting of stars of arbitrary order.

preprint2011arXiv

Cross-Sperner families

A pair of families $(\cF,\cG)$ is said to be \emph{cross-Sperner} if there exists no pair of sets $F \in \cF, G \in \cG$ with $F \subseteq G$ or $G \subseteq F$ . There are two ways to measure the size of the pair $(\cF,\cG)$: with the sum $|\cF|+|\cG|$ or with the product $|\cF|\cdot |\cG|$. We show that if $\cF, \cG \subseteq 2^{[n]}$, then $|\cF||\cG| \le 2^{2n-4}$ and $|\cF|+|\cG|$ is maximal if $\cF$ or $\cG$ consists of exactly one set of size $\lceil n/2 \rceil$ provided the size of the ground set $n$ is large enough and both $\cF$ and $\cG$ are non-empty.

preprint2011arXiv

Generalizations of the Tree Packing Conjecture

The Gyárfás tree packing conjecture asserts that any set of trees with $2,3, ..., k$ vertices has an (edge-disjoint) packing into the complete graph on $k$ vertices. Gyárfás and Lehel proved that the conjecture holds in some special cases. We address the problem of packing trees into $k$ -chromatic graphs. In particular, we prove that if all but three of the trees are stars then they have a packing into any $k$ -chromatic graph. We also consider several other generalizations of the conjecture.

preprint2011arXiv

Saturating Sperner families

A family $\cF \subseteq 2^{[n]}$ saturates the monotone decreasing property $\cP$ if $\cF$ satisfies $\cP$ and one cannot add any set to $\cF$ such that property $\cP$ is still satisfied by the resulting family. We address the problem of finding the minimum size of a family saturating the $k$ -Sperner property and the minimum size of a family that saturates the Sperner property and that consists only of $l$ -sets and $(l+1)$ -sets.

preprint2011arXiv

Two-part set systems

The two part Sperner theorem of Katona and Kleitman states that if $X$ is an $n$ -element set with partition $X_1 \cup X_2$ , and $\cF$ is a family of subsets of $X$ such that no two sets $A, B \in \cF$ satisfy $A \subset B$ (or $B \subset A$ ) and $A \cap X_i=B \cap X_i$ for some $i$ , then $|\cF| \le {n \choose \lfloor n/2 \rfloor}$. We consider variations of this problem by replacing the Sperner property with the intersection property and considering families that satisfiy various combinations of these properties on one or both parts $X_1$ , $X_2$ . Along the way, we prove the following new result which may be of independent interest: let $\cF, \cG$ be families of subsets of an $n$ -element set such that $\cF$ and $\cG$ are both intersecting and cross-Sperner, meaning that if $A \in \cF$ and $B \in \cG$, then $A \not\subset B$ and $B \not\subset A$ . Then $|\cF| +|\cG| < 2^{n-1}$ and there are exponentially many examples showing that this bound is tight.

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.

Cory Palmer

Research overview

Is this your work?

16 publications

On the number of maximal independent sets: From Moon-Moser to Hujter-Tuza

Maximum size intersecting families of bounded minimum positive co-degree

Rainbow cycles vs. rainbow paths

Some exact results for generalized Turán problems

Turán numbers for hypergraph star forests

On the number of cycles in a graph with restricted cycle lengths

Rainbow Turán problems for paths and forests of stars

Topological orderings of weighted directed acyclic graphs

Extremal results for Berge-hypergraphs

The biased odd cycle game

On the tree packing conjecture

On the Turan number of forests

Cross-Sperner families

Generalizations of the Tree Packing Conjecture

Saturating Sperner families

Two-part set systems

See the researcher in context

Building this map preview