Seog-Jin Kim (김석진), Signed colouring and list colouring of k-chromatic graphs
Room B232 IBS (기초과학연구원)A signed graph is a pair (G, σ), where G is a graph and σ: E(G) → {1,-1} is a signature of G. A set S of integers is symmetric …
10 events found.
Discrete Math Seminar
-
-
-
-
Andreas Holmsen, Large cliques in hypergraphs with forbidden substructures
Room B232 IBS (기초과학연구원)A result due to Gyárfás, Hubenko, and Solymosi, answering a question of Erdős, asserts that if a graph $G$ does not contain $K_{2,2}$ as an induced subgraph yet has at …
-
-
Jon-Lark Kim (김종락), Introduction to Boolean functions with Artificial Neural Network
Room B232 IBS (기초과학연구원)A Boolean function is a function from the set Q of binary vectors of length n (i.e., the binary n-dimensional hypercube) to $F_2=\{0,1\}$. It has several applications to complexity theory, …
-
Rose McCarty, Circle graphs are polynomially chi-bounded
Room B232 IBS (기초과학연구원)Circle graphs are the intersection graphs of chords on a circle; vertices correspond to chords, and two vertices are adjacent if their chords intersect. We prove that every circle graph …
-
-
Sang June Lee (이상준), On strong Sidon sets of integers
Room B232 IBS (기초과학연구원)Let $\mathbb N$ be the set of natural numbers. A set $A\subset \mathbb N$ is called a Sidon set if the sums $a_1+a_2$, with $a_1,a_2\in S$ and $a_1\leq a_2$, are …
-
Xin Zhang (张欣), On equitable tree-colorings of graphs
Room B232 IBS (기초과학연구원)An equitable tree-$k$-coloring of a graph is a vertex coloring using $k$ distinct colors such that every color class (i.e, the set of vertices in a common color) induces a …
-
Lars Jaffke, A complexity dichotomy for critical values of the b-chromatic number of graphs
Room B232 IBS (기초과학연구원)A $b$-coloring of a graph $G$ is a proper coloring of its vertices such that each color class contains a vertex that has at least one neighbor in all the …
-
-
Jinyoung Park (박진영), The number of maximal independent sets in the Hamming cube
Room B232 IBS (기초과학연구원)Let $Q_n$ be the $n$-dimensional Hamming cube (hypercube) and $N=2^n$. We prove that the number of maximal independent sets in $Q_n$ is asymptotically $2n2^{N/4}$, as was conjectured by Ilinca and …
-
Suil O (오수일), An odd [1,b]-factor in regular graphs from eigenvalues
Room B232 IBS (기초과학연구원)An odd $$-factor of a graph is a spanning subgraph $H$ such that for every vertex $v \in V(G)$, $1 \le d_H(v) \le b$, and $d_H(v)$ is odd. For positive integers $r …
-
Patrice Ossona de Mendez, A model theoretical approach to sparsity
Room B232 IBS (기초과학연구원)We discuss how the model theoretic notion of first-order transduction allows to define a notion of structural sparsity, and give some example of applications, like existence of low shrub-depth decompositions …