# KPPY 98

Apr 06, 2024. 11:30am - 5:00pm at KNU (Room 313 of Building 209)

Schedule | ||

11:30 |
Seunghun Lee KAIST | Constructions of geometric hypergraphs with high chromatic number and transversal ratio |

12:30 | Lunch | |

2:00 |
Victor Dalmau University Pompeu Fabra | Right-adjoints of Datalog Programs |

3:00 |
Rutger Campbell IBS | Counting well-quasi-ordered down-sets |

4:00 |
Eun-Kyung Cho Hanyang University | On the Interval Coloring Impropriety of Graphs |

5:00 | Dinner |

## Abstracts

Seunghun Lee

Constructions of geometric hypergraphs with high chromatic number and transversal ratio

Constructions of geometric hypergraphs with high chromatic number and transversal ratio

Given a hypergraph $H=(V,E)$, we say that $H$ is

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.

*(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.

Victor Dalmau

Right-adjoints of Datalog Programs

Right-adjoints of Datalog Programs

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.

Rutger Campbell

Counting well-quasi-ordered down-sets

Counting well-quasi-ordered down-sets

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).

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

Eun-Kyung Cho

On the Interval Coloring Impropriety of Graphs

On the Interval Coloring Impropriety of Graphs

An

The minimum integer $k$ such that there exists a $k$-improper interval coloring of the graph $G$ is the

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

*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.