Találkozó Frank András 60. születésnapja alkalmából

Fleiner Tamás (BME):

        A generalization of stable matchings

We describe a nonstandard generalization of stable matchings that may turn out to be useful in practical applications.

Győri Ervin (Rényi):

        On 2-factors in graphs

We survey sufficient (and mostly sharp) degree or degree sum conditions for the existence of 2-factors of exactly k cycles. Sometimes we have extra conditions on the cycles (say, prescribed edges) sometimes we have extra conditions (say, hamiltonicity).

Bill Jackson (University of London):

        Bounded direction-length frameworks

A d-dimensional direction-length framework is a pair (G,p), where G=(V;D,L) is a 'mixed' graph whose edges are labeled as 'direction' or 'length' edges, and p is a map from V to R^d. The label of an edge uv represents a direction or length constraint between p(u) and p(v). The framework (G,p) is bounded if there exits a K>0 such that every equivalent realisation (G,q) has |q(u)-q(v)|<=K for all u,v in V. I will describe a characterisation of bounded frameworks and outline its implications for the open problem of characterising globally rigid 2-dimensional generic frameworks. This is joint work with Peter Keevash.

Jordán Tibor (ELTE):

        When highly k-tree connected graphs are what we need

Inductive constructions for certain families of graphs may be very useful in inductive proofs. Sometimes a nice construction already exists but such an application is yet to be found. This will be illustrated  by the story of highly k-tree connected  graphs.

Király Tamás (ELTE/EGRES): 

        Hyperedges: potatoes, stars, or cephalopods?

Hyperedges may appear in several forms in connectivity augmentation problems: they can be members or bases of a matroid, nodes of a bipartite graph, or bi-sets of heads and tails. I will demonstrate the usefulness of these different viewpoints through some examples.

Király Zoltán (ELTE): 

        On partition connectivity

In 1997 Frank and Szigeti asked the following question. When a graph has a T-odd strongly connected orientation? I solved a special form of it: for which graphs we have a T-odd strongly connected orientation for each T with appropriate parity. In 1998 together with András we extend this result to k-arc connected orientations, introduced the notion of (k,l)-partition-connectedness, and asked several questions related to this notion. Since then most of these questions has been answered by different members of Egres group. But the basic question of Frank and Szigeti is still open.

The development of OR based decision support tools is a tremendous task which requires both a solid theoretical foundation and a deep practical insight.  Today I am going to speak about another challenge: how to gain the practitioners' acceptance so that they actually end up using the tools.  The talk will illustrated by some lessons learnt from the rolling stock scheduling problem of Netherlands Railways.

The known combinatorial algorithm for the path matching problem augments a non-maximal path matching using alternating paths and cycles. It is open whether it is enough to use alternating paths - this is the question to be discussed in my talk.

Starting from a recent joint work with  Ageev and Szigeti, a current leaf of my Frank-Arborescence,  I follow a path  back to the root: a question on Odd Forests, a first problem Andras Frank asked me. There are several recent and old stops on the way,  and I will not hide the other branches of the arborescence either

Szabó Jácint (SZTAKI/ELTE):

        Matroid parity and jump systems

András Recski conjectured that the matroid parity problem for linearly represented matroids remain polynomial time solvable if we change the parity requirement to any prescription without two consecutive gaps. In this lecture we outline a proof to this conjecture. The proof is based on Lovász' result on the polynomial solvability of the matroid parity problem for linearly represented matroids and on a technique about jump systems, proved by Sebő.

Szegő László (Corvinus):

        A distorted point of view: about a stunning joint result with Andras

When recalling a joint result of mine with Andras my heart still aches with pleasure. At the beginning of the millenium Andras and I gave the constructive characterization of graphs being the edge-disjoint union of k spanning trees after adding any new edge. The elementary case of k=2 must have been extended quite a lot. I would like to show an important part of the proof which evolved much after being published in the proceedings of IPCO 2001: the characterization of a node at which the inverse of the building operation can be applied. The question where other approaches can be found sounds interesting and promising.

We present some old and new results on edge-connectivity augmentation  in hypergraphs.

Tardos Éva (Cornell):

        Ad Auction Nash Equilibria with Conservative Bidder

Generalized Second Price Auction and its variants has been the main mechanism used by search companies to auction positions for sponsored search links. In this paper we study the social welfare of the Nash equilibria of this game. It is known that socially optimal Nash equilibria exists, but its not hard to see that in the general case there are also very bad equilibria: the gap between a Nash equilibrium and the socially optimal can be arbitrarily large. In this paper, we consider the case when the bidders are conservative, in the sense that they do not bid above their own valuations. We prove that for conservative bidders the worse Nash equilibrium and the socially optimal are within a factor of 1.618. Join work with Renato Paes Leme.

Végh László (EGRES):

        Augmenting undirected connectivity by one

We give a min-max formula for augmenting the node-connectivity of an undirected graph by one, proving the conjecture of Tibor Jordán.