Source author record

Nathan Lemons

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 Applications Computational Geometry math.PR physics.data-an physics.soc-ph Social and Information Networks Systems and Control

Catalog footprint

Research overview

8works

9topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Induced and non-induced poset saturation problems

A subfamily $\mathcal{G}\subseteq \mathcal{F}\subseteq 2^{[n]}$ of sets is a non-induced (weak) copy of a poset $P$ in $\mathcal{F}$ if there exists a bijection $i:P\rightarrow \mathcal{G}$ such that $p\le_P q$ implies $i(p)\subseteq i(q)$ . In the case where in addition $p\le_P q$ holds if and only if $i(p)\subseteq i(q)$ , then $\mathcal{G}$ is an induced (strong) copy of $P$ in $\mathcal{F}$ . We consider the minimum number $sat(n,P)$ [resp.\ $sat^*(n,P)$ ] of sets that a family $\mathcal{F}\subseteq 2^{[n]}$ can have without containing a non-induced [induced] copy of $P$ and being maximal with respect to this property, i.e., the addition of any $G\in 2^{[n]}\setminus \mathcal{F}$ creates a non-induced [induced] copy of $P$ . We prove for any finite poset $P$ that $sat(n,P)\le 2^{|P|-2}$ , a bound independent of the size $n$ of the ground set. For induced copies of $P$ , there is a dichotomy: for any poset $P$ either $sat^*(n,P)\le K_P$ for some constant depending only on $P$ or $sat^*(n,P)\ge \log_2 n$ . We classify several posets according to this dichotomy, and also show better upper and lower bounds on $sat(n,P)$ and $sat^*(n,P)$ for specific classes of posets. Our main new tool is a special ordering of the sets based on the colexicographic order. It turns out that if $P$ is given, processing the sets in this order and adding the sets greedily into our family whenever this does not ruin non-induced [induced] $P$ -freeness, we tend to get a small size non-induced [induced] $P$ -saturating family.

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.

preprint2016arXiv

Detection of Cyber-Physical Faults and Intrusions from Physical Correlations

Cyber-physical systems are critical infrastructures that are crucial both to the reliable delivery of resources such as energy, and to the stable functioning of automatic and control architectures. These systems are composed of interdependent physical, control and communications networks described by disparate mathematical models creating scientific challenges that go well beyond the modeling and analysis of the individual networks. A key challenge in cyber-physical defense is a fast online detection and localization of faults and intrusions without prior knowledge of the failure type. We describe a set of techniques for the efficient identification of faults from correlations in physical signals, assuming only a minimal amount of available system information. The performance of our detection method is illustrated on data collected from a large building automation system.

preprint2015arXiv

Online and quasi-online colorings of wedges and intervals

We consider proper online colorings of hypergraphs defined by geometric regions. We prove that there is an online coloring algorithm that colors $N$ intervals of the real line using $Θ(\log N/k)$ colors such that for every point $p$ , contained in at least $k$ intervals, not all the intervals containing $p$ have the same color. We also prove the corresponding result about online coloring a family of wedges (quadrants) in the plane that are the translates of a given fixed wedge. These results contrast the results of the first and third author showing that in the quasi-online setting 12 colors are enough to color wedges (independent of $N$ and $k$ ). We also consider quasi-online coloring of intervals. In all cases we present efficient coloring algorithms.

preprint2013arXiv

The phase transition in inhomogeneous random intersection graphs

We analyze the component evolution in inhomogeneous random intersection graphs when the average degree is close to 1. As the average degree increases, the size of the largest component in the random intersection graph goes through a phase transition. We give bounds on the size of the largest components before and after this transition. We also prove that the largest component after the transition is unique. These results are similar to the phase transition in Erdős-Rényi random graphs; one notable difference is that the jump in the size of the largest component varies in size depending on the parameters of the random intersection graph.

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

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.

Nathan Lemons

Research overview

Is this your work?

8 publications

Induced and non-induced poset saturation problems

Maximum size intersecting families of bounded minimum positive co-degree

Detection of Cyber-Physical Faults and Intrusions from Physical Correlations

Online and quasi-online colorings of wedges and intervals

The phase transition in inhomogeneous random intersection graphs

Cross-Sperner families

Saturating Sperner families

Two-part set systems

See the researcher in context

Building this map preview