KPPY 98

Given a hypergraph $H=(V,E)$, we say that $H$ is (weakly) $m$-colorable if there is a coloring $c:V\to [m]$ such that every hyperedge of $H$ is not monochromatic. The (weak) chromatic number of $H$, denoted by $\chi(H)$, is the smallest $m$ such that $H$ is $m$-colorable. A vertex subset $T \subseteq V$ is called a transversal of $H$ if for every hyperedge $e$ of $H$ we have $T\cap e \ne \emptyset$. The transversal number of $H$, denoted by $\tau(H)$, is the smallest size of a transversal in $H$. The transversal ratio of $H$ is the quantity $\tau(H)/|V|$ which is between 0 and 1. Since a lower bound on the transversal ratio of $H$ gives a lower bound on $\chi(H)$, these two quantities are closely related to each other.

We present constructions of geometric hypergraphs with high chromatic number and(or) transveral ratio. The ultimate conjecture on this line asks for a construction of $d$-polytopes for every $d\geq 4$ such that the supremum among the transversal ratios of the facet hypergraphs of those $d$-polytopes is eqaul to 1. As intermediate steps towards the conjecture, we will consider constructions regarding transversals and colorings coming from various types of simplicial complexes - neighborly spheres, simplicial complexes which are piecewise-linearly (or geometrically) embeddable in $\mathbb{R}^d$ and so on.

This presentation is based on the two joint work; one with Joseph Briggs and Michael Gene Dobbins, and the other with Eran Nevo.

We say that two functors $\Lambda$ and $\Gamma$ between thin categories of relational structures are adjoint if for all structures $A$ and $B$, we have that $\Lambda(A)$ maps homomorphically to B if and only if A maps homomorphically to $\Gamma(B)$. If this is the case $\Lambda$ is called the left adjoint to $\Gamma$ and $\Gamma$ the right adjoint to $\Lambda$. In 2015, Foniok and Tardif described some functors on the category of digraphs that allow both left and right adjoints. The main contribution of Foniok and Tardif is a construction of right adjoints to some of the functors identified as right adjoints by Pultr in 1970. We shall present several recent advances in this direction including a new approach based on the notion of Datalog Program borrowed from logic.

For a poset arising from combinatorial objects under some substructure relation, we characterize when there are (un)countably-many well-quasi-ordered down-sets.

This is based on joint work with Dillon Mayhew (University of Leeds).

An improper interval (edge) coloring of a graph $G$ is an assignment of colors to the edges of $G$ satisfying the condition that, for every vertex $v \in V(G)$, the set of colors assigned to the edges incident with $v$ forms an integral interval. An interval coloring is $k$-improper if at most $k$ edges with the same color all share a common endpoint.

The minimum integer $k$ such that there exists a $k$-improper interval coloring of the graph $G$ is the interval coloring impropriety of $G$, denoted by $\mu_{int}(G)$. In this talk, we determine improved upper bounds on the interval coloring impropriety of several classes of graphs, namely 2-trees, iterated triangulations, and outerplanar graphs. Additionally, we investigate the interval coloring impropriety of the corona product of two graphs, $G\odot H$. Finally, we provide a construction of an interval coloring of a subclass of complete multipartite graphs. This provides additional evidence to the conjecture by Casselgren and Petrosyan that $\mu_{int}(G)\leq 2$ for all complete multipartite graphs $G$.

This is a joint work with MacKenzie Carr, Nicholas Crawford, Vesna Iršič, Leilani Pai, and Rebecca Robinson.