세미나 및 콜로퀴엄
구글 Calendar나 iPhone 등에서 구독하면 세미나 시작 전에 알림을 받을 수 있습니다.
Courcelle’s Theorem is an influential metatheorem published in 1990. It tells us that a property of graph can be tested in polynomial time, as long as the property can expressed in the monadic secondorder logic of graphs, and as long as the input is restricted to a class of graphs with bounded treewidth. There are several properties that are NPcomplete in general, but which can be expressed in monadic logic (3colourability, Hamiltonicity…), so Courcelle’s Theorem implies that these difficult properties can be tested in polynomial time when the structural complexity of the input is limited.
Matroids can be considered as a special class of hypergraphs. Any finite set of vectors over a field leads to a matroid, and such a matroid is said to be representable over that field. Hlineny produced a matroid analogue of Courcelle’s Theorem for input classes with bounded branchwidth that are representable over a finite field.
We have now identified the structural properties of hypergraph classes that allow a proof of Hliněný’s Theorem to go through. This means that we are able to extend his theorem to several other natural classes of matroids.
This talk will contain an introduction to matroids, monadic logic, and treeautomata.
This is joint work with Daryl Funk, Mike Newman, and Geoff Whittle.
What is the largest subset of $\mathbb Z_{2^n}$ that doesn’t contain a projective dcube? In the Boolean lattice, Sperner’s, Erdos’s, Kleitman’s and Samotij’s theorems state that families that do not contain many chains must have a very specific layered structure. We show that if instead of
Z
n
2
we work in
Z
2
n
, analogous statements hold if one replaces the word kchain by projective cube of dimension
2
k
−
1
. The largest dcubefree subset of
Z
2
n
, if d is not a power of two, exhibits a much more interesting behaviour.
This is joint work with Jason Long.
An important family of incidence problems are discrete analogs of deep questions in geometric measure theory. Perhaps the most famous example of this is the finite field Kakeya conjecture, proved by Dvir in 2008. Dvir’s proof introduced the polynomial method to incidence geometry, which led to the solution to many longstanding problems in the area.
I will talk about a generalization of the Kakeya conjecture posed by Ellenberg, Oberlin, and Tao. A
(
k
,
m
)
Furstenberg set S in
F
n
q
has the property that, parallel to every affine
k
plane V, there is a kplane W such that

W
∩
S

>
m
. Using sophisticated ideas from algebraic geometry, Ellenberg and Erman showed that if S is a
(
k
,
m
)
Furstenberg set, then

S

>
c
m
n
/
k
, for a constant c depending on n and k. In recent joint work with Manik Dhar and Zeev Dvir, we give simpler proofs of stronger bounds. For example, if
m
>
2
n
+
7
q
, then

S

=
(
1
−
o
(
1
)
)
m
q
n
−
k
, which is tight up to the
o
(
1
)
term.
In many applications of machine learning, interpretable or explainable models for binary classification, such as decision trees or decision lists, are preferred over potentially more accurate but less interpretable models such as random forests or support vector machines. In this talk, we consider boolean decision rule sets (equivalent to boolean functions in disjunctive normal form) as interpretable models for binary classification. We define the complexity of a rule set to be the number of rules (clauses) plus the number of conditions (literals) across all clauses, and assume that simpler or less complex models are more interpretable. We discuss an integer programming formulation for such models that trades off classification accuracy against rule simplicity, and obtain highquality classifiers of this type using column generation techniques. Compared to some recent alternatives, our algorithm dominates the accuracysimplicity tradeoff in 8 out of 16 datasets, and also produced the winning entry in the 2018 FICO explainable machine learning challenge. When compared to rule learning methods designed for accuracy, our algorithm sometimes finds significantly simpler solutions that are no less accurate.
자연과학동(E61) Room 1401
확률론
남경식 (UC Berkeley)
Elliptic and hypoelliptic diffusions with singular drift
자연과학동(E61) Room 1401
확률론
It has been known that stochastic differential equations with nondegenerate diffusion admit a unique solution for subcritical drifts. In this talk, we extend this in two different directions: the critical drift case and the degenerate diffusion case. I will briefly introduce a hypoelliptic theory, and then explain how to obtain probabilistic results on stochastic differential equations.
A classical problem in mechanics is the following: given a set of forces applied at some points in space, is there any discrete network with all the wires under tension that supports such a system of forces? In this talk I will present some recent results on the topic, obtained in collaboration with Graeme Milton, Pierre Seppecher and Guy Bouchitte. In usual wire or cable networks, such as in a bridge or bicycle wheel, one distributes the forces by adjusting the tension in the wires. Here our discrete networks provide an alternative way of distributing the forces through the geometry of the network. In particular the network can be chosen so it is uniloadable, i.e. supports only one set of forces at the terminal nodes. Such uniloadable networks are relevant as the tension in one element determines the tension in the joint wires and, by extension, uniquely determines the stress in the entire network.
We introduce a notion of PAC structures, which generalizes perfect PAC fields, and we study their elementary theories via their Galois groups.
It is well known that elementary equivalences of PAC fields are controlled by their Galois groups by Embedding Lemma of M. Jarden and U. Kiehne. Also, G. Cherlin, L. van den Dries, and A. Macintyre introduced a notion of complete systems of profinite groups, axiomatized by first order logic, and they showed that the category of complete systems whose morphisms are embedding is equivalent to the category of profinite groups whose morphisms are epimorphisms. And they showed that the complete systems of Galois groups of PAC fields determine elementary equivalences and elementary extensions between PAC fields. Recently, Z. Chatzidakis and N. Ramsey showed that complete systems of Galois groups are very crucial role in the classification program of first order theories of PAC fields: If the complete system of Galois group of a given PAC field is SNOPn, then so is the PAC field.
We generalize these previous results for PAC fields into PAC structures: We generalize Embedding Lemma for PAC fields into PAC structures. We also introduce a notion of sorted complete systems, which generalizes the complete systems and we show that first order theories of PAC structures are determined by their sorted complete systems. And we generalize NSOPn criteria for PAC fields into PAC structures in terms of sorted complete systems.
This talk is based on joint works of J. Dobrowolski, D. M. Hoffmann, and of D. M. Hoffmann.
We introduce a notion of PAC structures, which generalizes perfect PAC fields, and we study their elementary theories via their Galois groups.
It is well known that elementary equivalences of PAC fields are controlled by their Galois groups by Embedding Lemma of M. Jarden and U. Kiehne. Also, G. Cherlin, L. van den Dries, and A. Macintyre introduced a notion of complete systems of profinite groups, axiomatized by first order logic, and they showed that the category of complete systems whose morphisms are embedding is equivalent to the category of profinite groups whose morphisms are epimorphisms. And they showed that the complete systems of Galois groups of PAC fields determine elementary equivalences and elementary extensions between PAC fields. Recently, Z. Chatzidakis and N. Ramsey showed that complete systems of Galois groups are very crucial role in the classification program of first order theories of PAC fields: If the complete system of Galois group of a given PAC field is SNOPn, then so is the PAC field.
We generalize these previous results for PAC fields into PAC structures: We generalize Embedding Lemma for PAC fields into PAC structures. We also introduce a notion of sorted complete systems, which generalizes the complete systems and we show that first order theories of PAC structures are determined by their sorted complete systems. And we generalize NSOPn criteria for PAC fields into PAC structures in terms of sorted complete systems.
This talk is based on joint works of J. Dobrowolski, D. M. Hoffmann, and of D. M. Hoffmann.
We will see several applications of model theory to other mathematics, mainly to number theory, arithmetic geometry, and algebraic geometry.
Model theory is a branch of mathematical logic. There are mainly four branches: computability theory, model theory, proof theory, and set theory. W. Hodges described model theory as "algebraic geometry minus fields" in his book "A Shorter Model Theory". In model theory, we study definable sets in mathematical structures, for example, algebraic sets in the field of complex numbers or semialgebraic sets in the field of real numbers, and we classify their first order theories of the structures.
We recall several basic concepts of model theory: elementary equivalence, quantifier elimination, and elimination of imaginaries. And we will see how such concepts can be applied to number theory, arithmetic geometry, and algebraic geometry.
To an abelian category A satisfying certain finiteness conditions, one can associate an algebra H_A (the Hall algebra of A) which encodes the structures of the space of extensions between objects in A. For a nonadditive setting, Dyckerhoff and Kapranov introduced the notion of protoexact categories, as a nonadditive generalization of an exact category, which is shown to suffice for the construction of an associative Hall algebra. In this talk, I will discuss the category of matroids in this perspective.
We consider generalized MHD equations with fractional diffusions. Existence of local solutionshas been wellknown for initial datain Sobolev spaces $H^s$, if $s$ is sufficiently large. The goal of the talk is to present local existence results with initial datain $H^{s_1} \times H^{s_2}$ of lower orders $s_1$ and/or $s_2$, which extend recent existence results by Fefferman, McCormick, Robinson, and Rodrigo(2014, 2017). This is a joint work with Yong Zhou at the Sun YatSen University (Zhuhai), China.
In this talk, I propose a computer model that generalizes most if not all previous computer models including Turing machine, Boolean circuit, continuous time system, quantum computer, BlumShubSmale model, and deep learning. I will describe a computational complexity theory for this new model, and construct infinite dimensional algebraic varieties that parametrize deterministic/nondeterministic polynomial time languages.
Let
M
=
(
M
i
:
i
∈
K
)
be a finite or infinite family consisting of finitary and cofinitary matroids on a common ground set
E
.
We prove the following CantorBernsteintype result: if
E
can be covered by sets
(
B
i
:
i
∈
K
)
which are bases in the corresponding matroids and there are also pairwise disjoint bases of the matroids
M
i
then
E
can be partitioned into bases with respect to
M
.
Let f be a nonzero polynomial. A pair of matrices (A, B) of polynomials is called a matrix factorization of f if both AB and BA are f times identity matrices. Eisenbud introduced this notion to study free resolutions over hypersurface rings and complete intersection rings. Among several applications of matrix factorization, we focus on the correspondence between aCM/Ulrich sheaves in this talk. Then we provide a matrix factorization of a general cubic hypersurface of dimension at most 7 using Shamash's construction. Note that this is an alternative proof of the existence of rank 9 Ulrich bundle on a general cubic sevenfold, which is first known by Iliev and Manivel. If time permits, we discuss on classification of cubic forms whose Hessian matrices induce matrix factorization of themselves. This is a joint work with F.O. Schreyer.
Given any integers $s,t\geq 2$, we show there exists some $c=c(s,t)>0$ such that any $K_{s,t}$free graph with average degree $d$ contains a subdivision of a clique with at least $cd^{\frac{1}{2}\frac{s}{s1}}$ vertices. In particular, when $s=2$ this resolves in a strong sense the conjecture of Mader in 1999 that every $C_4$free graph has a subdivision of a clique with order linear in the average degree of the original graph. In general, the widely conjectured asymptotic behaviour of the extremal density of $K_{s,t}$free graphs suggests our result is tight up to the constant $c(s,t)$. This is joint work with Richard Montgomery.
In this presentation, we consider the randomcluster model which is a generalization of the standard edge percolation model. For the randomcluster model on lattice, we prove that the Glauber dynamics exhibits a phenomenon known as the cutoff, especially for the very subcritical regime for all dimensions. This is a joint work with Shirshendu Ganguly.
The notion of bounded expansion captures uniform sparsity of graph classes and renders various algorithmic problems that are hard in general tractable. In particular, the modelchecking problem for firstorder logic is fixedparameter tractable over such graph classes. With the aim of generalizing such results to dense graphs, we introduce classes of graphs with structurally bounded expansion, defined as firstorder interpretations of classes of bounded expansion. As a first step towards their algorithmic treatment, we provide their characterization analogous to the characterization of classes of bounded expansion via low treedepth decompositions, replacing treedepth by its dense analogue called shrubdepth.
We use circles on a sphere to illustrate important concepts in symplectic topology. We explain the difficulties encountered in higher dimensions and to what extent it can be overcome. Subsequently, we introduce the Fukaya category and connect the story to Khovanov homology.
The subject of padic differential equations was pioneered by Dwork in 1950’s, who investigated padic properties of solutions of a certain hypergeometric differential equation. This study of Dwork’s study led to extremely fascinating applications in number theory; especially, on elliptic curves and modular forms. The main goal of this colloquium talk is to explain the motivating example of the padic hypergeometric differential equation studied by Dwork and its link to the Legendre family of elliptic curves. If time permits, I’d like to discuss some generalization of Dwork’s study to families of abelian varieties and its potential applications.
The Swan conductor is a local invariant measuring wild ramification (for Artin representations or suitable variants thereof). It is one of the central objects to study in the ramification theory.
In this expository talk, let me start with a review of ramification subgroups and the theory of Swan conductors and Swan characters. At the end of the talk, I would like to pose some questions on ‘padic analogue of Swan characters’ in the theory of padic differential equations, motivated by equivariant BSD conjecture over global function fields.
Seminar Talk
Seminar Talk