Dear all,

A correction: the talk is scheduled for 12:20, as planned originally. The meeting time in the previous email was wrong.

Apologies for the confusion. Misha.

On 3 March 2022 08:51:03 CET, tyomkyn tyomkyn@kam.mff.cuni.cz wrote:

Reminder: this is today. Please find the zoom meeting details below.

---

Mykhaylo Tyomkyn is inviting you to a scheduled Zoom meeting.

Topic: Noon seminar Time: Mar 3, 2022 02:00 PM Budapest

Join Zoom Meeting https://cesnet.zoom.us/j/98163194532?pwd=VDFMbG5hdmZxVTRuckZiL2FTMnYvQT09

Meeting ID: 981 6319 4532 Passcode: 697354 One tap mobile +420228882388,,98163194532# Czech Republic +420239018272,,98163194532# Czech Republic

Dial by your location +420 2 2888 2388 Czech Republic +420 2 3901 8272 Czech Republic +420 5 3889 0161 Czech Republic Meeting ID: 981 6319 4532 Find your local number: https://cesnet.zoom.us/u/ad9zWV0KOA

On 2022-02-28 17:45, tyomkyn wrote:

...

Dear all,

This week's noon seminar will (exceptionally) be via zoom. I will send out the meeting room information on Thursday morning. Please find the talk details below.

Kind regards, Misha.

---

Automated Feature Extraction from Large Cardiac Electrophysiological Data Sets Peter Hinow University of Wisconsin - Milwaukee March 3, 2022, 12:20 in Zoom

Abstract A new multi-electrode array-based application for the long-term recording of action potentials from electrogenic cells makes possible exciting cardiac electrophysiology studies in health and disease. With hundreds of simultaneous electrode recordings being acquired over a period of days, the main challenge becomes achieving reliable signal identification and quantification. We set out to develop an algorithm capable of automatically extracting regions of high-quality action potentials from terabyte size experimental results and to map the trains of action potentials into a low-dimensional feature space for analysis. Our automatic segmentation algorithm finds regions of acceptable action potentials in large data sets of electrophysiological readings. We use spectral methods and support vector machines to classify our readings and to extract relevant features. We are able to show that action potentials from the same cell site can be recorded over days without detrimental effects to the cell membrane. The variability between measurements 24 h apart is comparable to the natural variability of the features at a single time point. Our work contributes towards a non-invasive approach for cardiomyocyte functional maturation, as well as developmental, pathological, and pharmacological studies. As the human-derived cardiac model tissue has the genetic makeup of its donor, a powerful tool for individual drug toxicity screening emerges.

This is joint work with Stacie Kroboth, Viviana Zlochiver (Advocate Aurora Health) and John Jurkiewicz (UWM).

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

Reminder: this is today.

--------------------------------------------------------------------

On 2022-03-07 09:18, tyomkyn wrote:

Dear all,

This week's speaker is Abhiruk Lahiri (IUUK, Charles University). Please find the talk details below.

Best regards, Misha.

---

Revisiting Convexity Testing Abhiruk Lahiri Charles University March 10, 2022, 12:20 in S6

Abstract In this talk, we will show that the number of distinct discrete derivatives, as opposed to the input size, is a better input parameter to express the complexity of convexity testing. We will present a nonadaptive convexity tester with query complexity O(log s/epsilon) and complement it with a nearly matching lower bound.

Joint work with Ilan Newman and Nithin Varma. Accepted for presentation at SOSA 2022.

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

Reminder: this is today.

----------------------------------

On 2022-03-13 21:45, Mykhaylo Tyomkyn wrote:

Dear all,

This week's speaker is Sam Braunfeld (IUUK, Charles University). Please find the talk details below.

Best regards, Misha.

---

Structure and non-structure in hereditary (graph) classes via model theory Samuel Braunfeld Charles University March 17, 2022, 12:20 in S6

Abstract For monotone graph classes (i.e. closed under subgraph), nowhere denseness is seemingly the most general property dividing classes that admit some sort of structure theory from those that are wild. We will discuss ongoing work to generalize this division to hereditary classes of structures (i.e. closed under induced substructure), using concepts and techniques from model theory.

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

Reminder: this is today.

Misha.

----------------------------------------------------------------------

On 2022-03-21 08:23, Mykhaylo Tyomkyn wrote:

Dear all,

This week's speaker is Gaurav Kucheriya (Charles University). Please find the talk details below.

Best regards, Misha Tyomkyn.

---

Characterization of edge-ordered graphs with nearly linear extremal functions.

Gaurav Kucheriya Charles University March 24, 2022, 12:20 in S6

Abstract The Turán-type extremal theory of graphs asks for the maximal number of edges in a simple graph without containing the forbidden subgraph H. Recently this problem has been studied for edge-ordered graphs which are simple graphs with a linear order on their edges.

In this talk we concentrate on a single result generalizing the simple observation that the Turán-type extremal function of any forbidden forest is linear but the extremal function of a forbidden simple graph with a cycle is much larger. We characterize the forbidden edge ordered graphs with almost linear extremal functions.

This is joint work with Gábor Tardos (Alfréd Rényi Institute of Mathematics).

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

Dear all,

This week's speaker is Ben Moore (Charles University). Please find the talk details below.

Best regards, Misha Tyomkyn.

-------------------------------------------------------------------

A counterexample to a conjecture of Esperet Benjamin Moore Charles University April 7, 2022, 12:20 in S6

Abstract

I'll show that for any integer n, there exists a K_4-free graph G such that G has chromatic number at least n, and every induced subgraph that is triangle free has chromatic number at most 4. Up to changing this 4 to a 3, this is best possible.

Joint work with Alvaro Carbonero, Patrick Hompe, and Sophie Spirkl.

-------------------------------------------------------------------- _______________________________________________ TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

Dear all,

This week's speaker is Jakub Pekárek (Charles University), winner of Jirka Matousek prize 2021. Please find the talk details below.

Best regards, Misha Tyomkyn.

-----------------------------------------------------------------------------------------------

Coloring near-quadrangulations of the torus Jakub Pekárek Charles University April 14, 2022, 12:20 in S6

Abstract The 3-colorability of triangle-free graphs is always guaranteed for graphs embedded in the plane, while NP-complete when triangles are allowed. It is known that in general for any surface, deciding 3-colorability of triangle-free graphs cannot be algorithmically hard and can be reduced to 3-coloring of near-quadrangulations of the given surface. However only for the plane and the projective plane a nice characterization of 3-colorability was known. Our focus is on the graphs embedded in the torus. We design an algorithm capable of deciding 3-colorability of near-quadrangulations in a reasonable time. Based on this result, we derive further characteristics necessary for a triangle-free graph embedded in the torus to not have a 3-coloring and design a practical algorithm for 3-coloring triangle-free graphs embedded in the torus. Based on our ideas, an algorithm for general surfaces was later derived.

Joint work with Zdeněk Dvořák

------------------------------------------------------------------------------------------------

Dear all,

This week's speaker is Jan Volec (ČVUT). Please find the talk details below.

Best regards, Misha Tyomkyn.

-----------------------------------------------------------------------------------------------

Existence of common graphs with large chromatic number Jan Volec Czech Technical University in Prague April 21, 2022, 12:20 in S6

Abstract Ramsey's Theorem states that for every graph H, there is an integer R(H) such that every 2-edge-coloring of R(H)-vertex complete graph contains a monochromatic copy of H. In this talk, we focus on a natural quantitative extension: how many monochromatic copies of H can we find in every 2-edge-coloring of K_N, and, what graphs H are so-called common, i.e., the number of monochromatic copies of H is asymptotically minimized by a random 2-edge-coloring.

A classical result of Goodman from 1959 states that triangle is a common graph. On the other hand, Thomason proved in 1989 that no clique of order at least four is common, and the existence of a common graph with chromatic number larger than three was open until about 10 years ago, when Hatami, Hladky, Kral, Norin and Razborov proved that the 5-wheel is common. In this talk, we show that for every k>4 there exists a common graph with chromatic number k.

This is a joint work with D. Kral and F. Wei

------------------------------------------------------------------------------------------------ _______________________________________________ TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

Dear all,

This week's speaker is Matas Šileikis (Czech Academy of Sciences). Please find the talk details below.

Best regards, Misha Tyomkyn.

-----------------------------------------------------------------------------------------------

Flip processes on dense graphs and dynamical systems Matas Šileikis Czech Academy of Sciences April 28, 2022, 12:20 in S6

Abstract Consider a class of discrete time graph processes, where at each step we choose, uniformly at random, a k-tuple of vertices and transform the subgraph it induces by a predefined rule, for example "if you see a clique, remove all its edges" or "whatever you see, replace it by a random graph G(k,1/2)". We will show how to convert the question about concentration of this process (for a quadratic number of steps) to a dynamical system on a certain normed space of functions. We will consider a few examples of simple rules, and consider a rule which gives rise to a periodic trajectory. Based on work with P. Araújo, F. Garbe, J. Hladký, E. K. Hng and F. Skerman.

------------------------------------------------------------------------------------------------ _______________________________________________ TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

Dear all,

Due to the spring school happening this week, there will be *NO* noon seminar this week. The planned talk has been moved to 19 May.

Best regards, Misha Tyomkyn.

Reminder: this is today.

On 9 May 2022 10:32:41 CEST, Mykhaylo Tyomkyn tyomkyn@kam.mff.cuni.cz wrote:

Dear all,

This week's speaker is Akbar Davoodi (Czech Academy of Sciences). Please find the talk details below.

Best regards, Misha Tyomkyn.

---

Size Ramsey Number of Star Forests Akbar Davoodi Czech Academy of Sciences May 12, 2022, 12:20 in S6

Abstract Given graphs G, H and F, we say that F is Ramsey for (G, H) and we write F → (G, H), if for every edge coloring of F by red and blue, there is either a red copy of G or a blue copy of H in F. The size Ramsey number rˆ(G, H) is defined as the minimum number of edges of a graph F such that F → (G, H). In 1978, Burr, Erdős, Faudree, Rousseau and Schelp conjectured the exact value of rˆ(G, H), whenever G and H are two arbitrary galaxies. In this talk, we give a partial solution to the conjecture by proving it for many pairs (G, H) of star forests.

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

Reminder: this is today.

----------------------------------------------

On 2022-05-16 15:30, Mykhaylo Tyomkyn wrote:

Dear all,

This week's speaker is Tomáš Čížek (Charles University), co-winner of Jirka Matousek prize 2021. Please find the talk details below.

Best regards, Misha Tyomkyn.

---

Implementation of Sprouts: A Graph Drawing Game Tomáš Čížek Charles University May 19, 2022, 12:20 in S6

Abstract Sprouts is a two-player pencil-and-paper game invented by John Conway and Michael Paterson in 1967. In the game, the players take turns in joining dots by curves according to simple rules until one player cannot make a move. The game of Sprouts is very popular and simple-looking, so it may come as a surprise that there are essentially no AI Sprouts players available. This lack of computer opponents is caused by the fact that the game hides a surprisingly high combinatorial complexity and implementing it involves fascinating programming challenges.

We overcome all the implementation barriers and create the first user-friendly Sprouts application with a strong artificial intelligence after more than 50 years of the existence of the game. In particular, we apply results from the theory of nimbers together with new methods based on Delaunay triangulations and crossing-preserving force-directed algorithms to develop a Sprouts implementation with an AI Sprouts player which plays a perfect game on up to 11 spots.

This is a joint work with Martin Balko.

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

Dear all,

This is a reminder that we have a noon lecture today at 12:20. Please find the talk details below.

Best regards, Misha.

--------------------------------------------------------------

Star transposition Gray codes for multiset permutations Torsten Mütze University of Warwick and Charles University May 24, 2022, 12:20 in S6

Abstract Abstract: Given integers k>=2 and a_1,...,a_k>=1, let a:=(a_1,...,a_k) and n:=a_1+...+a_k. An a-multiset permutation is a string of length n that contains exactly a_i symbols i for each i=1,...,k. In this work we consider the problem of exhaustively generating all a-multiset permutations by star transpositions, i.e., in each step, the first entry of the string is transposed with any other entry distinct from the first one. This is a far-ranging generalization of several known results. For example, it is known that permutations (a_1=...=a_k=1) can be generated by star transpositions, while combinations (k=2) can be generated by these operations if and only if they are balanced (a_1=a_2), with the positive case following from the middle levels theorem. To understand the problem in general, we introduce a parameter \Delta(a):=n-2*max {a_1,...,a_k} that allows us to distinguish three different regimes for this problem. We show that if \Delta(a)<0, then a star transposition Gray code for a-multiset permutations does not exist. We also construct such Gray codes for the case \Delta(a)>0, assuming that they exist for the case \Delta(a)=0. For the case \Delta(a)=0 we present some partial positive results. Our proofs establish Hamilton-connectedness or Hamilton-laceability of the underlying flip graphs, and they answer several cases of a recent conjecture of Shen and Williams. In particular, we prove that the middle levels graph is Hamilton-laceable.

This is joint work with Petr Gregor and Arturo Merino

--------------------------------------------------------------

On 2022-05-23 13:27, Mykhaylo Tyomkyn wrote:

Dear all,

This week we have *two* noon lectures, on Tuesday and Thursday:

Torsten Mütze (University of Warwick and Charles University): Star transposition Gray codes for multiset permutations. May 24, 2022, 12:20 in S6.

Arturo Merino (TU Berlin): Greedily generating all bases of a matroid by base exchanges. May 26, 2022, 12:20 in S6.

Please find the abstracts on the webpage https://www.mff.cuni.cz/en/kam/teaching-and-seminars/noon-lectures

I will send out reminders on the days of the talks.

Best regards, Misha Tyomkyn. _______________________________________________ TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

Dear colleagues,

the edge exchange method described in Arturo Merino's noon lecture on May 26 seems to be nearly identical with the memoryless algorithm for computing spanning trees that has appeared in D. Avis and K. Fukuda, "Reverse Search for Enumeration," Discrete Applied Mathematics 6 (1996), 21-46 (see also http://cgm.cs.mcgill.ca/~avis/doc/avis/AF96a.pdf and http://cgm.cs.mcgill.ca/~avis/doc/tutorial.html ).

Best regards, Vašek

Quoting Mykhaylo Tyomkyn tyomkyn@kam.mff.cuni.cz:

Dear all,

This is a reminder that we have a noon lecture by Arturo Merino today at 12:20. Please find the talk details below.

Best regards, Misha.

---

Greedily generating all bases of a matroid by base exchanges Arturo Merino TU Berlin May 26, 2022, 12:20 in S6

Abstract A classical result states that one can generate a spanning tree by repeatedly adding edges such that no cycle is created. More generally, one can compute a base of a matroid in a similar greedy way. We show that one can not only compute one base of a matroid greedily but exhaustively generate them all by a simple base-exchange greedy algorithm. For example, the spanning trees of a graph can be generated by edge exchanges using the following greedy rule: Minimize the larger label of an edge that enters or exits the current spanning tree and which creates a new spanning tree (i.e., that hasn’t been visited already). Amazingly, this works for any graph, for any labeling of its edges, for any initial spanning tree, and regardless of how you choose the edge with the smaller label in each exchange.

In general, for any matroid, we can greedily compute a listing of all its bases matroid such that consecutive bases differ by base exchanges. Furthermore, we can generate these orders using “history-free” iterative algorithms. More specifically, if m is the number of elements in the matroid, we store O(m) bits of data and use O(m) time per base assuming O(1) time independence and coindependence oracles.

During the talk, we will not assume any previous knowledge of matroids and mainly focus on the particular case of spanning trees of graphs.

This is joint work with Torsten Mütze and Aaron Williams.

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

Reminder: this is today. Please note the unusual time and location.

Misha.

---------------------------------------------

On 2022-06-02 09:09, Mykhaylo Tyomkyn wrote:

Dear all,

This week there is no noon lecture.

The last noon lecture of the semester will be on Tuesday, 7 June, and will be given by Jindrich Zapletal, the talk details are given below. Please be aware of the unusual day, time and meeting room.

Best regards, Misha.

---

Coloring graphs on Euclidean spaces Jindrich Zapletal University of Florida / Czech Academy of Sciences June 7, 2022, 15:00 in S5

Abstract For n>0, let Gn be the graph connecting points in Rn of rational Euclidean distance. In ZFC, these graphs all have countable chromatic number. I proved that for every n>0, it is consistent with choiceless set theory that Gn has countable chromatic number while Gn+1 does not, showing that the coloring problem grows in difficulty with n. The proof depends on certain finite combinatorial features of Rn, and the talk will concentrate on these.

---

Reminder: this is today.

-------------------------------------------

On 2022-06-12 11:34, Mykhaylo Tyomkyn wrote:

Dear all,

This week we will have a noon lecture on Thursday 16 June, given by Ian Mertz (University of Toronto). Please find the talk details below.

Best regards, Misha Tyomkyn.

---

Trading Time and Space in Catalytic Branching Programs Ian Mertz University of Toronto June 16, 2022, 12:20 in S6

Abstract An m-catalytic branching program (Girard, Koucký, McKenzie 2015) is a set of m distinct branching programs for f which are permitted to share internal (i.e. non-source non-sink) nodes. While originally introduced as a non-uniform analogue to catalytic space, this also gives a natural notion of amortized non-uniform space complexity for f, namely the smallest value |G|/m for an m-branching program G for f (Potechin 2017).

Potechin (2017) showed that every function f has amortized size O(n), witnessed by an m-catalytic branching program where m = 2^{2^n−1}. We recreate this result by defining a catalytic algorithm for evaluating polynomials using a large amount of space but O(n) time. This allows us to balance this with previously known algorithms which are efficient with respect to space at the cost of time (Cook, Mertz 2020, 2021). We show that for any ϵ ≥ 2n^{−1}, every function f has an m-catalytic branching program of size O_ϵ(mn), where m = 2^2^{ϵn}.

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

Reminder: this is today.

--------------------------------------------

On 2022-07-18 13:13, Mykhaylo Tyomkyn wrote:

Dear all,

This week we will have a noon lecture on Thursday 21 July, given by Jakub Tětek. Please find the talk details below.

Best regards, Misha Tyomkyn.

---

Jakub Tětek Basic Algorithms Research Copenhagen and University of Copenhagen July 21, 2022, 12:20 in S6

Abstract There is a simple O(n^3/eps^2 T) time algorithm for 1+-eps-approximate triangle counting where T is the number of triangles in the graph and n the number of vertices. At the same time, one may count triangles exactly using fast matrix multiplication in time O(n^\omega). Is it possible to get a negative dependency on the number of triangles T while retaining the state-of-the-art n^\omega dependency on n? We answer this question positively by providing an algorithm which runs in time O(n^\omega/T^(\omega - 2)) poly(n^o(1)/eps). This is optimal in the sense that as long as the exponent of T is independent of n, T, it cannot be improved while retaining the dependency on n. Our algorithm improves upon the state of the art when T >> 1 and T << n. We also consider approximate triangle counting in sparse graphs.

The paper is a (shared) best student paper at ICALP 2022.

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

A reminder: this is today.

On 2 October 2022 20:05:48 CEST, Mykhaylo Tyomkyn tyomkyn@kam.mff.cuni.cz wrote:

Dear all,

It is a new semester, and we are resuming the noon seminar series. Our first speaker on Thursday 6 October will be Pedro Araújo. Please find the talk details below.

Best regards, Misha Tyomkyn.

---

Ramsey numbers of cycles in random graphs Pedro Araújo Czech academy of sciences October 6, 2022, 12:20 in S6

Abstract Let G,H be graphs. We write G -> H to say that every blue/red-coloring of the edges of G contains a copy of H whose edges all have the same colour. The study of such property is called Ramsey Theory and it is one of the most fruitful fields of research in Combinatorics.

In general, it is very hard to determine if G -> H, but there are some classes of graphs that make the problem more approachable. Here we consider one example in this class, where H is a cycle on n vertices, denoted by C_n. We call the minimum N such that K_N-> H by R(H), the Ramsey number of H. It is known that R(C_n) = 2n-1 if n is odd and R(C_n) = 3n/2 - 1 if n is even.

Here we transfer this property of the complete graph to random graphs. We consider G=G(N,p) to be a graph on N vertices where each pair belongs to G with probability p=p(N) and we investigate for which functions p(n) we have the property G -> C_n. We show that there exist C>0 such that if p > C/N then with high probability we have G(N,p) -> C_n if N > R(C_n)+C/p. Moreover, the bounds on p and on N are best possible, up to the constant.

This is joint work with Matías Pavez-Signé and Nicolás Sanhueza-Matamala.

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

Reminder: this is today.

On 10 October 2022 09:15:02 CEST, Mykhaylo Tyomkyn tyomkyn@kam.mff.cuni.cz wrote:

Dear all,

There will be a noon lecture this Thursday, 13 October given by Guillermo Gamboa. Please find the talk details below.

Best regards, Misha Tyomkyn.

---

Additive MDS Codes Guillermo Gamboa Charles University October 13, 2022, 12:20 in S6

Abstract:

We introduce the notion of additive nonlinear codes and present some of their properties. We present two examples of additive nonlinear Maximum Distance Separable codes over two different alphabets. Finally, we prove the MDS conjecture for additive nonlinear codes over the alphabet F_9 and F_16, preserving the linearity over F_4 for the latter case. Joint work with Simeon Ball and Michel Lavrauw.

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz _______________________________________________ TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

A reminder: this is today.

On 17 October 2022 09:54:39 CEST, Mykhaylo Tyomkyn tyomkyn@kam.mff.cuni.cz wrote:

Dear all,

There will be a noon lecture this Thursday, 20 October given by Michel Grabisch. Please find the talk details below.

Best regards, Misha Tyomkyn.

---

Random generation of capacities Michel Grabisch University of Paris I Panthéon-Sorbonne and Paris School of Economics October 20, 2022, 12:20 in S6

Abstract Capacities, introduced by Choquet in 1953, are monotone set functions vanishing on the empty set. They are widely used in decision making under risk and uncertainty, multicriteria decision making, game theory (monotone TU-games) and related to many combinatorial problems in Operations Research. In the phase of determining or learning a model based on capacities, it is often important to generate randomly capacities in a uniform way. The problem appears to be surprisingly difficult, due to the monotonicity constraints, and naive methods give poor results, with extremely biased distributions for some coefficients of the capacity. The theoretical exact solution to this problem is however known, since the set of capacities on a finite set N is an order polytope, associated to the Boolean lattice (2 N , ⊆), and generating uniformly random elements in an order polytope amounts to generating all linear extensions of the the underlying poset, that is, in our case, the Boolean lattice. Unfortunately, the number of linear extensions in (2 N , ⊆) grows tremendously with the size of N, and is even not known beyond |N | = 7. This obliges to resort to approximate methods. The literature has produced many such methods, among which the Markov chain approach seems to give the best results.

In this talk, after reviewing most representative methods, we propose a new approximate method, counting a limited number of linear extensions, eliminating linear extensions with very low probability. The basic idea for this is to concentrate on the two top and two bottom layers on the Boolean lattice, and to eliminate one by one maximal elements in the two top layers, and minimal elements in the two bottom layers. For this reason, the method is called 2-layer approximation method. In a second part, we explain how to measure the performance of a given random capacity generator. Our experiments show that our 2-layer approximation method performs equally well as the Markov chain method, while taking much less computation time.

(joint work with Christophe Labreuche and Peiqi Sun)

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz _______________________________________________ TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

A reminder: this is today.

--------------------------------

On 2022-10-24 11:54, Mykhaylo Tyomkyn wrote:

Dear all,

There will be a noon lecture this Thursday, 27 October given by Andres Aranda. Please find the talk details below.

Best regards, Misha Tyomkyn.

---

What I've learned about homogeneity Andrés Aranda Charles University October 27, 2022, 12:20 in S6

Abstract The classical notion of homogeneity in relational structures is about the possibility of extending any local isomorphism (i.e., an isomorphism with finite domain) to an automorphism of the potentially infinite structure. The original Fraïssé theorem establishes a correspondence between homogeneous countable structures and hereditary classes of finite structures with the joint embedding property and the amalgamation property. In this talk, I will present variations on the idea of homogeneity related to the extension of local homomorphisms of different types which can be extended to elements of submonoids of the endomorphism monoid of an infinite structure and explain their analogues of Fraïssé's theorem. If there is enough time, I will also present some structural results about countably infinite homomorphism-homogeneous graphs.

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz _______________________________________________ TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

A reminder: this is today.

-------------------------------

On 2022-10-31 11:29, Mykhaylo Tyomkyn wrote:

Dear all,

There will be a noon lecture this Thursday, 3 November given by Jan Hladký. Please find the talk details below.

Best regards, Misha Tyomkyn.

---

The cut norm and the weak* topology for graphons Jan Hladký Czech Academy of Sciences November 3, 2022, 12:20 in S6

Abstract The cut norm, introduced by Borgs-Chayes-Lovasz-Sos-Szegedy-Vesztergombi is in the heart of the theory of limits of dense graph sequences a.k.a. graphons. With Dolezal, Grebik, Rocha a Rozhon we looked at the relation between this norm and the weak* topology. This view gives a number of insights including an alternative proof of the celebrated Lovasz-Szegedy compactness theorem for graphons.

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

A reminder: this is today.

-----------------------------

On 2022-11-07 10:02, Mykhaylo Tyomkyn wrote:

Dear all,

There will be a noon lecture this Thursday, 10 November given by Jan Volec. Please find the talk details below.

Best regards, Misha Tyomkyn.

---

The sixth Ramsey number is at most 147 Jan Volec Czech Technical University in Prague November 10, 2022, 12:20 in S6

Abstract The diagonal Ramsey number R(k) is the smallest order of a complete graph such that any 2-coloring of its edges contain a monchromatic complete subgraph of order k. It is well known that a*k*2^(k/2) < R(k) < 4^k / k^(b*log(k)) for some absolute constants a>0 and b>0. On the other extreme, we know that R(3)=6 and R(4)=18, but already the exact value of R(5) is not known.

Determining the exact value of R(k) for k>4 is a challenging problem, and a well known quote of Erdos says that if aliens invade the Earth and demand within a year the exact value of R(6), it would be better for the humans to fight the aliens. In this talk, we use the flag algebra method to show R(6) is at most 147 improving on the previous upper bound R(6) <= 165.

This is a joint work with Sergey Norin and Jeremie Turcotte.

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

A reminder: This is today. Please also note a change in topic.

---------------------------------------

On 2022-11-20 16:27, Mykhaylo Tyomkyn wrote:

Dear all,

There will be a noon lecture this Thursday, 24 November given by Pranshu Gupta. Please find the talk details below.

Best regards, Misha Tyomkyn.

---

Ramsey simplicity of random graphs Pranshu Gupta University of Passau November 24, 2022, 12:20 in S6

Abstract A graph $G$ is \emph{$q$-Ramsey} for another graph $H$ if in any $q$-edge-colouring of $G$ there is a monochromatic copy of $H$, and the classic Ramsey problem asks for the minimum number of vertices in such a graph. This was broadened in the seminal work of Burr, Erd\H{o}s, and Lov'asz to the investigation of other extremal parameters of Ramsey graphs, including the minimum degree.

It is not hard to see that if $G$ is minimally $q$-Ramsey for $H$ we must have $\delta(G) \ge q(\delta(H) - 1) + 1$, and we say that a graph $H$ is \emph{$q$-Ramsey simple} if this bound can be attained. Grinshpun showed that this is typical of rather sparse graphs, proving that the random graph $G(n,p)$ is almost surely $2$-Ramsey simple when $\frac{\log n}{n} \ll p \ll n^{-2/3}$. In this paper, we explore this question further, asking for which pairs $p = p(n)$ and $q = q(n,p)$ we can expect $G(n,p)$ to be $q$-Ramsey simple. We resolve the problem for a wide range of values of $p$ and $q$; in particular, we uncover some interesting behaviour when $n^{-2/3} \ll p \ll n^{-1/2}$.

This is a joint work with Simona Boyadzhiyska, Dennis Clemens, and Shagnik Das.

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

A reminder: this is today.

-------------------------------

On 2022-11-28 10:52, Mykhaylo Tyomkyn wrote:

Dear all,

There will be a noon lecture this Thursday, 1 December, given by Martin Balko. Please find the talk details below.

Best regards, Misha Tyomkyn.

---

On Helly numbers of exponential lattices Martin Balko Charles University December 1, 2022, 12:20 in S6

Abstract For every set $S \subseteq \mathbb{R}^2$, the \emph{Helly number of $S$} is the smallest positive integer $N$, if it exists, such that, for every finite family $\mathcal{F}$ of convex sets in~$\mathbb{R}^2$ the following statement is true: if the intersection of any $N$ or fewer members of~$\mathcal{F}$ contains at least one point of $S$, then $\bigcap \mathcal{F}$ contains at least one point of $S$.

We prove that the Helly numbers of exponential lattices ${\alpha^n \colon n \in \mathbb{N}_0}^2$ are finite for every $\alpha>1$ and we determine their exact values in some instances, which in particular solves a problem posed by Dillon. We also fully characterize nondiagonal exponential lattices ${\alpha^n \colon n \in \mathbb{N}_0} \times {\beta^n \colon n \in \mathbb{N}_0}$ with $\alpha,\beta>1$ with finite Helly numbers using results from number theory.

This is a joint work with Gergely Ambrus, Nóra Frankl, Attila Jung, and Márton Naszódi.

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

Dear all,

The last noon lecture in this calendar year will take place this Thursday, 22 December, and will be given by Václav Rozhoň. Please find the talk details below.

Best regards, Misha Tyomkyn.

-----------------------------

Parallel shortest paths and stronger notions of approximate distances. Václav Rozhoň ETH Zurich December 22, 2022, 12:20 in S6

Abstract We will discuss recent advances in the parallel shortest path problem and different definitions of approximate distances. Joint work with Christoph Grunau, Bernhard Haeupler, Anders Martinsson, Goran Zuzic. Paper: https://arxiv.org/pdf/2210.16351.pdf

------------------------------

Dear all,

There will be a noon lecture this Thursday, 2 February, given by Marta Pavelka. Please find the talk details below.

Best regards, Misha Tyomkyn.

-----------------------------

2-LC triangulated manifolds are exponentially many Marta Pavelka University of Miami February 2, 2023, 12:30 in S10

Abstract We introduce "t-LC triangulated manifolds" as those triangulations obtainable from a tree of d-simplices by recursively identifying two boundary (d-1)-faces whose intersection has dimension at least d - t - 1. The t-LC notion interpolates between the class of LC manifolds introduced by Durhuus–Jonsson (corresponding to the case t = 1), and the class of all manifolds (case t = d). Benedetti–Ziegler proved that there are at most 2^(N d^2) triangulated 1-LC d-manifolds with N facets. Here we show that there are at most 2^(N/2 d^3) triangulated 2-LC d-manifolds with N facets.

We also introduce "t-constructible complexes", interpolating between constructible complexes (the case t = 1) and all complexes (case t = d). We show that all t-constructible pseudomanifolds are t-LC, and that all t-constructible complexes have (homotopical) depth larger than d - t. This extends the famous result by Hochster that constructible complexes are (homotopy) Cohen–Macaulay.

This is joint work with Bruno Benedetti. Details of the proofs and more can be found in our paper of the same title.

------------------------------

A reminder: this is today.

------------------------------------------------

On 2023-01-30 12:56, Mykhaylo Tyomkyn wrote:

Addendum: please note the non-standard time and location.

---

On 2023-01-30 12:36, Mykhaylo Tyomkyn wrote:

...

Dear all,

There will be a noon lecture this Thursday, 2 February, given by Marta Pavelka. Please find the talk details below.

Best regards, Misha Tyomkyn.

---

2-LC triangulated manifolds are exponentially many Marta Pavelka University of Miami February 2, 2023, 12:30 in S10

Abstract We introduce "t-LC triangulated manifolds" as those triangulations obtainable from a tree of d-simplices by recursively identifying two boundary (d-1)-faces whose intersection has dimension at least d - t -

1. The t-LC notion interpolates between the class of LC manifolds

introduced by Durhuus–Jonsson (corresponding to the case t = 1), and the class of all manifolds (case t = d). Benedetti–Ziegler proved that there are at most 2^(N d^2) triangulated 1-LC d-manifolds with N facets. Here we show that there are at most 2^(N/2 d^3) triangulated 2-LC d-manifolds with N facets.

We also introduce "t-constructible complexes", interpolating between constructible complexes (the case t = 1) and all complexes (case t = d). We show that all t-constructible pseudomanifolds are t-LC, and that all t-constructible complexes have (homotopical) depth larger than d - t. This extends the famous result by Hochster that constructible complexes are (homotopy) Cohen–Macaulay.

This is joint work with Bruno Benedetti. Details of the proofs and more can be found in our paper of the same title.

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

Apologies, we are in S11

---------------------------

On 2023-02-02 12:19, Mykhaylo Tyomkyn wrote:

A change of location: we are in S9.

---

On 2023-02-02 08:15, Mykhaylo Tyomkyn wrote:

...

A reminder: this is today.

---

On 2023-01-30 12:56, Mykhaylo Tyomkyn wrote:

...

Addendum: please note the non-standard time and location.

---

On 2023-01-30 12:36, Mykhaylo Tyomkyn wrote:

...

Dear all,

There will be a noon lecture this Thursday, 2 February, given by Marta Pavelka. Please find the talk details below.

Best regards, Misha Tyomkyn.

---

2-LC triangulated manifolds are exponentially many Marta Pavelka University of Miami February 2, 2023, 12:30 in S10

Abstract We introduce "t-LC triangulated manifolds" as those triangulations obtainable from a tree of d-simplices by recursively identifying two boundary (d-1)-faces whose intersection has dimension at least d - t

1. The t-LC notion interpolates between the class of LC manifolds

introduced by Durhuus–Jonsson (corresponding to the case t = 1), and the class of all manifolds (case t = d). Benedetti–Ziegler proved that there are at most 2^(N d^2) triangulated 1-LC d-manifolds with N facets. Here we show that there are at most 2^(N/2 d^3) triangulated 2-LC d-manifolds with N facets.

We also introduce "t-constructible complexes", interpolating between constructible complexes (the case t = 1) and all complexes (case t = d). We show that all t-constructible pseudomanifolds are t-LC, and that all t-constructible complexes have (homotopical) depth larger than d - t. This extends the famous result by Hochster that constructible complexes are (homotopy) Cohen–Macaulay.

This is joint work with Bruno Benedetti. Details of the proofs and more can be found in our paper of the same title.

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

A reminder: this is today.

On 20 February 2023 09:39:15 CET, Mykhaylo Tyomkyn tyomkyn@kam.mff.cuni.cz wrote:

Dear all,

There will be a noon seminar this Thursday, 23 February: a prize lecture given by Tomáš Hons, one of the two winners of the Jirka Matousek prize 2022. Please find the talk details below.

Best regards, Misha Tyomkyn.

---

Gadget construction and structural convergence Tomáš Hons (Matousek prize lecture) Charles University February 23, 2023, 12:20 in S6

Abstract Nešetřil and Ossona de Mendez recently proposed a new definition of graph convergence called structural convergence. The structural convergence framework is based on the probability of satisfaction of logical formulas from a fixed fragment of first-order formulas. The flexibility of choosing the fragment allows to unify the classical notions of convergence for sparse and dense graphs. Moreover, it is possible to generalize the graph convergence to convergence of arbitrary L-structures where L is a fixed language. Since the field is relatively young, the range of examples of convergent sequences is limited and only a few methods of construction are known. Our aim is to extend the variety of constructions by considering the gadget construction that appears, e.g., in studies of homomorphisms. In particular, the gadget construction is a natural way of transforming a given structure into a structure of a different language. We show that the gadget construction works well with the structural convergence when restricting to the set of sentences. For the general case, we show counterexamples witnessing that a generalization to the full first-order convergence is not possible without additional assumptions. Moreover, we give several different sufficient conditions to ensure the convergence; one of them states that the resulting sequence is first-order convergent if the replaced edges are dense in the original sequence of structures.

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

A reminder: this is today.

------------------------------------------------------

On 2023-02-27 10:01, Mykhaylo Tyomkyn wrote:

Dear all,

There will be a noon seminar this Thursday, 2 March: a prize lecture given by Denys Bulavka, one of the two winners of the Jirka Matousek prize 2022. Please find the talk details below.

Best regards, Misha Tyomkyn.

---

Weak saturation of multipartite hypergraphs Denys Bulavka (Matousek prize lecture) Charles University March 2, 2023, 12:20 in S6

Abstract Given a host graph H and a pattern graph P, a subgraph G of H is weakly P-saturated in H if the edge set E(H)-E(G) admits an ordering e_1,e_2,.. such that adding these edges in this ordering to G creates a new copy of P at each step containing the newly added edge. Weak saturation was introduced by Bollobas in the 60's, and the main task is to compute the minimum number of edges a weakly P-saturated graph of H can have, so called weak saturation number of P in H. Weak saturation has been studied extensively. For example, if both pattern and host are cliques then the weak saturation number was determined independently by Frankl, Kalai, and Alon; if the pattern is a complete bipartite graph with equal-sized parts, and the host is the clique the weak saturation number was determined by Kalai; the case where both pattern and host are complete d-partite d-uniform hypergraphs was studied first by Alon and later by Moshkovitz and Shapira. In this talk, I will explain our result concerning the case where the pattern and the host are complete d-partite q-uniform hypergraphs, with q at most d, generalizing the above mentioned results of Alon and, Moshkovitz and Shapira.

This is a joint work with Martin Tancer and Mykhaylo Tyomkyn.

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

A reminder: this is today

------------------------------------------------------

On 2024-02-26 09:20, Mykhaylo Tyomkyn wrote:

Dear all,

There will be a noon seminar this Thursday, 29 February: a prize lecture given by Gaurav Kucheriya, one of the three winners of the Jirka Matousek prize 2023. Please find the talk details below.

Best regards, Misha Tyomkyn.

---

A characterization of edge-ordered graphs with almost linear extremal functions Gaurav Kucheriya (Matousek prize lecture) Charles University February 29, 2024, 12:20 in S6

Abstract The Turán-type extremal graph theory aims to determine the maximum number of edges in a simple graph without containing the forbidden subgraph H. Recently this problem has been studied for edge-ordered graphs which are simple graphs with a linear order on their edges by Gerbner, Methuku, Nagy, Pálvölgyi, Tardos and Vizer. In this talk we show that the extremal functions of edge-ordered forests of order chromatic number 2 is almost linear, whereas the extremal function of any other edge-ordered graph is at least n^c, for some c>1. In other words, we characterize the forbidden edge ordered graphs with almost linear extremal functions.

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

A reminder: this is today.

------------------------------------------------------

On 2024-03-04 09:28, Mykhaylo Tyomkyn wrote:

Dear all,

There will be a noon seminar this Thursday, 7 March: a prize lecture given by Tung Anh Vu, one of the three winners of the Jirka Matousek prize 2023. Please find the talk details below.

Best regards, Misha Tyomkyn.

---

Bounds on Functionality and Symmetric Difference – Two Intriguing Graph Parameters Tung Anh Vu (Matousek prize lecture) Charles University March 7, 2024, 12:20 in S6

Abstract [Alecu et al.: Graph functionality, JCTB2021] define functionality (fun), a graph parameter that generalizes graph degeneracy. They research the relation of functionality to many other graph parameters (tree-width, clique-width, VC-dimension, etc.). Extending their research, we prove logarithmic lower bound for functionality of random graph G(n,p) for large range of p. Previously known graphs have functionality logarithmic in number of vertices. We show that for every graph G on n vertices we have fun(G) ≤ O(sqrt(n log n)) and we give a nearly matching Ω(sqrt(n))-lower bound provided by projective planes. Further, we study a related graph parameter symmetric difference (sd), the minimum size of the symmetric difference between the neighbourhood of any two distinct vertices of the “worst possible” induced subgraph. It was observed by Alecu et al. that fun(G) ≤ sd(G)+1 for every graph G. We compare fun and sd for the class INT of interval graphs and CA of circular-arc graphs. We let INT_n denote the n-vertex interval graphs, similarly for CA_n. Alecu et al. ask, whether fun(INT) is bounded. Dallard et al. answer this positively in a recent preprint. On the other hand, we show that Ω(4sqrt(n)) ≤ sd(INT_n) ≤ O(3sqrt(n)). For the related class CA we show that sd(CA_n) = Θ(sqrt(n)). We propose a follow-up question: is fun(CA) bounded?

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

A reminder: this is today.

------------------------------------------------------

On 2024-03-11 09:19, Mykhaylo Tyomkyn wrote:

Dear all,

There will be a noon seminar this Thursday, 14 March, given by Denys Bulavka. Please find the talk details below.

Best regards, Misha Tyomkyn.

---

A Hilton-Milner theorem for exterior algebras Denys Bulavka Hebrew University and Charles University March 14, 2024, 12:20 in S6

Abstract A set family F is pairwise-intersecting if every pair of its members intersect. In 1960, Erdős, Ko, and Rado gave an upper-bound on the size of a pairwise-intersecting family of k-sets coming from a ground set of size n. Moreover, they characterized the families achieving the upper-bound. These are families whose members all share exactly one element, so called trivial families. Later, Hilton and Milner provided the next best upper-bound for pairwise-intersecting families that are non-trivial.

There are several generalizations of the above results. We will focus on the case when the set family is replaced with a subspace of the exterior algebra. In this scenario intersection is replaced with the wedge product, being pairwise-intersecting with self-annihilating and being trivial with being annihilated by a 1-form. Scott and Wilmer, and Woodroofe gave an upper-bound on the dimension of self-annihilating subspaces of the exterior algebra. In the current work we show that the better upper-bound coming from Hilton and Milner's theorem holds for non-trivial self-annihilating subspaces of the exterior algebra.

This talk is based on a joint work with Francesca Gandini and Russ Woodroofe.

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

A reminder: this is today.

-----------------------------------------------------

On 2024-03-25 08:42, Mykhaylo Tyomkyn wrote:

Dear all,

There will be a noon seminar this Thursday, 28 March, given by Todor Antić. Please find the talk details below.

Best regards, Misha Tyomkyn.

---

Star-Forest Decompositions of Complete (Geometric) Graphs Todor Antić Charles University March 28, 2024, 12:20 in S6

Abstract A star-forest is a forest in which every component is a star. A plane star-forest is a star-forest drawn in the plane with no crossings. We deal with the problem of decomposing Complete (Geometric) Graphs into (plane) star-forests. In the Abstract case, it is known that $K_n$ can be decomposed into $\lceil \frac{n}{2}\rceil+1 $ star-forests and that this is is thight. We show that for even $n$, any such forest is "unique" in a certain sense. We also construct Complete Geometric Graphs on $n$ vertices which can be decomposed into $\lceil \frac{n}{2}\rceil +1$ plane star-forests, resolving the conjecture of Pach, Saghafian and Schnider.

This is joint work with Milan Milivojčević and Jelena Glišić

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

A reminder: this is today

-----------------------------------------------------

On 2024-04-01 10:12, Mykhaylo Tyomkyn wrote:

Dear all,

There will be a noon seminar this Thursday, 4 April, given by Torsten Ueckerdt. Please find the talk details below.

Best regards, Misha Tyomkyn.

---

When Surrounding is not Catching in Cops and Robber Torsten Ueckerdt Karlsruhe Institute of Technology April 4, 2024, 12:20 in S6

Abstract After a short introduction of the classical game of Cops and Robber on graphs, we shall discuss two recently introduced variants in which the robber only loses when he is completely surrounded by the cops. In the first variant the robber is surrounded when he sits at a vertex v and there is at least one cop on each neighbor of v. In the second variant cops occupy edges of the graph and the robber (still moving on vertices) is surrounded if he sits at a vertex v and there is at least one cop on each incident edge at v. We shall compare these games with each other and also with the classical game in which the robber is already caught when one cop sits on the same vertex as the robber.

This is joint work with Paul Jungeblut, Minh Tuan Ha and Samuel Schneider.

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

A reminder: this is today.

------------------------------------------------------

On 2024-04-29 06:49, Mykhaylo Tyomkyn wrote:

Dear all,

There will be a noon seminar this Thursday, 2 May, given by Sofia Brenner. Please find the talk details below.

Best regards, Misha Tyomkyn.

---

From graphs to groups: Tuple regularity and $k$-ultrahomogeneity Sofia Brenner TU Darmstadt May 2, 2024, 12:20 in S6

Abstract Tuple regularity and $k$-ultrahomogeneity are refinements of the classical notion of ultrahomogeneity, which is a well-studied symmetry notion of graphs, or, more generally, of relational structures. For many graph classes, all of these concepts are well-understood.

Ultrahomogeneity has also been studied for groups. In particular, the ultrahomogeneous finite groups were classified by Li (1999) and, independently, by Cherlin and Felgner (2000). However, especially in order to study finite groups from a combinatorial perspective, we are interested in refinements of this notion for groups.

In this talk, I will discuss the concepts of $k$-ultrahomogeneity and $k$-tuple regularity for various graph classes, and define suitable analogs for groups. At the end, I will briefly discuss a classification result for finite groups.

Parts of this talk are based on joint work with Irene Heinrich.

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

A reminder: this is today.

------------------------------------------------------

On 2024-05-06 05:37, Mykhaylo Tyomkyn wrote:

Dear all,

There will be a noon seminar this Thursday, 9 May, given by Matěj Konečný. Please find the talk details below.

Best regards, Misha Tyomkyn.

---

EPPA numbers of graphs Matěj Konečný TU Dresden May 9, 2024, 12:20 in S6

Abstract If G is a graph, A, B its induced subgraphs and f: A -> B an isomorphism, we say that f is a partial automorphism of G. In 1992, Hrushovski proved that graphs have the extension property for partial automorphisms (EPPA, also called the Hrushovski property), that is, for every finite graph G there is a finite graph H, its EPPA-witness, such that G is an induced subgraph of H and every partial automorphism of G extends to an automorphism of H. The EPPA number of a graph G, denoted by eppa(G), is the smallest number of vertices of an EPPA-witness for G, and we put eppa(n) = max{eppa(G) : |G| = n}.

I plan to introduce the area and many of its (nice if I may say so) open problems, and discuss some recent advances. This is joint work with Bradley-Williams, Cameron, and Hubička.

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

A reminder: this is today.

-------------------------------------------------------

On 2024-05-13 07:05, Mykhaylo Tyomkyn wrote:

Dear all,

There will be a noon seminar this Thursday, 16 May, given by Daniela Opočenská. Please find the talk details below.

Best regards, Misha Tyomkyn.

---

Repetitions in sequences Daniela Opočenská Czech Technical University in Prague May 16, 2024, 12:20 in S6

Abstract Two of the fundamental questions in the area of combinatorics on words are the following: Is there an infinite sequence of letters over a binary alphabet that contains no cubes, i.e., no word repeating consecutively three times? Is there an infinite sequence over a ternary alphabet that contains no squares, i.e., no word repeating consecutively two times?

Both of these questions were affirmatively answered by Axel Thue in the beginning of the 20th century. It is clear that some repetitions have to occur in any infinite sequence over a finite alphabet. The maximum repetition rate in a sequence is captured by the notion of the critical exponent. The critical exponent of any sequence is greater than 1, and it is natural to ask what is the smallest possible critical exponent for a given class of sequences. For example, the sequences in Thue's answers must have their critical exponents at most 3 and at most 2, respectively. In fact, the sequence answering the second question has the critical exponent equal to 2, and it is known as the Thue-Morse sequence.

In this talk, we first introduce the required notions and explain how to compute the critical exponent for certain classes of sequences. After that, we will present our recent results concerning the minimal critical exponent. This talk is based on joint works with Ľ. Dvořáková, E. Pelantová, A. M. Shur, J. Currie, P. Ochem, N. Rampersad, and J. Shallit.

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

A reminder: this is today.

-------------------------------------------------------

On 2024-05-20 09:04, Mykhaylo Tyomkyn wrote:

Dear all,

There will be a noon seminar this Thursday, 23 May, given by Yvo Ad Meeres. Please find the talk details below.

Best regards, Misha Tyomkyn.

---

Finite State Automata accepting Directed Acyclic Graphs Yvo Ad Meeres University of Bremen May 23, 2024, 12:20 in S6

Abstract Analogously to regular string and tree languages, regular languages of directed acyclic graphs (DAGs) have been defined in literature. Although called regular, those DAG-languages are way more powerful and, consequently, standard problems have a higher complexity than in the string case. Top-down as well as bottom-up deterministic DAG languages are subclasses of the regular DAG languages. We refine this hierarchy by providing a weaker subclass of the deterministic DAG languages. For a DAG grammar generating a language in this new DAG language class, or, equivalently, a DAG-automaton recognizing it, a classical deterministic finite state automaton (DFAs) can be constructed. As the main result, we provide a characterization of this class. The motivation behind this is the transfer of techniques for regular string languages to graphs. Trivially, our restricted DAG language class is closed under union and intersection, and permits the application of minimization and hyper-minimization algorithms known for DFAs. The alternative notion of regularity coins at the existence of a DFA for recognizing a DAG language.

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

Dear All,

Let me mention that this week we organize a problem-solving workshop in discrete geometry. Before the noon seminar on Thursday, we will have a PROGRESS REPORT (STARTING 10:45 OR 11). Everybody interested can come to see what problems we consider and what are our results so far. We will still send an info about the exact time and place of the progress report.

Best regards, Maria Saumell, Martin Balko and Pavel Valtr (organizers of the workshop)

before the noon seminar, there will be a progress report of our

On Tue, 25 Jun 2024, Mykhaylo Tyomkyn wrote:

Dear all,

There will be a noon seminar this Thursday, 27 June, given by Gelasio Salazar. Please find the talk details below (note the different from usual room).

Best regards, Misha Tyomkyn.

---

Applications of combinatorics to knot theory Gelasio Salazar Universidad Autónoma de San Luis Potosí, Mexico June 27, 2024, 12:20 in S8

Abstract If we project a knot to a plane we obtain a 2-dimensional curve, a shadow of the knot. Except for very special cases, a shadow does not determine a knot: in general, more than one knot can be projected to a given shadow. The relevant question is: which properties of a knot can be obtained from its shadow? In this talk we will illustrate how standard techniques from topological and extremal graph theory can be used to investigate this problem. No previous knot theory knowledge is expected from the audience (and very little knot theory knowledge should be expected from the speaker).

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

A reminder: this is today.

------------------------------------------------------

On 2023-03-06 09:11, Mykhaylo Tyomkyn wrote:

Dear all,

There will be a noon seminar this Thursday, 9 March, given by Yangyan Gu. Please find the talk details below.

Best regards, Misha Tyomkyn.

---

Refined list version of Hadwiger’ conjecture Yangyan Gu Charles University and Zhejiang Normal University March 9, 2023, 12:20 in S6

Abstract The concept of \lambda-choosability is a refinement of choosability that puts k-choosability and k-colourability in the same framework. If |\lambda| is close to k_\lambda, then \lambda-choosability is close to k_\lambda-colourability; if |\lambda| is close to 1, then \lambda-choosability is close to k_\lambda-choosability. We study Hadwiger's Conjecture in the context of such a refined list colouring. Hadwiger's Conjecture is equivalent to saying that every K_t-minor-free graph is {1 \star (t-1)}-choosable for any positive integer t. We prove that for t >= 5, for any partition \lambda of t-1 other than {1 \star (t-1)}, there is a K_t-minor-free graph G that is not \lambda-choosable. We then construct several types of K_t-minor-free graphs that are not \lambda-choosable, where k_\lambda-(t-1) gets larger as k_\lambda-|\lambda| gets larger.

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

A reminder: this is today.

On 13 March 2023 09:29:29 CET, Mykhaylo Tyomkyn tyomkyn@kam.mff.cuni.cz wrote:

Dear all,

There will be a noon seminar this Thursday, 16 March, given by Jailu Zhu. Please find the talk details below.

Best regards, Misha Tyomkyn.

---

The generalization of Ohba conjecture Jailu Zhu Charles University and Zhejiang Normal University March 16, 2023, 12:20 in S6

Abstract It is well-known that there is a big gap between k-colourability and k-choosability. In particular, bipartite graphs can have arbitrary large choice number. An interesting problem is for which graphs G, chromatic number equals to choice number. Such graphs are called chromatic-choosable. There are a few challenging conjectures that assert certain families of graphs are chromatic-choosable. The most famous problem concerning this concept is perhaps the list coloring conjecture, which asserts that line graphs are chromatic-choosable. Another problem concerning chromatic-choosable graphs is the minimum order of a non-chromatic-choosable graph with given chromatic number.

For a positive integer k, let f(k) be the minimum n such that there is a non k-choosable k-chromatic n-vertex graph. Ohba conjectured that f(k) is at least 2k+2 and this conjecture was finally confirmed by Noel, Reed and Wu in 2014. Intuitively, the reason that a k-colourable graph fails to be L-colourable for a k-list assignment L is due to the fact that lists assigned to vertices by L may be complicately entangled. In 2019, Xuding Zhu put restrictions on the entanglements of lists that are allowed to be assigned to the vertices, and hence builds a refined scale for measuring choosability of graphs.

Now, we consider the similar Ohba problem under that refined scale. For a multi set lambda of k_lambda, we define f(lambda) similarly and we can determine the value of f(lambda) for all lambda.

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

A reminder: this is today.

-------------------------------------------------------

On 2023-03-21 08:24, Mykhaylo Tyomkyn wrote:

Dear all,

There will be a noon seminar this Thursday, 23 March, given by Eng Keat Hng. Please find the talk details below.

Best regards, Misha Tyomkyn.

---

Approximating fractionally isomorphic graphons Eng Keat Hng Czech Academy of Sciences March 23, 2023, 12:20 in S6

Abstract First introduced by Tinhofer in 1986, fractional isomorphism of finite graphs is an important and well-studied concept at the intersection of graph theory and combinatorial optimization. It has many different characterizations that involve a range of very different and seemingly unrelated properties of graphs. Recently, Grebík and Rocha developed a theory of fractional isomorphism for graphons, i.e. limits of dense graph sequences, where they showed that every characterization of fractional isomorphism in graphs has a well-defined graphon counterpart and that these are indeed all equivalent characterizations of fractional isomorphism for graphons. They asked whether fractionally isomorphic graphons can be characterized as the limits of graph sequences which are entry-wise fractionally isomorphic (in the graph sense). We answer their question in the affirmative.

This is joint work with Jan Hladký.

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

Dear all,

This week there will be no noon seminar. We shall reconvene next week.

Best regards, Misha Tyomkyn.

A reminder: this is today. Followed by a kampauza at 13:15 (snacks on 3rd floor) and a colloquium talk at 14:00.

Misha Tyomkyn.

On 3 April 2023 09:50:19 CEST, Mykhaylo Tyomkyn tyomkyn@kam.mff.cuni.cz wrote:

Dear all,

There will be a noon seminar this Thursday, 6 April, given by Kristýna Pekárková. Please find the talk details below.

Best regards, Misha Tyomkyn.

---

Preconditioners for matrix sparsity Kristýna Pekárková Masaryk University April 6, 2023, 12:20 in S6

Abstract An intensive line of research on fixed parameter tractability of integer programming is focused on exploiting the relation between the sparsity of a constraint matrix A and the norm of the elements of its Graver basis. In particular, integer programming is fixed parameter tractable when parameterized by the primal tree-depth and the entry complexity of A, and when parameterized by the dual tree-depth and the entry complexity of A; both these parameterizations imply that A is sparse, in particular, the number of its non-zero entries is linear in the number of columns or rows, respectively.

We study preconditioners transforming a given matrix to an equivalent sparse matrix if it exists and provide structural results characterizing the existence of a sparse equivalent matrix in terms of the structural properties of the associated column matroid. In particular, our results imply that the ℓ₁-norm of the Graver basis is bounded by a function of the maximum ℓ₁-norm of a circuit of A. We use our results to design a parameterized algorithm that constructs a matrix equivalent to an input matrix A that has small primal/dual tree-depth and entry complexity if such an equivalent matrix exists.

Our results yield parameterized algorithms for integer programming when parameterized by the ℓ₁-norm of the Graver basis of the constraint matrix, when parameterized by the ℓ₁-norm of the circuits of the constraint matrix, when parameterized by the smallest primal tree-depth and entry complexity of a matrix equivalent to the constraint matrix, and when parameterized by the smallest dual tree-depth and entry complexity of a matrix equivalent to the constraint matrix.

The talk is based on the results of joint work with M. Briański, M. Koutecký, D. Kráľ, and F. Schröder.

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

A reminder: this is today.

On 11 April 2023 09:23:45 CEST, Mykhaylo Tyomkyn tyomkyn@kam.mff.cuni.cz wrote:

Dear all,

There will be a noon seminar this Thursday, 13 April, given by Jan Legerský. Please find the talk details below.

Best regards, Misha Tyomkyn.

---

On the flexibility of tessellations Jan Legerský Czech Technical University in Prague April 13, 2023, 12:20 in S6

Abstract A bar-joint framework, which is a (possibly countably infinite) graph together with a realization of its vertices in the plane, is called flexible if it can be continuously deformed while preserving the distances between adjacent vertices, otherwise it is called rigid. In general, deciding rigidity/flexibility of a given finite framework is NP-hard, but there are more tractable subclasses. For instance Bolker and Crapo showed that rigidity of a braced finite grid of squares is determined by connectedness of an auxiliary bipartite graph. We focus on finite and infinite frameworks that "consist of triangles and parallelograms", for which a certain equivalence relation defined on the set of edges can be used to decide flexibility. We illustrate the result on the 1-skeleta of plane tessellations. We shall also discuss the rotationally symmetric case.

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

A reminder: this is today.

------------------------------------------------------

On 2023-04-17 10:47, Mykhaylo Tyomkyn wrote:

Dear all,

There will be a noon seminar this Thursday, 20 April, given by Diana Piguet. Please find the talk details below.

Best regards, Misha Tyomkyn.

---

The tree-packing conjecture for trees of nearly linear maximal degree Diana Piguet Czech Academy of Sciences April 20, 2023, 12:20 in S6

Abstract Gyárfás conjectured in 1978 that the edges of the complete graph on n vertices decomposes into any family of trees (T1, T2, ..., Tn), with |V(Ti)|=i. We'll present a solution to this conjecture for families of trees of maximum degree at most c n/(log n), for some fixed c>0.

This is joint work with Peter Allen, Julia Böttcher, Denis Clemens, Jan Hladký, and Anusch Taraz.

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

A reminder: this is today.

-----------------------------------------------------------

On 2023-05-01 20:09, Mykhaylo Tyomkyn wrote:

Dear all,

This Thursday, 4 May, we will have TWO noon lectures. The first lecture will be given by Peter Hinow, at the usual time 12:20. Afterwards, we will have a second lecture, given by Ioannis Eleftheriadis, starting at 13:10. Please find the talk abstracts below.

Misha Tyomkyn.

---

Ergodicity and loss of capacity for a random family of concave maps Peter Hinow University of Wisconsin - Milwaukee May 4, 2023, 12:20 in S6

Abstract Random fluctuations of an environment are common in ecological and economical settings. We consider a family of concave quadratic polynomials on the unit interval that model a self-limiting growth behavior. The maps are parametrized by an independent, identically distributed random parameter. What in the deterministic setting would be a single fixed point is now replaced by an invariant measure, which is a fixed point of the Perron-Frobenius operator. In select cases, we show the existence of a unique invariant ergodic measure of the resulting random dynamical system. Moreover, there is an attenuation of the mean of the state variable compared to the constant environment with the averaged parameter. This is joint work with Ami Radunskaya (Pomona College, Pomona, CA).

---

Towards a characterisation of universal categories of relational structures Ioannis Eleftheriadis University of Cambridge May 4, 2023, 13:10 in S6

Abstract Answering a conjecture of Konig, Frucht first established that every finite group is isomorphic to the automorphism group of a finite graph. Since then, there has been a series of results regarding the representation of groups in various finite and infinite structures. These culminated in the work of Isbel, who initiated the study of algebraically universal categories, i.e. those that fully embed every category of universal algebras. In this talk, I'll discuss recent work that establishes a partial characterisation of algebraically universal categories of relational structures, given in terms of a sparsity notion known as nowhere density and its model-theoretic consequences. This extends a result of Nesetril-Ossona de Mendez on categories of finite graphs to the context of categories of relational structures of unbounded size.

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

A reminder: this is today.

-----------------------------------------------------

On 2023-05-09 09:47, Mykhaylo Tyomkyn wrote:

Dear all,

There will be a noon seminar this Thursday, 11 May, given by Félix Moreno Peñarrubia. Please find the talk details below.

Best regards, Misha Tyomkyn.

---

A Computational Approach for Finding 6-List-Critical Graphs on the Torus Félix Moreno Peñarrubia Charles University and UPC May 11, 2023, 12:20 in S6

Abstract Coloring problems on graphs embedded on surfaces is an old and well-studied area of graph theory. Thomassen proved that there are finitely many 6-critical graphs on any fixed surface and provided the explicit list of 6-critical graphs on the torus. Later, Postle proved that there are finitely many 6-list-critical graphs on any fixed surface. With the goal of finding the list of 6-list-critical graphs on the torus, we develop and implement algorithmic techniques for computer search of critical graphs in different list-coloring settings.

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

A reminder: this is today.

-----------------------------------------------------

On 2023-05-15 07:54, Mykhaylo Tyomkyn wrote:

Dear all,

There will be a noon seminar this Thursday, 18 May, given by Michal Cizek. Please find the talk details below.

Best regards, Misha Tyomkyn.

---

Profinite graphs and their automorphisms Michal Cizek University of Western Ontario May 18, 2023, 12:20 in S6

Abstract There is an important interplay between group theory and graph theory. Using notions such as covering spaces or free actions of groups on graphs, one can describe group theoretical notions such as a free and amalgamated product using graph structures. That is the foundation for Bass-Serre theory, developed in the 1970s. While the covering spaces of graphs are a great tool for describing abstract groups, they are not so effective for Galois/Profinite groups, which are topological by their nature. Thus, to apply the ideas from Bass-Serre theory to profinite groups, we require graphs that are topological as well. Such graphs are called profinite graphs and were extensively studied by Ribes and Zaleskii.

The goal of this talk is to, in the first part, introduce profinite graphs and basic notions on them such as their topology, connectivity, and automorphisms. In the second part, we will focus on one application of profinite graphs, which shows that profinite groups can be represented as certain continuous bijections over a compact space, solving a conjecture made by Sidney Morris and Karl Hoffmann.

This lecture is meant for a broad audience. Its goal is to introduce the idea of adding a profinite structure on graphs and will provide some informal motivation of key notions. My research has been supported by the University of Western Ontario and Western Academy for Advanced Research.

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

A reminder: this is today.

-------------------------------------------------------

On 2023-10-09 08:31, Mykhaylo Tyomkyn wrote:

Dear all,

We are resuming the noon seminar series. There will be a noon seminar this Thursday, 12 October, given by Jack Allsop.

Please find the talk details below. Best regards,

Misha Tyomkyn.

---

Row-Hamiltonian Latin squares and perfect 1-factorisations Jack Allsop Monash University October 12, 2023, 12:20 in S6

Abstract A Latin square of order $n$ is an $n \times n$ matrix of $n$ symbols, such that each symbol occurs exactly once in each row and column. Let $L$ be a Latin square of order $n$. Each pair of distinct rows of $L$ forms a $2$-line permutation. If this permutation is a single $n$-cycle, for any choice of rows, then $L$ is called row-Hamiltonian. Each Latin square has six conjugate Latin squares, obtained by uniformly permuting the coordinates of its $(\text{row}, \text{column}, \text{symbol})$ triples. Let $\nu(L)$ denote the number of conjugates of $L$ which are row-Hamiltonian. It is known that $\nu(L) \in {0, 2, 4, 6}$ and for each $m \in {0, 2, 6}$ there are known infinite families of Latin squares with $\nu = m$. We construct the first known infinite family of Latin squares with $\nu=4$.

A $1$-factorisation of a graph is a partition of its edge set into $1$-factors. A $1$-factorisation is perfect if the union of edges in any pair of its $1$-factors forms a Hamiltonian cycle. A perfect $1$-factorisation of the complete bipartite graph $K_{n, n}$ is equivalent to a row-Hamiltonian Latin square of order $n$. Our family of Latin squares with $\nu=4$ allows us to build the eighth known infinite family of perfect $1$-factorisations of complete bipartite graphs.

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

Dear all,

This weak there will be no noon seminar. We shall resume next week.

Kind regards, MT

A reminder: this is today.

On 2023-10-23 12:27, Mykhaylo Tyomkyn wrote:

Dear all,

There will be a noon seminar this Thursday, 26 October, given by Lenka Ptáčková.

Please find the talk details below. Best regards,

Misha Tyomkyn.

---

A simple and complete discrete exterior calculus on general polygonal meshes Lenka Ptáčková Charles University October 26, 2023, 12:20 in S6

Abstract Discrete exterior calculus (DEC) offers a coordinate–free discretization of exterior calculus especially suited for computations on curved spaces. We present a new version of DEC on surface meshes formed by general polygons, possibly non–planar and non–convex. Unlike previous approaches in DEC, our framework bypasses the need for combinatorial subdivision and does not involve any dual mesh.

At its core, our approach introduces a new polygonal wedge product that is compatible with the discrete exterior derivative as it satisfies the Leibniz product rule. Based on the discrete wedge product, we derive a novel primal–to–primal Hodge star operator. Combining these three 'basic operators' we then define new discrete versions of the contraction operator, Lie derivative, codifferential, and Laplace operator. We discuss the numerical convergence of the proposed operators and compare them to existing DEC methods. Finally, we show simple applications of our operators on Helmholtz–Hodge decomposition of vector fields, Laplacian surface fairing, and Lie advection of functions and vector fields on meshes formed by general polygons.

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

A reminder: this is today

------------------------------------------------------

On 2023-11-06 09:15, Mykhaylo Tyomkyn wrote:

Dear all,

There will be a noon seminar this Thursday, 9 November, given by Josef Tkadlec.

Please find the talk details below. Best regards,

Misha Tyomkyn.

---

Fixation times in Moran process on directed graphs Josef Tkadlec Charles University November 9, 2023, 12:20 in S6

Abstract Introduced in 1958 in the field of population genetics, Moran process is a stochastic process that models the long-term fate of a newly occurring mutation, as it attempts to spread through a population of reproducing individuals. The spatial structure of the population can be represented by a graph, where nodes correspond to individuals and edges to their interactions. The Moran process then changes the vertex coloring of the graph, one vertex at a time. Eventually, the mutants either take over the whole graph, an event called fixation, or they disappear completely.

The two most studied quantities are the fixation probability of the new mutant, and the fixation time, that is, the expected number of steps until the process terminates. Both quantities critically depend on the graph structure and are believed to be hard to compute exactly for arbitrary graphs. In 2014, Diaz, Goldberg, Mertzios, Richerby, Serna, and Spirakis showed that for any undirected graph the fixation time is polynomially short, and thus fixation probability can be efficiently approximated by simulations. We consider directed graphs. We present an upper bound for the fixation time, and we show that this upper bound is polynomial for a broad class of directed graphs that includes most families of directed graphs that were previously studied in the context of Moran process.

---

A reminder: this is today

On 13 November 2023 12:16:47 CET, Mykhaylo Tyomkyn tyomkyn@kam.mff.cuni.cz wrote:

Dear all,

There will be a noon seminar this Thursday, 16 November, given by Guillaume Aubian. Please find the talk details below.

Best regards, Misha Tyomkyn.

---

Towards a directed analogue of Gyárfás-Sumner conjecture! Guillaume Aubian Charles University November 16, 2023, 12:20 in S6

Abstract In 1982, Victor Neumann-Lara introduced the dichromatic number, a directed analogue of the chromatic number for directed graphs. Since then, this novel idea has been successfully used to extend results and conjectures on undirected graphs to the realm of directed graphs.

One of the most important conjecture in graph colouring is the Gyárfás-Sumner conjecture, which seeks to describe the induced subgraphs that must necessarily appear in graphs of sufficiently large chromatic number. However, this conjecture remains widely open. In 2019, Aboulker, Charbit and Naserasr described an analogue conjecture for the dichromatic number, based upon the concept of heroes, a notion initially introduced by Berger, Choromanski, Chudnovsky, Fox, Loebl, Scott, Seymour and Thomassé.

In the pursuit of solving this problem, significant progress has been achieved, including the refutation of certain aspects of the original conjecture: we provide an overview of these advances.

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

A reminder: this is today.

------------------------------------------------------

On 2023-11-20 10:21, Mykhaylo Tyomkyn wrote:

Dear all,

There will be a noon seminar this Thursday, 23 November, given by Anna Limbach. Please find the talk details below.

Best regards, Misha Tyomkyn.

---

Anna Limbach Czech Academy of Sciences November 23, 2023, 12:20 in S6

Abstract We prove that the clique graph operator k is divergent on a (not necessarily finite) locally cyclic graph G with minimum degree δ ≥ 6 if and only if the universal triangular cover of G contains arbitrarily large triangular-shaped subgraphs. For finite G, this is equivalent to G being 6-regular.

A graph is called locally cyclic if the open neighbourhood N_G(v) of each vertex v induces a cycle. The clique graph kG of a graph G has the maximal complete subgraphs of G as its vertices and its edges are those pairs with non-empty intersection. The (n+1)-st iterated clique graph is recursively defined as the clique graph of the n-th iterated clique graph. If all iterated clique graphs of G are non-isomorphic, the graph G is called k-divergent; otherwise, it is k-convergent.

While it has been shown for finite locally cyclic graphs that those with minimum degree δ ≥ 7 are k-convergent while the 6-regular ones are k-divergent, we obtain a full characterisation of k-convergent locally cyclic graphs with minimum degree δ ≥ 6.

We start by showing that a k-convergent connected graph has a k-convergent universal triangular cover. Conversely, we give a sufficient condition under which the clique convergence of the universal triangular cover of a graph implies the clique convergence of the graph itself.

Locally cyclic graphs with minimum degree δ ≥ 6 which are triangularly simply connected are their own universal covers. On this class, clique convergence is characterised using an explicit construction of the iterated clique graphs and a finite yet divergent parameter for the k-divergent case. Furthermore, it is shown that locally cyclic graphs with minimum degree δ ≥ 6 are k-convergent if and only if their universal covers are k-convergent. This way, the characterisation is completed.

This is joint work with Markus Baumeister and Martin Winter.

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

A reminder: this is today.

-----------------------------------------------------

On 2023-11-27 22:06, Mykhaylo Tyomkyn wrote:

Dear all,

There will be a noon seminar this Thursday, 30 November, given by Felix Schröder. Please find the talk details below.

Best regards, Misha Tyomkyn.

---

Cell coloring and Tutte's 3-flow conjecture Felix Schröder Charles University November 30, 2023, 12:20 in S6

Abstract We introduce cell colorings of drawings of graphs in the plane. By the 4-color theorem, every drawing of a bridgeless graph has a cell 4-coloring. A drawing of a graph is cell 2-colorable if and only if the underlying graph is Eulerian. We will also see that every graph without degree 1 vertices admits a cell 3- colorable drawing. The hardest question however is: When can every drawing of a graph be cell 3-colored? We show that every 4-edge-connected graph and every graph admitting a nowhere-zero 3-flow is universally cell 3-colorable. We also discuss circumstances under which universal cell 3-colorability guarantees the existence of a nowhere-zero 3-flow because of its connection to the 3-flow-conjecture. We make a generalized 3-flow conjecture and prove our conjecture for subcubic and for K3,3-minor-free graphs.

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

A reminder: this is today.

-----------------------------------------------------

On 2024-01-08 09:59, Mykhaylo Tyomkyn wrote:

Dear all,

There will be a noon seminar this Thursday, 11 January, given by Marek Eliáš. Please find the talk details below.

Best regards, Misha Tyomkyn.

---

Learning-Augmented Algorithms with Explicit Predictors Marek Eliáš Bocconi University January 11, 2024, 12:20 in S6

Abstract In the field of algorithmic design, there has been recent progress in utilizing predictions from machine learning models applied to the input data (or historical data). These approaches have demonstrated an enhancement in performance when the predictions are accurate, while also ensuring robustness by providing worst-case guarantees when predictions fail. In this manuscript we focus on online problems; prior research in this context has generally treated the machine learning algorithm as a black-box with unspecified training methods. In contrast, in this work, we unpack the algorithm and examine the learning problem it gives rise to, with the ultimate goal of designing online learning algorithms specifically tailored for the algorithmic task at hand. Adopting this perspective, we turn our attention to a number of fundamental problems, including caching and scheduling, which have been well-studied in the black-box setting. For each of the problems we consider, we introduce new algorithms that take advantage of explicit learning algorithms which we carefully design towards optimizing the overall performance. We demonstrate the potential of our approach by deriving performance bounds that show improvement over those established in previous work. Joint work with Haim Kaplan, Yishay Mansour, Shay Moran.

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz

A reminder: this is today

------------------------------------------------------

On 2024-02-05 10:53, Mykhaylo Tyomkyn wrote:

Dear all,

There will be a noon seminar this Thursday, 8 February, given by Tinaz Ekim. Please find the talk details below.

Best regards, Misha Tyomkyn.

---

Extremal Triangle-free Graphs Tinaz Ekim Bogazici University February 8, 2024, 12:20 in S6

Abstract In this talk, we will address an extremal problem from two perspectives: structural graph theory and Integer Programming (IP). We will determine the maximum number of edges in a triangle-free graph when its maximum degree is at most d and its matching number is at most m for two given integers d and m. We will derive structural properties of extremal triangle-free graphs, which will allow us i) to provide a formula for this maximum number which is valid in most cases, ii) to develop an IP formulation for constructing extremal graphs, which has surprising links with the classical Knapsack problem. We conjecture that our formula giving the size of extremal triangle-free graphs is also valid for all the open cases and endorse this conjecture by solving the IP formulation for some additional cases

---

---

TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz