Debsoumya Chakraborti, Some classical problems in graph saturation
Room B232 IBS (기초과학연구원)Graph saturation is one of the oldest areas of investigation in extremal combinatorics. A graph
Graph saturation is one of the oldest areas of investigation in extremal combinatorics. A graph
We propose a theoretical analysis of recommendation systems in an online setting, where items are sequentially recommended to users over time. In each round, a user, randomly picked from a population of m users, requests a recommendation. The decision-maker observes the user and selects an item from a catalogue of n items. Importantly, an item …
Corneil, Olariu, and Stewart presented a recognition algorithm for interval graphs by six graph searches. Li and Wu simplified it to only four. The great simplicity of the latter algorithm is however eclipsed by the complicated and long proofs. The main purpose of this paper is to present a new and significantly shorter proof for …
In 1975, Erdős asked the following question: what is the smallest function
The twin-width of a graph G can be defined as the least integer d such that there is a sequence of length |V(G)| of (strictly) coarser and coarser partitions of its vertex set V(G), and every part X of every partition P of the sequence has at most d other parts Y of P with …
We show that that the maximum number of of edges in a
A pure pair in a graph G is a pair of subsets A, B of the vertex set of G such that in G, either all of the edges or none of the edges between A and B are present. Pure pairs have been studied recently motivated by their connections to the Erdos-Hajnal conjecture. In …
In this talk we will have a brief introduction to oriented matroids and their relation to real-representability.
For a graph G and an integer d, the dth power of G is the graph
Ordered Ramsey numbers were introduced in 2014 by Conlon, Fox, Lee, and Sudakov. Their results included upper bounds for general graphs and lower bounds showing separation from classical Ramsey numbers. We show the first nontrivial results for ordered Ramsey numbers of specific small graphs. In particular we prove upper bounds for orderings of graphs on four vertices, …