기초과학연구원 이산수학그룹
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 least $c\binom{n}{2}$ edges, then $G$ has a complete subgraph on at least $\frac{c^2}{10}n$ vertices. In this paper we suggest a "higher-dimensional" analogue of the notion …
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, digital circuits, coding theory, and cryptography. In this talk we give a connection between Boolean functions and Artificial Neural Network. We describe how to represent …
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 with clique number k has chromatic number at most $4k^2$. Joint with James Davies.
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 distinct, or equivalently, if \ for every $x,y,z,w\in S$ with $x<y\leq z<w$. We define strong Sidon sets as follows: For a constant $\alpha$ with $0\leq …
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 forest and the sizes of any two color classes differ by at most one. The minimum integer $k$ such that a graph $G$ is equitably …
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 other color classes. The $b$-Coloring problem asks whether a graph $G$ has a $b$-coloring with $k$ colors. The $b$-chromatic number of a graph $G$, denoted …
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 Kahn in connection with a question of Duffus, Frankl and Rödl. The value is a natural lower bound derived from a connection between maximal independent …
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 \ge 3$ and $b \le r$, Lu, Wu, and Yang gave an upper bound for the third largest eigenvalue in an $r$-regular graph with even number of …
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 for tranductions of bounded expansion classes, characterization of transductions of classes with bounded pathwidth, decompositions of graphs with bounded rank-width into cographs.
Given a finite set of elements $V$ and a family $\mathcal{C}$ of subsets of $V$, the set covering problem is to find a minimum cardinality subset of $V$ intersecting every subset in the family $\mathcal{C}$. The set covering problem, also known as the hitting set problem, admits a simple integer linear programming formulation. The constraint …