20.01.2015, Maciej Poleski 
An online version of Rota's basis conjecture 

Rota’s basis conjecture states that in any square array of vectors whose rows
are bases of a fixed vector space the vectors can be rearranged within their
rows in such a way that afterwards not only the rows are bases, but also the
columns. We discuss an online version of this conjecture, in which the
permutation used for rearranging the vectors in a given row must be determined
without knowledge of the vectors further down the array. The paper contains
surprises both for those who believe this online basis conjecture at first
glance, and for those who disbelieve it. 

references: Guus P. Bollen, Jan Draisma, An online version of Rota’s basis conjecture, Journal of Algebraic Combinatorics, October 2014

13.01.2015, Helena Borak 
Variants of Hat Guessing Games 

Hat problems have become a popular topic in recreational mathematics. In a typical hat
problem, each of n players tries to guess the color of the hat they are wearing by looking at
the colors of the hats worn by some of the other players. In this paper we consider several
variants of the problem, united by the common theme that the guessing strategies are required to be deterministic and the objective is to maximize the number of correct answers in the worst case. We also summarize what is currently known about the worstcase analysis of deterministic hatguessing problems with a finite number of players. 

references: S.Butler, M.T.Hajiaghayi, R.D.Kleinberg, T.Leighton, Hat Guessing Games

16.12.2014, Marcin Dziaduś 
Fivelistcoloring of planar graphs 

Let G be a plane graph with outer cycle C, let u,v be vertices of C and let (L(x):x in V(G)) be a family of sets such that L(u)=L(v)=2, L(x) has at least three elements for every vertex x of C \ {u,v} and L(x) has at least five elements for every vertex x of G \ V(C). We prove a conjecture of Hutchinson that G has a proper coloring f such that f(x) belongs to L(x) for every vertex x of G. 

references: Luke Postle, Robin Thomas, Fivelistcoloring graphs on surfaces I. Two lists of size two in planar graphs, Journal of Combinatorial Theory, Series B

09.12.2014, Karol Banyś 
Online Load Balancing and Correlated Randomness 

This paper looks at online load balancing, in
a setting where each job can only be served by a subset of
the servers. The subsets are revealed only on arrival, and
can be arbitrary. The cost of an allocation is the sum of
cost for each server, which in turn is a convex increasing
function of the number of jobs allocated to it. There are
no departures. 

references: S. Moharir, S. Sanghavi. Online Load Balancing and Correlated Randomness. 50th Annual Allerton Conference, 2012 U. Vazirani V. Vazirani A. Mehta, A. Saberi. Adwords and generalized online matching. Proceedings of FOCS, 2005

02.12.2014, Andrzej Dorobisz 
Random Walks that Find Perfect Objects and the Lov´asz Local Lemma 

We give an algorithmic local lemma by establishing a sufficient condition for the uniform random walk on a directed graph to reach a sink quickly. Our work is inspired by Moser’s entropic method proof of the Lov´asz Local Lemma (LLL) for satisfiability and completely bypasses the Probabilistic Method formulation of the LLL. In particular, our method works when the underlying state space is entirely unstructured. Similarly to Moser’s argument, the key point is that algorithmic progress is measured in terms of entropy rather than energy (number of violated constraints) so that termination can be established even under the proliferation of states in which every step of the algorithm (random walk) increases the total number of violated constraints. 

references: Dimitris Achlioptas, Fotis Iliopoulos, Random Walks that Find Perfect Objects and the Lovasz Local Lemma, FOCS 2014

25.11.2014, 18.11.2014, Jakub Brzeski 
Markov Chains and Random Walks on Graphs 



references: D. Aldous and J. A. Fill, Reversible Markov Chains and Random Walks on Graphs, monograph, 2014. L. Lovász, Random walks on graphs: a survey, Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993), 353–397, Bolyai Soc. Math. Stud., 2, János Bolyai Math. Soc., Budapest, 1996.

04.11.2014, Jakub Cieśla 
Finding All MaximallyMatchable Edges in a Bipartite Graph 

We consider the problem of finding all maximallymatchable edges in a bipartite graph G =
(V, E), i.e., all edges that are included in some maximum matching. We show that given any maximum
matching in the graph, it is possible to perform this computation in linear time O(n + m)
(where n = V and m = E). Hence, the time complexity of finding all maximallymatchable
edges reduces to that of finding a single maximum matching. 

references: T. Tassa, Finding all maximallymatchable edges in a bipartite graph, Theoret. Comput. Sci. 423 (2012), 50–58.

28.10.2014, Marcin Ziemiński 
Perfect Matchings in O(n log n) Time in Regular Bipartite Graphs 

In this paper, we give a randomized algorithm that finds a perfect matching in a dregular graph and
runs in O(n log n) time (both in expectation and with high probability). The algorithm performs an appropriately
truncated random walk on a modified graph to successively find augmenting paths. Our algorithm
may be viewed as using adaptive uniform sampling, and is thus able to bypass the limitations of
(nonadaptive) uniform sampling established in earlier work. We also show that randomization is crucial
for obtaining o(nd) time algorithms by establishing an
(nd) lower bound for any deterministic algorithm. 

references: A. Goel, M. Kapralov, S. Khanna, Perfect matchings in O(n log n) time in regular bipartite graphs, Proceedings of the 2010 ACM International Symposium on Theory of Computing (STOC'10), 39–46, ACM, New Yo

21.10.2014, Patryk Mikos 
Maximum Matching in Regular and Almost Regular Graphs 

An O(n^2*log(n))time algorithm that finds a maximum matching
in a regular graph with n vertices. More generally, the algorithm runs in O(r*n^2 log n)
time if the difference between the maximum degree and the minimum degree is
less than r. This running time is faster than applying the fastest known general
matching algorithm that runs in O(√nm)time for graphs with m edges, whenever
m = ω(rn1.5 log n). 

references: R. Yuster, Maximum matching in regular and almost regular graphs, Algorithmica 66 (2013), no. 1, 87–92.

14.10.2014, 07.10.2014, Bartłomiej Bosek 
Incremental algorithm on bipartite graphs 

The talk presents the jont work of Bartłomiej Bosek, Darek Leniowski, Piotr Sankowski, and Anna Zych. We investigated the problem of maintaining maximum size matchings in incremental bipartite graphs. In this problem a bipartite graph G between n clients and n servers is revealed online. The clients arrive in an arbitrary order and request to be matched to a subset of servers. In our model we allow the clients to switch between servers and want to maximize the matching size between them, i.e., after a client arrives we find an augmenting path from a client to a free server. Our goals in this model are twofold. First, we want to minimize the number of times clients are reallocated between the servers. Second, we want to give fast algorithms that recompute such reallocation. 

references: Bartłomiej Bosek, Dariusz Leniowski, Piotr Sankowski, Anna Zych. Online bipartite matching in offline time. In Proceedings of the 55th Symposium on Foundations of Computer Science, FOCS14, pp. 384393, 2014.
