Let $g, f$ be non-negative integer-valued functions on $V(G)$ such that $g(v) \le f(v) \le d_G(v)$ for all $v \in V(G)$.
A $(g,f)$-factor of $G$ is a spanning subgraph $H$ of $G$ such that for every vertex $v \in V(G)$, $g(v) \le d_H(v) \le f(v)$. For $g$ and $f$ with $g(v) \equiv f(v) (\mod 2)$ for all $v \in V(G)$, a $(g, f)$-parity factor of $G$ is a $(g,f)$-factor $H$ such that $d_H(v)...
A signed graph is a pair $(G,\Sigma)$ where $G$ is a graph and $\Sigma$ is a subset of edges of $G$. We say that a cycle $C$ of $G$ is even in $(G,\Sigma)$ if $|C \cap \Sigma|$ is even; otherwise, $C$ is odd. A matroid $M$ is an even-cycle matroid if there exists a signed graph $(G,\Sigma)$ such that the circuits of $M$ precisely correspond to the even cycles or the unions of two odd cycles...
We call an induced cycle of length at least four a hole. The parity of a hole is the parity of its length. Forbidding holes of certain types in a graph has deep structural implications. In 2006, Chudnovksy, Seymour, Robertson, and Thomas famously proved that a graph is perfect if and only if it does not contain an odd hole or a complement of an odd hole. In 2002, Conforti, Cornuéjols,...
The oriented Ramsey number $\vec{r}(H)$ for an acyclic digraph $H$ is the minimum integer $n$ such that any $n$-vertex tournament contains a copy of $H$ as a subgraph. We prove that the $1$-subdivision of the $k$-vertex transitive tournament $H_k$ satisfies $\vec{r}(H_k)\leq O(k^2\log\log k)$. This is tight up to multiplicative $\log\log k$-term.
We also show that if $T$ is an $n$-vertex...
The list switch homomorphisms problem $LSwHom(H)$ is for a signed graph $G$ with list if there is a switch homomorphism to $H$ preserving lists. We present towards a structural characterisation of the signed graphs $H$ for which the $LSwHom(H)$ problem is polynomial time solvable. We prove the characterisation in the case that the signed graph is reflexive.
The study of patterns in inversion sequences was initiated by Corteel-Martinez-Savage-Weselcouch and Mansour-Shattuck independently. This talk introduces some investigation on several classical statistics on restricted inversion sequences that are either known or conjectured to be enumerated by Catalan, Large Schröder, Baxter and Euler numbers. This talk is based on joint work with Zhicong Lin...
$q$-analogues of quantities in mathematics involve perturbations of classical quantities using the parameter $q$, and revert to the original quantities when $q$ goes $1$. An important example is the $q$-analogues of binomial coefficients, which give the number of $k$-dimensional subspaces in $\mathbb{F}_{q}^{n}$. When $q$ goes to $1$, this reverts to the binomial coefficients which measure...
Bonnet, Kim, Thomass\'{e}, and Watrigant (2020) introduced the twin-width of a graph. We show that the twin-width of an $n$-vertex graph is less than $(n+\sqrt{n\ln n}+\sqrt{n}+2\ln n)/2$, and the twin-width of an $m$-edge graph is less than $\sqrt{3m}+ m^{1/4} \sqrt{\ln m} / (4\cdot 3^{1/4}) + 3m^{1/4} / 2$. Conference graphs of order $n$ (when such graphs exist) have twin-width at least...
A family $\mathcal{H}$ of graphs is said to be $\chi$-bounded, if there is a function $f:\mathbb{N}\rightarrow\mathbb{N}$ such that for every graph $H\in\mathcal{H}$ the chromatic number $\chi(H)$ of $H$ is at most $f(\omega)$, where $\omega$ is the clique number of $H$. We show that the family of graphs that do not have a cycle with exactly $k$ chords is $\chi$-bounded, for every large enough...
Helly's theorem and its variants asserts that for a family of convex sets in Euclidean space, local intersection patterns influence global intersection patterns. A classical result of Eckhoff in 1988 provided an optimal fractional Helly theorem for axis-parallel boxes, which are Cartesian products of line segments. Answering a question raised by Barany and Kalai, and independently by Lew, we...
We study a natural generalization of the well-studied Tur\'an problems, known as multicolor Tur\'an problems, which was first introduced and nurtured by Keevash, Saks, Sudakov, and Verstra\"{e}te. A simple $k$-coloring of a multigraph $G$ is a decomposition of the edge multiset as a disjoint sum of $k$ simple graphs which are referred as \emph{colors}. A subgraph $H$ of a multigraph $G$ is...
We define an n-dimensional projective smooth toric variety associated with a triangulation of the (n+2)-gon. Such a toric variety is called of Catalan type. We show that toric varieties of Catalan type are Fano Bott manifolds, and they appear in certain smooth toric Richardson varieties in the flag variety. We also see that toric varieties of Catalan type are classified up to isomorphism in...
What is the largest number $f(d)$ where every graph with average degree at least $d$ contains a subdivision of $K_{f(d)}$? Mader asked this question in 1967 and $f(d) = \Theta(\sqrt{d})$ was proved by Bollob\'as and Thomason and independently by Koml\'os and Szemer\'edi. This is best possible by considering a disjoint union of $K_{d,d}$. However, this example contains a much smaller subgraph...
A dominating set of a graph $G$ is a set $S$ of vertices such that each vertex not in $S$ is adjacent to some vertex in $S$. The independent domination number of a graph $G$, denoted $i(G)$, is the minimum cardinality of a dominating set of $G$ which is also independent. In 2018, Abrishami and Henning showed that $i(G) \leq \frac{4}{11}|V(G)|$ for every cubic graph $G$ with girth at least...
When two balls in a metric space has small intersection? We give some natural conditions to guarantee an exponential decay on the volume of such intersections. Our proof is conceptually simple, making use of concentration of measure on a "slice". We will discuss a couple of applications of this volume estimate in coding theory. This is joint work with Jaehoon Kim and Tuan Tran.
The (manufacturer's) pallet loading problem has been a topic of wide interest for operational research and companies for more than 50 years. It is to find the optimal loading of identical rectangular boxes onto a single rectangular pallet (also allowing for 90 degree rotation).
It was already known that all box layouts in the given pallet are completely determined by the set of efficient...
This talk presents a method for detecting and restoring integer datasets that have been manipulated by operations involving non-integral real-number multiplication and rounding. Detecting and restoring such manipulated integer datasets is not straightforward, nor are there any known solutions. We introduce the manipulation process, which was motivated by an actual case of fraud on the TV...
