Hongseok Yang (양홍석), Learning Symmetric Rules with SATNet

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.

Kyeongsik Nam (남경식), Large deviations for subgraph counts in random graphs

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.

Cheolwon Heo (허철원), The complexity of the matroid-homomorphism problems

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.

Boram Park (박보람), Odd coloring of sparse graphs

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.

Younjin Kim (김연진), On the extremal problems related to Szemerédi’s theorem

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.

The ECOPRO Opening Conference was held online from April 4 to April 6

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.

Day 1: April 4 Monday

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

Day 2: April 5 Tuesday

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

Day 3: April 6 Wednesday

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

Hong Liu is appointed as the CI of the new group, “IBS Extremal Combinatorics and Probability Group (ECOPRO)” as of April 1

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.

Hong Liu is moving to IBS as a Chief Investigator to start the IBS Extremal Combinatorics and Probability Group (ECOPRO) on April 2022 and is hiring up to 5 postdocs in all fields of combinatorics with emphasis on extremal and probabilistic combinatorics, graph theory, Ramsey theory, combinatorial number theory and discrete geometry

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

  1. Curriculum vitae including a publication list (PDF format)
  2. Research statement (PDF format)
  3. Up to 3 best papers or preprints
  4. Consent to Collection and Use of Personal Information (Please convert to a PDF file)
  5. Two or three recommendation letters.

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.

IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.