The concept of p-th variation of a real-valued continuous function along a general class of refining sequence of partitions is presented. We show that the finiteness of the p-th variation of a given function is closely related to the finiteness of ℓp-norm of the coefficients along a Schauder basis, similar to the fact that Hölder coefficient of the function is connected to ℓ∞-norm of the Schauder coefficients. This result provides an isomorphism between the space of α-Hölder continuous functions with finite (generalized) p-th variation along a given partition sequence and a subclass of infinite-dimensional matrices equipped with an appropriate norm, in the spirit of Ciesielski.

We present a full characterization of the unavoidable induced subgraphs of graphs with large pathwidth. This consists of two results. The first result says that for every forest H, every graph of sufficiently large pathwidth contains either a large complete subgraph, a large complete bipartite induced minor, or an induced minor isomorphic to H. The second result describes the unavoidable induced subgraphs of graphs with a large complete bipartite induced minor. We will also try to discuss the proof of the first result with as much detail as time permits. Based on joint work with Maria Chudnovsky and Sophie Spirkl.

A family $\mathcal{F}$ of graphs is said to satisfy the Erdős-Pósa property if there exists a function $f$ such that for every positive integer $k$, every graph $G$ contains either $k$ (vertex-)disjoint subgraphs in $\mathcal{F}$ or a set of at most $f(k)$ vertices intersecting every subgraph of $G$ in $\mathcal{F}$. We characterize the obstructions to the Erdős-Pósa property of $A$-paths in unoriented group-labelled graphs. As a result, we prove that for every finite abelian group $\Gamma$ and for every subset $\Lambda$ of $\Gamma$, the family of $\Gamma$-labelled $A$-paths whose lengths are in $\Lambda$ satisfies the half-integral relaxation of the Erdős-Pósa property. Moreover, we give a characterization of such $\Gamma$ and $\Lambda\subseteq\Gamma$ for which the same family of $A$-paths satisfies the full Erdős-Pósa property. This is joint work with Youngho Yoo.

An induced packing of cycles in a graph is a set of vertex-disjoint cycles such that the graph has no edge between distinct cycles of the set. The classic Erdős-Pósa theorem shows that for every positive integer $k$, every graph contains $k$ vertex-disjoint cycles or a set of $O(k\log k)$ vertices which intersects every cycle of $G$. We generalise this classic Erdős-Pósa theorem to induced packings of cycles of length at least $\ell$ for any integer $\ell$. We show that there exists a function $f(k,\ell)=O(\ell k\log k)$ such that for all positive integers $k$ and $\ell$ with $\ell\geq3$, every graph $G$ contains an induced packing of $k$ cycles of length at least $\ell$ or a set $X$ of at most $f(k,\ell)$ vertices such that the closed neighbourhood of $X$ intersects every cycle of $G$. Furthermore, we extend the result to long cycles containing prescribed vertices. For a graph $G$ and a set $S\subseteq V(G)$, an $S$-cycle in $G$ is a cycle containing a vertex in $S$. We show that for all positive integers $k$ and $\ell$ with $\ell\geq3$, every graph $G$, and every set $S\subseteq V(G)$, $G$ contains an induced packing of $k$ $S$-cycles of length at least $\ell$ or a set $X$ of at most $\ell k^{O(1)}$ vertices such that the closed neighbourhood of $X$ intersects every cycle of $G$. Our proofs are constructive and yield polynomial-time algorithms, for fixed $\ell$, finding either the induced packing of the constrained cycles or the set $X$. This is based on joint works with Pascal Gollin, Tony Huynh, and O-joung Kwon.

The group \( S_n \) of permutations on \([n]=\{1,2,\dots,n\} \) is generated by simple transpositions \( s_i = (i,i+1) \). The length \( \ell(\pi) \) of a permutation \( \pi \) is defined to be the minimum number of generators whose product is \( \pi \). It is well-known that the longest element in \( S_n \) has length \( n(n-1)/2 \). Let \( F_n \) be the semigroup of functions \( f:[n]\to[n] \), which are generated by the simple transpositions \( s_i \) and the function \( t:[n]\to[n] \) given by \( t(1) =t(2) = 1 \) and \( t(i) = i \) for \( i\ge3 \). The length \( \ell(f) \) of a function \( f\in F_n \) is defined to be the minimum number of these generators whose product is \( f \). In this talk, we study the length of longest elements in \( F_n \). We also find a connection with the Slater index of a tournament of the complete graph \( K_n \). This is joint work with Yasuhide Numata.

A replacement action is a function $\mathcal L$ that maps each graph to a collection of subgraphs of smaller size. Given a graph class $\mathcal H$, we consider a general family of graph modification problems, called “$\mathcal L$-Replacement to $\mathcal H$”, where the input is a graph $G$ and the question is whether it is possible to replace some induced subgraph $H_1$ of $G$ on at most $k$ vertices by a graph $H_2$ in ${\mathcal L}(H_1)$ so that the resulting graph belongs to $\mathcal H$. “$\mathcal L$-Replacement to $\mathcal H$” can simulate many graph modification problems including vertex deletion, edge deletion/addition/edition/contraction, vertex identification, subgraph complementation, independent set deletion, (induced) matching deletion/contraction, etc. We prove here that, for any minor-closed graph class $\mathcal H$ and for any action $\mathcal L$ that is hereditary, there is an algorithm that solves “$\mathcal L$-Replacement to $\mathcal H$” in time $2^{{\sf poly}(k)}\cdot |V(G)|^2$, where $\sf poly$ is a polynomial whose degree depends on $\mathcal H$.

We propose a general learning based framework for solving nonsmooth and nonconvex inverse problems with application to low-dose CT (LDCT) reconstruction. We model the regularization function as the combination of a sparsity enhancing and a non-local smoothing regularization. We develop an efficient learned descent-type algorithm (ELDA) to solve the nonsmooth nonconvex minimization problem by leveraging the Nesterov’s smoothing technique and incorporating the residual learning structure. We proved the convergence of the algorithm and generate the network, whose architecture follows the algorithm exactly. Our method is versatile as one can employ various modern network structures into the regularization, and the resulting network inherits the convergence properties, and hence is interpretable. We also show that the proposed network is parameter-efficient and its performance compares favorably to the state-of-the-art methods.

---

https://kaist.zoom.us/j/82680768716?pwd=4jDj5hW70PKYbTcYq1nbkEa9Gsarhi.1 Meeting ID: 826 8076 8716 Passcode: 933841 참고: Jan 16, 2025 07:00 PM Eastern Time (US and Canada) https://kaist.zoom.us/j/82680768716?pwd=4jDj5hW70PKYbTcYq1nbkEa9Gsarhi.1 Meeting ID: 826 8076 8716 Passcode: 933841

Given a manifold, the vertices of a geometric intersection graph are defined as a class of submanifolds. Whether there is an edge between two vertices depends on their geometric intersection numbers. The geometric intersection complex is the clique complex induced by the geometric intersection graph. Common examples include the curve (arc) complex and the Kakimizu complex. Curve complexes and arc complexes are used to understand mapping class groups and Teichmüller spaces, while Kakimizu complexes are primarily used to study hyperbolic knots. We can study these geometric intersection complexes from various perspectives, including topology (e.g., homotopy type), geometry (e.g., dimension, diameter, hyperbolicity), and number-theoretic connections (e.g., trace formulas of maximal systems). In this talk, we will mainly explain how to determine the dimension of the (complete) $1$-curve (or arc) complex on a non-orientable surface and examine the transitivity of maximal complete $1$-systems of loops on a punctured projective plane.

A major goal of additive combinatorics is to understand the structures of subsets A of an abelian group G which has a small doubling K = |A+A|/|A|. Freiman’s celebrated theorem first provided a structural characterization of sets with small doubling over the integers, and subsequently Ruzsa in 1999 proved an analog for abelian groups with bounded exponent. Ruzsa further conjectured the correct quantitative dependence on the doubling K in his structural result, which has attracted several interesting developments over the next two decades. I will discuss a complete resolution of (a strengthening of) Ruzsa’s conjecture. Surprisingly, our approach is crucially motivated by purely graph-theoretic insights, where we find that the group structure is superfluous and can be replaced by much more general combinatorial structures. Using this general approach, we also obtain combinatorial and nonabelian generalizations of classical results in additive combinatorics, and solve longstanding open problems around Cayley graphs and random Cayley graphs motivated by Ramsey theory, information theory and computer science. Based on joint work with David Conlon, Jacob Fox and Liana Yepremyan.