Source author record

Kevin G. Milans

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

Catalog footprint

Research overview

8works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

Tight paths in fully directed hypergraphs

It is well-known that every tournament has a spanning path. We consider hypergraph analogues. In an \emph{ $r$ -uniform fully directed hypergraph}, or \emph{ $r$ -digraph}, every edge is a list or $r$ distinct vertices. An $(r,k)$ -tournament is an $r$ -digraph $G$ such that for every $r$ -set $S$ of vertices in $G$ , exactly $k$ of the orderings of $S$ are edges in $G$ . A \emph{directed tight path} is an $r$ -digraph $G$ whose vertices can be ordered so that the intervals of size $r$ are the edges in $G$ . Let $f(n,r,k)$ be the maximum $s$ such that every $n$ -vertex $(r,k)$ -tournament contains a tight path on $s$ vertices. Since every tournament has a spanning path, we have $f(n,2,1)=n$ . In this paper, we show that the minimum $k$ such that $f(n,r,k)$ tends to infinity with $n$ is in the interval $\left[\left(1-\frac{1}{r}-O(\frac{\log r}{r^2\log\log r})\right)r!, ~\left(1-\frac{1}{r} - \frac{φ(r)-1}{r!}\right)r!\right]$ where $φ(r)$ is the Euler Totient Function, and we find the exact value when $r\le 5$ . We also show that $Ω(\sqrt{\log n/\log \log n}) \le f(n,3,3) \le O(\log n)$ and $f(n,3,4)\ge Ω(n^{1/5})$ .

preprint2016arXiv

The 2-Ranking Numbers of Graphs

In a graph whose vertices are assigned integer ranks, a path is well-ranked if the endpoints have distinct ranks or some interior point has a higher rank than the endpoints. A ranking is an assignment of ranks such that all nontrivial paths are well-ranked. A $k$ -ranking is a relaxation in which all nontrivial paths of length at most $k$ are well-ranked. The $k$ -ranking number of a graph $G$ is the minimum $t$ such that there is a $k$ -ranking of $G$ using ranks in $\{1,\ldots,t\}$ . We prove that the $2$ -ranking number of the $n$ -dimensional hypercube $Q_n$ is $n+1$ . As a corollary, we improve the bounds on the star chromatic number of products of cycles when each cycle has length divisible by $4$ . For $m\le n$ , we show that the $2$ -ranking number of $K_m \mathop\square K_n$ is $Ω(n\log m)$ and $O(nm^{\log_2(3)-1})$ with an asymptotic result when $m$ is constant and an exact result when $m!$ divides $n$ . We prove that every subcubic graph has $2$ -ranking number at most $7$ , and we also prove the existence of a graph with maximum degree $k$ and $2$ -ranking number $Ω(k^2/\log(k))$ .

preprint2015arXiv

Monotone Paths in Dense Edge-Ordered Graphs

The altitude of a graph $G$ , denoted $f(G)$ , is the largest integer $k$ such that under each ordering of $E(G)$ , there exists a path of length $k$ which traverses edges in increasing order. In 1971, Chvátal and Komlós asked for $f(K_n)$ , where $K_n$ is the complete graph on $n$ vertices. In 1973, Graham and Kleitman proved that $f(K_n) \ge \sqrt{n - 3/4} - 1/2$ and in 1984, Calderbank, Chung, and Sturtevant proved that $f(K_n) \le (\frac{1}{2} + o(1))n$ . We show that $f(K_n) \ge (\frac{1}{20} - o(1))(n/\lg n)^{2/3}$ .

preprint2015arXiv

Tree-width and dimension

Over the last 30 years, researchers have investigated connections between dimension for posets and planarity for graphs. Here we extend this line of research to the structural graph theory parameter tree-width by proving that the dimension of a finite poset is bounded in terms of its height and the tree-width of its cover graph.

preprint2014arXiv

Set families with forbidden subposets

Let $F$ be a family of subsets of $\{1,\ldots,n\}$ . We say that $F$ is $P$ -free if the inclusion order on $F$ does not contain $P$ as an induced subposet. The \emph{Turán function} of $P$ , denoted $π^*(n,P)$ , is the maximum size of a $P$ -free family of subsets of $\{1,\ldots,n\}$ . We show that $π^*(n,P) \le (4r + O(\sqrt{r}))\binom{n}{n/2}$ if $P$ is an $r$ -element poset of height at most $2$ . We also show that $π^*(n,S_r) = (r+O(\sqrt{r}))\binom{n}{n/2}$ where $S_r$ is the standard example on $2r$ elements, and that $π^*(n,B_2) \le (2.583+o(1))\binom{n}{n/2}$ , where $B_2$ is the $2$ -dimensional Boolean lattice.

preprint2013arXiv

Boolean algebras and Lubell functions

Let $2^{[n]}$ denote the power set of $[n]:=\{1,2,..., n\}$ . A collection $\B\subset 2^{[n]}$ forms a $d$ -dimensional {\em Boolean algebra} if there exist pairwise disjoint sets $X_0, X_1,..., X_d \subseteq [n]$ , all non-empty with perhaps the exception of $X_0$ , so that $\B={X_0\cup \bigcup_{i\in I} X_i\colon I\subseteq [d]}$. Let $b(n,d)$ be the maximum cardinality of a family $\F\subset 2^X$ that does not contain a $d$ -dimensional Boolean algebra. Gunderson, Rödl, and Sidorenko proved that $b(n,d) \leq c_d n^{-1/2^d} \cdot 2^n$ where $c_d= 10^d 2^{-2^{1-d}}d^{d-2^{-d}}$ . In this paper, we use the Lubell function as a new measurement for large families instead of cardinality. The Lubell value of a family of sets $\F$ with $\F\subseteq \tsupn$ is defined by $h_n(\F):=\sum_{F\in \F}1/{n\choose |F|}$. We prove the following Turán type theorem. If $\F\subseteq 2^{[n]}$ contains no $d$ -dimensional Boolean algebra, then $h_n(\F)\leq 2(n+1)^{1-2^{1-d}}$ for sufficiently large $n$ . This results implies $b(n,d) \leq C n^{-1/2^d} \cdot 2^n$ , where $C$ is an absolute constant independent of $n$ and $d$ . As a consequence, we improve several Ramsey-type bounds on Boolean algebras. We also prove a canonical Ramsey theorem for Boolean algebras.

preprint2011arXiv

Chain-making games in grid-like posets

We study the Maker-Breaker game on the hypergraph of chains of fixed size in a poset. In a product of chains, the maximum size of a chain that Maker can guarantee building is $k-\lfloor r/2\rfloor$ , where $k$ is the maximum size of a chain in the product, and $r$ is the maximum size of a factor chain. We also study a variant in which Maker must follow the chain in order, called the {\it Walker-Blocker game}. In the poset consisting of the bottom $k$ levels of the product of $d$ arbitrarily long chains, Walker can guarantee a chain that hits all levels if $d\ge14$ ; this result uses a solution to Conway's Angel-Devil game. When d=2, the maximum that Walker can guarantee is only 2/3 of the levels, and 2/3 is asymptotically achievable in the product of two equal chains.

preprint2010arXiv

First-Fit is Linear on Posets Excluding Two Long Incomparable Chains

A poset is (r + s)-free if it does not contain two incomparable chains of size r and s, respectively. We prove that when r and s are at least 2, the First-Fit algorithm partitions every (r + s)-free poset P into at most 8(r-1)(s-1)w chains, where w is the width of P. This solves an open problem of Bosek, Krawczyk, and Szczypka (SIAM J. Discrete Math., 23(4):1992--1999, 2010).

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.