Search

Given a poset P , a family F of elements in the Boolean lattice is said to be P -saturated if (1) F contains no copy of P as a subposet and (2) every proper superset of F contains a copy of P as a subposet. The maximum size of a P -saturated family is denoted by La ( n , P ) , which has been studied for a number of choices of P . The minimum size of a P -saturated family, sat ( n , P ) , was introduced by Gerbner et al. (2013), and parallels the deep literature on the saturation function for graphs. We introduce and study the concept of saturation for induced subposets. As opposed to induced saturation in graphs, the above definition of saturation for posets extends naturally to the induced setting. We give several exact results and a number of bounds on the induced saturation number for several small posets. We also use a transformation to the biclique cover problem to prove a logarithmic lower bound for a rich infinite family of target posets.

Let π 1 = ( d 1 ( 1 ) , … , d n ( 1 ) ) and π 2 = ( d 1 ( 2 ) , … , d n ( 2 ) ) be graphic sequences. We say they pack if there exist edge-disjoint realizations G 1 and G 2 of π 1 and π 2 , respectively, on vertex set { v 1 , … , v n } such that for j ∈ { 1 , 2 } , d G j ( v i ) = d i ( j ) for all i ∈ { 1 , … , n } . In this case, we say that ( G 1 , G 2 ) is a ( π 1 , π 2 ) -packing. A clear necessary condition for graphic sequences π 1 and π 2 to pack is that π 1 + π 2 , their componentwise sum, is also graphic. It is known, however, that this condition is not sufficient, and furthermore that the general problem of determining if two sequences pack is N P -complete. S. Kundu proved in 1973 that if π 2 is almost regular, that is each element is from { k − 1 , k } , then π 1 and π 2 pack if and only if π 1 + π 2 is graphic. In this paper we will consider graphic sequences π with the property that π + 1 is graphic. By Kundu’s theorem, the sequences π and 1 pack, and there exist edge-disjoint realizations G and I , where I is a 1-factor. We call such a ( π , 1 ) packing a Kundu realization. Assume that π is a graphic sequence, in which each term is at most n ∕ 24 , that packs with 1 . This paper contains two results. On one hand, any two Kundu realizations of the degree sequence π + 1 can be transformed into each other through a sequence of other Kundu realizations by swap operations. On the other hand, the same conditions ensure that any particular 1-factor can be part of a Kundu realization of π + 1 .

The distinguishing number of a graph G , denoted D ( G ) , is the minimum number of colors needed to produce a coloring of the vertices of G so that every nontrivial automorphism interchanges vertices of different colors. A list assignment L on a graph G is a function that assigns each vertex of G a set of colors. An L -coloring of G is a coloring in which each vertex is colored with a color from L ( v ) . The list distinguishing number of G , denoted D l ( G ) is the minimum k such that every list assignment L that assigns a list of size at least k to every vertex permits a distinguishing L -coloring. In this paper, we prove that when n is large enough, the distinguishing and list-distinguishing numbers of K n □ K m agree for almost all m > n , and otherwise differ by at most one. As a part of our proof, we give (to our knowledge) the first application of the Combinatorial Nullstellensatz to setting of distinguishing graph colorings and also prove an inequality for the binomial distribution that may be of independent interest.

A star $k$-coloring is a proper $k$-coloring where the union of two color classes induces a star forest. While every planar graph is 4-colorable, not every planar graph is star 4-colorable. One method to produce a star 4-coloring is to partition the vertex set into a 2-independent set and a forest; such a partition is called an I,F-partition. We use a combination of potential functions and discharging to prove that every graph with maximum average degree less than $\frac{5}{2}$ has an I,F-partition, which is sharp and answers a question of Cranston and West [A guide to the discharging method, arXiv:1306.4434]. This result implies that planar graphs of girth at least 10 are star 4-colorable, improving upon previous results of Bu, Cranston, Montassier, Raspaud, and Wang [Star coloring of sparse graphs, J. Graph Theory 62 (2009), 201-219]., Comment: 11 pages, 6 figures

Let $G$ be a fixed graph and let ${\mathcal F}$ be a family of graphs. A subgraph $J$ of $G$ is ${\mathcal F}$-saturated if no member of ${\mathcal F}$ is a subgraph of $J$, but for any edge $e$ in $E(G)-E(J)$, some element of ${\mathcal F}$ is a subgraph of $J+e$. We let $\text{ex}({\mathcal F},G)$ and $\text{sat}({\mathcal F},G)$ denote the maximum and minimum size of an ${\mathcal F}$-saturated subgraph of $G$, respectively. If no element of ${\mathcal F}$ is a subgraph of $G$, then $\text{sat}({\mathcal F},G) = \text{ex}({\mathcal F}, G) = |E(G)|$. In this paper, for $k\ge 3$ and $n\ge 100$ we determine $\text{sat}(K_3,K_k^n)$, where $K_k^n$ is the complete balanced $k$-partite graph with partite sets of size $n$. We also give several families of constructions of $K_t$-saturated subgraphs of $K_k^n$ for $t\ge 4$. Our results and constructions provide an informative contrast to recent results on the edge-density version of $\text{ex}(K_t,K_k^n)$ from [A. Bondy, J. Shen, S. Thomass\'e, and C. Thomassen, Density conditions for triangles in multipartite graphs, Combinatorica 26 (2006), 121--131] and [F. Pfender, Complete subgraphs in multipartite graphs, Combinatorica 32 (2012), no. 4, 483--495]., Comment: 16 pages, 4 figures

Given a group $\Gamma$ acting on a set $X$, a $k$-coloring $\phi:X\to\{1,\dots,k\}$ of $X$ is distinguishing with respect to $\Gamma$ if the only $\gamma\in \Gamma$ that fixes $\phi$ is the identity action. The distinguishing number of the action $\Gamma$, denoted $D_{\Gamma}(X)$, is then the smallest positive integer $k$ such that there is a distinguishing $k$-coloring of $X$ with respect to $\Gamma$. This notion has been studied in a number of settings, but by far the largest body of work has been concerned with finding the distinguishing number of the action of the automorphism group of a graph $G$ upon its vertex set, which is referred to as the distinguishing number of $G$. The distinguishing number of a group action is a measure of how difficult it is to "break" all of the permutations arising from that action. In this paper, we aim to further differentiate the resilience of group actions with the same distinguishing number. In particular, we introduce a precoloring extension framework to address this issue. A set $S \subseteq X$ is a fixing set for $\Gamma$ if for every non-identity element $\gamma \in \Gamma$ there is an element $s \in S$ such that $\gamma(s) \neq s$. The distinguishing extension number $\operatorname{ext}_D(X,\Gamma;k)$ is the minimum number $m$ such that for all fixing sets $W \subseteq X$ with $|W| \geq m$, every $k$-coloring $c : X \setminus W \to [k]$ can be extended to a $k$-coloring that distinguishes $X$. In this paper, we prove that $\operatorname{ext}_D(\mathbb{R},\operatorname{Aut}(\mathbb{R}),2) =4$, where $\operatorname{Aut}(\mathbb{R})$ is comprised of compositions of translations and reflections. We also consider the distinguishing extension number of the circle and (finite) cycles, obtaining several exact results and bounds., Comment: 21 pages, 4 figures