기초과학연구원 이산수학그룹
The IBS Discrete Mathematics Group welcomes Dr. Jun Gao (高峻), a new (and second) research fellow at the IBS Extremal Combinatorics and Probability Group from August 1, 2022. He received his Ph.D. from the University of Science and Technology of China (USTC) under the supervision of Prof. Jie Ma.
SATNet is a differentiable constraint solver with a custom backpropagation algorithm, which can be used as a layer in a deep-learning system. It is a promising proposal for bridging deep learning and logical reasoning. In fact, SATNet has been successfully applied to learn, among others, the rules of a complex logical puzzle, such as Sudoku, just from input and output pairs where inputs are given as images. In this paper, we show how to improve the learning of SATNet by exploiting symmetries in the target rules of a given but unknown logical puzzle or more generally a logical formula. We present SymSATNet, a variant of SATNet that translates the given symmetries of the target rules to a condition on the parameters of SATNet and requires that the parameters should have a particular parametric form that guarantees the condition. The requirement dramatically reduces the number of parameters to learn for the rules with enough symmetries, and makes the parameter learning of SymSATNet much easier than that of SATNet. We also describe a technique for automatically discovering symmetries of the target rules from examples. Our experiments with Sudoku and Rubik’s cube show the substantial improvement of SymSATNet over the baseline SATNet.
This is joint work with Sangho Lim and Eungyeol Oh.
The IBS Discrete Mathematics Group welcomes Dr. Stijn Cambie, a new (and first) research fellow at the IBS Extremal Combinatorics and Probability Group from May 16, 2022. He received his Ph.D. from the Radboud University in the Netherlands under the supervision of Prof. Ross Kang. He is interested in extremal problems on various graph parameters and in extremal set theory.
The upper tail problem for subgraph counts in the Erdos-Renyi graph, introduced by Janson-Ruciński, has attracted a lot of attention. There is a class of Gibbs measures associated with subgraph counts, called exponential random graph model (ERGM). Despite its importance, lots of fundamental questions have remained unanswered owing to the lack of exact solvability. In this talk, I will talk about a brief overview on the upper tail problem and the concentration of measure results for the ERGM. Joint work with Shirshendu Ganguly and Ella Hiesmayr.
In this talk, we introduce homomorphisms between binary matroids that generalize graph homomorphisms. For a binary matroid $N$, we prove a complexity dichotomy for the problem $\rm{Hom}_\mathbb{M}(N)$ of deciding if a binary matroid $M$ admits a homomorphism to $N$. The problem is polynomial-time solvable if $N$ has a loop or has no circuits of odd length, and is otherwise $\rm{NP}$-complete. We also get dichotomies for the list, extension, and retraction versions of the problem.
This is joint work with Hyobin Kim and Mark Siggers at Kyungpook National University.
We introduce an odd coloring of a graph, which was introduced very recently, motivated by parity type colorings of graphs. A proper vertex coloring of graph $G$ is said to be odd if for each non-isolated vertex $x \in V (G)$ there exists a color $c$ such that $c$ is used an odd number of times in the neighborhood of $x$. The recent work on this topic will be presented, and the work is based on Eun-Kyung Cho, Ilkyoo Choi, and Hyemin Kown.
To celebrate the opening of the IBS Extremal Combinatorics and Probability Group, the IBS ECOPRO Opening Conference was held online from April 4 to April 6. There were 10 invited speakers and more than 100 participants.
Jeong Han Kim, 7:15-8:00pm
Majority dynamics on sparse random graphs
Oleg Pikhurko, 8:00-8:45pm
Moser-Tardos Algorithm with small number of random bits
Jeff Kahn, 8:45-9:30pm
Linear cover time is exponentially unlikely
Noga Alon, 9:30-10:15pm
Random processes of graphs and permutations
Mihyun Kang, 8:00-8:45pm
Random subgraphs of the hypercube
József Balogh, 8:45-9:30pm
On Robustness of The Erdős-Ko-Rado Theorem
Benny Sudakov, 9:30-10:15pm
Short proofs of rainbow matching results
Van Vu, 8:00-8:45pm/1:00-1:45pm/7:00-7:45am
Majority dynamics on a random graph: The power of few
Tibor Szabó, 8:45-9:30pm
Topology at the North Pole
Nati Linial, 9:30-10:15pm
Geodesic Geometry of Graphs
On April 1, 2022, Hong Liu from the University of Warwick is appointed as the Chief Investigator to lead a new group, the IBS Extremal Combinatorics and Probability Group (ECOPRO), in the Center for Mathematical and Computational Sciences. To enhance our collaboration, the IBS Discrete Mathematics Group will move to the 3rd floor of the theory building on April 19-21 to share the space with the Extremal Combinatorics and Probability Group.
In 1975, Szemerédi proved that for every real number $\delta > 0 $ and every positive integer $k$, there exists a positive integer $N$ such that every subset $A$ of the set $\{1, 2, \cdots, N \}$ with $|A| \geq \delta N$ contains an arithmetic progression of length $k$. There has been a plethora of research related to Szemerédi’s theorem in many areas of mathematics. In 1990, Cameron and Erdős proposed a conjecture about counting the number of subsets of the set $\{1,2, \dots, N\}$ which do not contain an arithmetic progression of length $k$. In the talk, we study a natural higher dimensional version of this conjecture, and also introduce recent extremal problems related to Szemerédi’s theorem.
We are very excited to learn that Prof. Hong Liu from University of Warwick, UK will move to the Institute for Basic Science (IBS) as a Chief Investigator (CI) to lead a new group called the Extremal Combinatorics and Probability Group (ECOPRO) on April 2022. This new group will be also located in the IBS headquarter and is expected to work closely with the IBS Discrete Mathematics Group (DIMAG). Both DIMAG and ECOPRO belong to the IBS Center for Mathematical and Computational Sciences together with the Data Science Group and the Biomedical Mathematics Group and we share the staff members.
The website was made recently. https://www.ibs.re.kr/ecopro/
Yesterday, the IBS Extremal Combinatorics and Probability Group (ECOPRO) posted the hiring announcement for up to 5 postdocs. Here are a few paragraphs from the announcement.
The Extremal Combinatorics and Probability Group (ECOPRO) at the Institute for Basic Science (IBS) in Daejeon, South Korea invites applications for 5 postdoctoral research fellowship positions. ECOPRO is a new research group that will be officially launched in April 1, 2022 at IBS, led by Prof. Hong Liu. We welcome highly motivated postdoc researchers with outstanding research potential in all fields of combinatorics with emphasis on extremal and probabilistic combinatorics, graph theory, Ramsey theory, combinatorial number theory and discrete geometry. This appointment is for 2 years with possible 1 year extension contingent upon the outstanding performance of the researcher. The starting salary is no less than 57,000,000 KRW (about 48,400 USD or 42,800 EUR). The appointment starting date is flexible: between April 1 and Oct 1, 2022. This is a purely research position and will have no teaching duties.
A complete application packet should include
For full consideration, applicants should email items 1, 2, 3, and 4 and arrange their recommendation letters emailed to ecopro@ibs.re.kr by January 14, 2022.
Recommendations letters forwarded by an applicant will not be considered.